Олимпиада имени Леонарда Эйлера 2018-2019 учебный год, I тур заключительного этапа

Устройство КК42 работает так: если положить в него четыре шарика, то в первый лоток вывалится второй по весу шарик (т.е. шарик веса $b,$ если $a > b > c > d)$, а во второй лоток вывалятся остальные. С другим числом шариков устройство не работает. Имеются 100 одинаковых на вид шариков попарно различных весов. Их пронумеровали числами $1, 2, \ldots, 100.$ Как, использовав прибор не более 100 раз, найти самый тяжелый шарик? ( К. Кноп )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Сначала каждый раз кладем в прибор 4 не отложенных ранее шарика и откладываем тот, который выпал в первый лоток. После 97 проб у нас остались не отложенными самый тяжелый и два самых легких шарика, так как ни один из них выпасть в первый лоток не может. Пусть их номера — $x, y, z.$ Выберем из отложенных любые три шарика $a, b, c$ и проделаем последние три пробы: $(x, a, b, c),$ $(y, a, b, c),$ $(z, a, b, c).$ В результате два раза в первый лоток выпадет второй по весу шарик из $a,$ $b,$ $c$ и один — когда вместе с $a, b, c$ в пробе участвует самый тяжёлый шарик из всех ста — самый тяжелый шарик из $a, b, c.$ Таким образом, самый тяжёлый шарик из всех — это шарик из $x,$ $y,$ $z,$ участвовавший в той из трёх последних проб, в которой в первый лоток выпал не тот шарик, что в двух других.