Савватан и весы
У Алексея Савватеева на канале «Маткульт-привет» - занятная задача про взвешивание.
Есть 12 монет, одна из которых отличается по весу в неизвестную сторону. Как с помощью трёх взвешиваний найти эту монету и понять, легче она или тяжелее?
И задача со звёздочкой: можно ли решить для 13 монет?
Click to viewАлексей говорит, что сам не додумался за контрольное время, поэтому подсмотрел ключевой момент решения в шпаргалке. (И всё равно потом затупил и вытупил в прямом эфире).
В комментариях предложили алгоритм, похожий на код коррекции ошибок! Когда не строится дерево решений «если первое взвешивание такое, то второе делаем так, а если другое, то этак...», а сразу, безусловно, выполняются три взвешивания, извлекаются 3 трита информации, и по ним однозначно определяется номер монеты и отклонение её веса.
(Понятно, что 3 трита - это 27 исходов, а у нас 12 или 13 монет по два исхода, то есть 24 или 26, и 3 взвешиваний должно хватить... Но есть какие-то но).
Можете не смотреть спойлер в кино, а сами сперва покумекать.