Иван ⇄ жизнь
Смотрю на Netflix Brooklyn 99, простенькую и добрую комедию про нью-йоркских копов. Карантин, чо, могу себе позволить.

Так вот, в S02E18 копы всем участком безуспешно пытаются решить такую головоломку. Есть остров, и на нем 12 человек. 11 одинакового веса, один – то ли чуть легче, то ли чуть тяжелее остальных. Весов нет, но есть качели (которые перевешивают в ту сторону, на которой больше вес, или находятся в балансе). Нужно за 3 взвешивания на качелях определить, кто из 12 особенный и легче он или тяжелее. Как это сделать?

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

14 comments

Petr Korolev
Красиво. С 4й итерации дошел до правильного алгоритма. Очень нравиться что идя от просто к сложносу ты видишь изъян алгоритмя, фиксишь его, получаешь следующий. Фиксишь и получаешь ответ. :) 
мыслят все примерно одинаково. хотя может это только у меня такой путь был.
ego 108
Ну так вроде не сложно.. сначала по 6 взвесить, потом по 3.. а потом из 3х взвешиванием 2х станет ясно.. или так много людей за раз не взвесить?))
Alina Aisay
ego 108
Ну так вроде не сложно.. сначала по 6 взвесить, потом по 3.. а потом из 3х взвешиванием 2х станет ясно.. или так много людей за раз не взвесить?))
Но ты не знаешь, человек легче или тяжелее нормы.
2
Seva
У меня получилось перебором с отсечениями по информационным оценкам, было бы интересно услышать про решение без перебора.

Коды натянуть на это дело не осилил, скорее всего должен быть адаптивный и очевидно не xor-ах.
Seva
ego 108
Ну так вроде не сложно.. сначала по 6 взвесить, потом по 3.. а потом из 3х взвешиванием 2х станет ясно.. или так много людей за раз не взвесить?))
После первого взвешивания каждый из двенадцати человек может быть искомым. На оставшиеся два взвешивания остается 9 исходов, по которым надо выбрать одного из двенадцати. Что невозможно.
1
ego 108
Alina Aisay
Но ты не знаешь, человек легче или тяжелее нормы.
ааа) теперь ясно)
Iván Bogatyy
Seva
У меня получилось перебором с отсечениями по информационным оценкам, было бы интересно услышать про решение без перебора. Коды натянуть на это дело не осилил, скорее всего должен быть адаптивный и очевидно не xor-ах.
Да, именно это решение имел в виду. Имхо очень красиво, что теория информации позволяет заранее предсказать результат в каждой ветке. Мб "без перебора" не абсолютно точная формулировка, но в общем линейный перебор, а не экспоненциальный.
Petr Korolev
Petr Korolev
Красиво. С 4й итерации дошел до правильного алгоритма. Очень нравиться что идя от просто к сложносу ты видишь изъян алгоритмя, фиксишь его, получаешь следующий. Фиксишь и получаешь ответ. :)  мыслят все примерно одинаково. хотя может это только у меня такой путь был.
Ваня! Это фиаско. У меня было три разных решения, но у всех есть пограничные кейсы где нужно 4 взвешивания.  

Мне казалось, при разных результатах результатах можно применить разные стратегии и тогда они перекрывают друг друга. Но нет. Я забыл что в олном из них я не знаю легче или тяжелее человек в конце.  А делал предположение что знаю (из предыдущих взвешиваний). Так что решения пока нет
Aidar Y.
Делим их на 3 кучки и за 4 взвешивания находим особенного
Aidar Y.
То есть за 3, конечно
BEKISH
логично начать с 6 против 6, но нет. Ставим 4 vs 4 на первое взвешивание, дальше очень просто…
Show next 3 comments