Решение задачи 475

Условие:

Шерлок Холмс расследует преступление, в котором замешаны 120 человек, среди них один — преступник, а один — свидетель. Каждый день детектив может пригласить к себе одного или нескольких людей и если среди них есть свидетель, но нет преступника, то свидетель скажет, кто преступник. Как гарантированно раскрыть преступление за 9 дней?

Решение:

Закодируем всех людей разными последовательностями из нулей и единиц, в которых ровно 4 единицы. Таких последовательностей всего C₉⁴ (цэ из девяти по четыре), что равно 126, значит последовательностей хватит.

В i-ый день (1≤i≤9) пригласим тех и только тех людей, у которых в коде на i-ом месте стоит единица. У свидетеля и преступника разные коды, в которых стоят по 4 единицы, значит найдется разряд с номером k, в котором у свидетеля стоит 1, а у преступника 0.

Получается, в k-ый день Шерлок Холмс пригласит свидетеля, но не преступника и раскроет преступление.