2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Мудрая Сова и 5 монет
Сообщение19.06.2018, 23:45 
Аватара пользователя


01/12/11

8634
Перед Мудрой Совой выложили 5 монет. Сова точно знает, что ровно две из этих монет - фальшивые, причём одна фальшивая монета тяжелее настоящей, а другая - легче.
Задача Совы - обнаружить обе фальшивые монеты за 3 взвешивания на чашечных весах без гирь.
Но есть два момента. Во-первых, ни на какую чашу весов нельзя класть две или более монет одновременно. Во-вторых, все три взвешивания должны быть спланированы заранее, то есть, последующие взвешивания не должны зависеть от результатов предыдущих (говоря языком программистов, код должен быть без ифов).

Помогите Сове!

 Профиль  
                  
 
 Re: Мудрая Сова и 5 монет
Сообщение20.06.2018, 01:20 
Заслуженный участник


04/05/09
4582
А почему вы решили, что это возможно?

 Профиль  
                  
 
 Re: Мудрая Сова и 5 монет
Сообщение20.06.2018, 02:16 
Заслуженный участник


20/08/14
11061
Россия, Москва
По моему тоже невозможно: если нигде не ошибся, то есть всего 4 варианта топологии последовательностей взвешивания и для всех них у меня построены контрпримеры распределения монет, когда не удаётся определить обе фальшивых монеты.

 Профиль  
                  
 
 Re: Мудрая Сова и 5 монет
Сообщение20.06.2018, 09:18 
Аватара пользователя


01/12/11

8634
venco в сообщении #1321246 писал(а):
А почему вы решили, что это возможно?

Задача - не моя, мне её прислали по почте. Возможно, под помощью Сове имелось в виду либо дать ей нужный алгоритм, либо доказать, что его нет.

 Профиль  
                  
 
 Re: Мудрая Сова и 5 монет
Сообщение20.06.2018, 10:18 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
Мудрая сова не использует слово "если":

1) первую сравниваем со второй
2) третью сравниваем с четвертой
3) пятую сравниваем с настоящей

 Профиль  
                  
 
 Re: Мудрая Сова и 5 монет
Сообщение20.06.2018, 10:25 


05/09/16
11461
TOTAL
1) первую сравниваем со второй : перевесила первая
2) третью сравниваем с четвертой : перевесила третья
3) пятую сравниваем с настоящей : пятая оказалась настоящей
и? :mrgreen:

 Профиль  
                  
 
 Re: Мудрая Сова и 5 монет
Сообщение20.06.2018, 10:36 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
Вот на языке программирования:

$v1=sign(a(1)-a(3))$
$v2=sign(a(2)-a(4))$
$v3=sign(a(5)-a(2+v2))$

По значениям $v1, v2, v3$ находим фальшивки

 Профиль  
                  
 
 Re: Мудрая Сова и 5 монет
Сообщение20.06.2018, 10:40 


21/05/16
4292
Аделаида
У вас третье взвешивание зависит от результата второго.

 Профиль  
                  
 
 Re: Мудрая Сова и 5 монет
Сообщение20.06.2018, 10:50 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
kotenok gav в сообщении #1321284 писал(а):
У вас третье взвешивание зависит от результата второго.
Все мои взвешивания спланированы заранее, код без ифов, как требовалось. Или автору придется уточнить, что такое "взвешивания спланировать заранее".

 Профиль  
                  
 
 Re: Мудрая Сова и 5 монет
Сообщение20.06.2018, 12:12 


02/04/18
240
Если я правильно понимаю, то сова нумерует монеты от 1 до 5, потом составляет таблицу из трех строк, в первом столбце пишет пары цифр, а во втором будут фигурировать результаты взвешивания - всего 27 исходов, при 20 вариантах распределения. На этом этапе пока взвешиваний хватает...

Конечно, при таком подходе порядок взвешиваний неважен, и мы можем их переставлять в плане. При этом очевидно, что хотя бы одна из монет участвует во взвешиваниях дважды (Дирихле). Пусть для определенности то номер 1 (опять же, до начала взвешивания мы можем перенумеровывать их как угодно), и она сравнивается сначала с 2, потом с 3. Всего 9 исходов, но нам интересен, в частности, случай, когда она тяжелее их обеих.
Следовательно, она - тяжелая, а легкая - среди четырех остальных. Еще одним взвешиванием мы можем различить три варианта, но никак не 4. Таким образом, сове никак не удастся совершить задуманное.

Но все же оценим шансы совы. Все же 9 исходов!
1) Если 1=2, 1=3, то это все настоящие монеты, тогда фальшивки уже найдены. Сравнение 4 и 5 позволит их различить.
2) Если 1=2, 1>3 - первые настоящие, 3 - легкая фальшивка. Тяжелая - либо 4, либо 5. Сравнив их между собой, мы различим тяжелую от настоящей.
3-5) 1=2, 1<3; 1>2, 1=3; 1<2, 1=3 - эти исходы аналогичны (2) с точностью до нумерации и терминологии веса.
6) 1>2, 1<3 - легко понять, что 3 - тяжелая фальшивка, 2- легкая, а 1 - настоящая. Третье взвешивание не понадобится, поэтому без разницы, как его провести.
7) 1<2, 1>3 - симметричен исходу (6)
8) 1>2, 1>3. Как указано выше, 1 - тяжелая. И раз уж нам понравилось взвешивать 4 и 5, то так и поступим. При разности весов мы находим легкую фальшивку. Но при равенстве... выходит, что среди монет 2 и 3 одна фальшивая легкая и одна настоящая, но какая из них, мы выяснить не сможем.
9) 1<2, 1<3 - аналогично (8), но легкая и тяжелая монеты меняются местами в рассуждениях.

Итак, при самом удачном планировании (взвесить 1-2, 1-3, 4-5) мы не сможем различить варианты ТЛННН и ТНЛНН, а также ЛТННН и ЛНТНН, хотя одна из монет локализуется полностью. Все остальные (всего 16) позволяют найти обе монеты. 80% успеха - это уже что-то.

Ну что, по крайней мере, так будут гарантированно найдены две настоящие - не так уж и плохо. И даже одна фальшивая, но какая именно, предсказать заранее нельзя.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group