Теория информации в задачах на взвешивание

Одна из первых задач здесь после начала учёбы в ШАДе была вот эта классическая задача на взвешивание. Удивительным образом сегодня я её закольцую с учётом нового опыта.

В задачах подобного типа часто встаёт вопрос, а почему нельзя обойтись меньшим количеством операций? Иногда это очевидно, но формальное доказательство очень длинное и скучное. Так вот недавно узнал о технике, которая в некоторых случаях справляется с доказательством в несколько строчек.

Суть очень простая. Допустим, вы загадали целое число от 1 до 4, а ваш друг хочет его узнать. Друг может задавать вам вопросы типа «это число больше / меньше n?» и получать ответы «да / нет». Какое минимальное количество вопросов небходимо задать, чтобы гарантированно узнать число? (Необходимое количество вопросов не обязательно будет достаточным). Заметим, что ответ бинарен, поэтому в лучшем случае исходное множество вариантов при каждом ответе сокращается в 2 раза. Так как дважды два – четыре, то необходимо задать не менее двух вопросов. На языке теории информации говорят, что нужно передать вашему другу не менее 2 битов информации. Понятно, что в этом случае 2 битов достаточно.

В задачах на взвешивания ответ небинарен (<, >, =). Однако подход всё равно работает, в чём мы сегодня убедимся.

Итак, во-первых, добавлено новое решение для задачи с 12 монетами на языке теории информации (спасибо проф. мехмата МГУ Николаю Константиновичу Верещагину за прекрасные лекции!). Во-вторых, добавлена новая задача с 13 монетами, которая очень наглядно иллюстрирует, где именно возникает потребность в дополнительном взвешивании.

#ШАД

• Новое решение для 12 монет
• Весы и 13 монет
• Решение для 13 монет