Девятый бит: Блог кафедры АСОИУ ОмГТУ

«Пять предметов» или «Сколько стоит кровать?»

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

Первым прислал ответ В.Н. Задорожный. Да-да, преподаватели тоже имеют право участвовать решать и присылать ответы наравне со всеми. Владимир Николаевич подошел к решению задачи творчески. Помимо основного решения, он написал алгоритм для общего случая, т.е. для n предметов. В этой заметке не будем приводить общий алгоритм, а просто дадим ответ на задачу о пяти предметах.

Первые 3 взвешивания: сначала взвешиваем 2 пары, а из них победителей в тяжести. Назовём самого тяжелого — 1, проигравшего ему в 1 бою — 2, победителя другой пары — 3, проигравшего другой пары — 4, не взвешенного — 5. Четвертое взвешивание: 3 против 5, при этом получаем два исхода:

1) 3 тяжелее 5. Тогда 4 и 5 равноправны. Тратим пятое взвешивание на проверку, кто из них тяжелее.Шестое взвешивание — победитель пятого взвешивания со 2-м. Если победит 2 останется взвесить его с 3. Если 2 проиграет, то его останется взвесить с тем кто проиграл пятое взвешивание.

2) 5 тяжелее 3. Тратим пятое на сравнение 1 и 5.

2.1) 5 тяжелее. Шестое взвешивание — 2 с 3. Седьмое взвешивание — 2 с 4.

2.2) Тяжелее 1-й. Шестое взвешивание — 2 с 3. Если 2 побеждает — взвешиваем его с 5. Если 2 проигрывает — взвешиванием его с 4.

Итого: каждый такой путь состоит из семи взвешиваний (или шести в пути 2.1) и порождает однозначное решение.

Да, как выяснилось, данная задача описана у Кнута. (3-й том, стр. 207 русского издания).


Сегодня предлагается другая задачка, значительно проще предыдущей, но с мелким подвохом. Задачка по математике, позаимствованная из скетча Монти Пайтона.

Сколько стоит кровать?

Пришел в магазин покупатель и спрашивает: сколько стоит кровать? Первый продавец ему отвечает: «600 фунтов». Покупатель удивляется, что очень дорого, но тут второй продавец ему говорит: «Знаете, у первого продавца есть особенность — он все числа называет в 12 раз больше, чем они есть на самом деле. А в остальном он совершенно прав.»

«Ну хорошо», говорит покупатель первому продавцу, «значит я понял, что кровать стоит 50 фунтов, поскольку Вы все увеличиваете в 12 раз». Тот на это отвечает: «Это Вам кто сказал, мой напарник? Знаете, у него есть одна особенность — он все числа преуменьшает в 3 раза. А так, в остальном он совершенно прав.»

Вопрос: сколько стоит кровать на самом деле?

И как уже сложилось — все ответы, вопросы и пожелания на ящик: мыши собака «в ящик» точка ру :)

  • Самая сложная головоломка, без сомнения, это: «мыши собака «в ящик» точка ру» :о)

You must be logged in to post a comment.