1
1

Среди 25 монет есть ровно 2 фальшивые. Есть волшебный горшок, в который можно положить 2 монеты, и он покажет количество фальшивых монет в этой паре. За какое наименьшее число таких операций можно гарантированно определить обе фальшивые монеты?

задан 21 Авг '21 0:04

изменен 21 Авг '21 0:46

Меньше 14-ти, что то не получается

(21 Авг '21 9:35) mihailm

Можно ли также положить одну монету?

(21 Авг '21 9:53) Rene

@Rene, это не важно. Все равно у нас в процессе будут куча монет про которые точно известно, что они не фальшивые. Взяв одну настоящую добавляем к ней ту которую вы хотели положить одну

(21 Авг '21 10:49) mihailm
1

По-моему, за 9 операций делается просто, но я пока не знаю, как доказать в обратную сторону.

(21 Авг '21 11:48) falcao

@falcao, 9 это странный ответ. 7 монет минимум останутся без проверки.

(21 Авг '21 11:53) spades

@falcao, а как Вы смогли за 9?

(21 Авг '21 11:59) Казвертеночка

@mihailm Что ж, вы можете сказать, что это не имеет значения, но это похоже на то, что должно быть доказано в решении.

Например, если бы требовалось всего 5 монет, то найти 2 подделки из 6 было бы совершенно другим решением, чем если бы для волшебного горшка требовалось от 1 до 5.

И кстати у меня тоже получилось 14.

(21 Авг '21 12:02) Rene
2

Я ошибочно прочитал условие. Мне показалось, что в волшебный горшок можно положить на проверку любое число монет. В этом случае 9 проверок хватает, и такой вариант задачи звучит, на мой взгляд, достаточно интересно.

(21 Авг '21 12:42) falcao

@falcao, ну раз звучит интересно, то было бы не менее интересно взглянуть на Ваш пример с 9-ю проверками.

(21 Авг '21 13:14) Казвертеночка
показано 5 из 9 показать еще 4
10|600 символов нужно символов осталось
3

13 проверок.
Выбираем 22 монеты и проводим 11 проверок. Если среди выбранных оказалось 2 фальшивых, то двумя проверками их находим.
Если фальшивых нет, то тоже элементарно найти за 2 проверки 2 фальшивых из трех.
Случай одной фальшивой монеты. Обозначим пару, где она может быть (a,b). Невыбранные (c,d,e).
Кладем в горшок (a,c) потом (a,d).
Если горшок показал один раз 2, то фальшивки найдены.
Иначе 4 случая:

  1. 11 - фальшивые a и е
  2. 10 - фальшивые b и c
  3. 01 - фальшивые b и d
  4. 00 - фальшивые b и e
ссылка

отвечен 21 Авг '21 11:52

изменен 21 Авг '21 11:52

Содержательная часть в задаче - это нахождение фальшивок среди 5 монет за 3 проверки. Остальные - это уже вода, и по большому счету, редакторский брак.

(21 Авг '21 12:26) spades
1

Нужно, наверное, ещё доказать, что 12 проверок не достаточно.

(21 Авг '21 12:44) falcao
2

Это достаточно очевидно. После 11 проверок останется непроверенным как минимум 3 монеты. Пусть все эти проверки не показали фальшивых. Тогда, если в 12-й проверке будет результат 1, то мы не сможем определить настоящую среди этих 3 при любом выборе монет.

(21 Авг '21 18:43) spades
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×293
×151
×102
×41
×4

задан
21 Авг '21 0:04

показан
375 раз

обновлен
21 Авг '21 18:43

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru