Задачка про саммит G50 и рукопожатия

Мой друг получил письмо от рекрутера, ведущее на сайт с такой задачкой:

На саммите большой пятидесятки собрались представители пятидесяти государств. От каждого государства присутствовал президент и премьер-министр. В перерыве между [дискуссиями] участники обменялись дипломатическими рукопожатиями, при этом, так как рукопожатия совершались в дипломатических целях, ни один президент не обменивался рукопожатиями с премьер-министром своей страны.

На званом обеде, посвящённом закрытию саммита, президент Анчурии опросил всех участников, кто сколько сделал рукопожатий, и не получил ни одного повторяющегося ответа. Сколько рукопожатий сделала премьер-министр Анчурии?

Как оказалось, задача имеет единственное решение.

Саму ссылку на сайт вы легко найдете в гугле.
Оставляя в стороне обсуждение «альтернативных» способов рекрутинга (а также тот факт, что решение было «вшито» в javascript страницы), попробуем решить задачу по-настоящему.

На фото: картинка из википедии по запросу G50

Надеюсь, к этому моменту все успели попробовать решить самостоятельно (а кто-то даже и преуспел в этом).

Итак, всего у нас 100 участников. Возможные значения рукопожатий лежат в диапазоне от 0 (очевидно) до 98 (т.к. никто не жмет руку себе и ПР и ПМ одной страны не жмут руки друг другу). Всего 99 значений.
Согласно принипу Дирихле ^[1] хотя бы одно значение рукопожатий повторяется дважды. Однако по условию все участники сообщили ПР Анчурии разные числа. Доверившись их честности и аккуратности подсчета, придем к первому выводу: сам ПР Анчурии имеет количество рукопожатий, равное числу рукопожатий одного из участников (конечно, мы предполагаем, что президенты не страдают шизофренией и не опрашивают сами себя; в противном случае условие задачи просто невозможно реализовать).

Далее заметим, что у нас все равно остается 99 участников и 99 различных чисел. Это значит, что каждое число присутствует ровно один раз, т.е. есть участник без рукопожатий, с 1 рукопожатием и т.д. вплоть до 98.

Возьмем участника с 98 рукопожатиями. Очевидно, он пожал руки всем-всем, кроме себя самого и своего соотечественника (т.к. ПР не жмут руки своим ПМ). Без потери общности допустим, что это ПР. Тогда понятно, что его ПМ — это и есть участник с числом 0 (потому что наш ПР пожал руки всем кроме него, т.е. все имеют как минимум 1 рукопожатие).
Назовем этих товарищей ПР98 и ПМ0 (запомним, что они из одной страны).

Продолжим рассуждение, рассмотрев ПР97. Он не пожал руку своему ПМ, себе, а также ПМ0 (его все обделили вниманием). Все остальные имеют уже минимум два рукопожатия (от ПР98 и ПР97). В результате оказывается, что единственный участник, получивший одно рукопожатие — только ПМ из той же страны, что и ПР97. Конечно, назовем его ПМ1.

Продолжив таким образом цепочку рассуждений, обнаружим, что ПР и ПМ из одной страны всегда называют в сумме 98 рукопожатий (это и есть наш второй вывод).

Теперь с неизбежностью обнаружим, что единственное повторяющееся здесь возможное число — это середина нашей сходящейся цепочки, т.е. 49. Половина цепочки строится «сверху» от 98 вниз, и каждое число может присутствовать только один раз. Другая же половина строится снизу вверх от 0, и тоже все элементы заполнены однозначно. Единственное возможное повторение — это совпадение чисел, когда цепочки сойдутся (естественно, сойдутся они посредине 98, т.е. на числе 49):
[0, 1, 2, ... 48, 49] и
[98, 97, 96, ... 50, 49]
А поскольку из первого вывода следует, что ПР Анчурии имеет число рукопожатий такое же, как у другого участника, то получим, что он является ПР49. Из второго вывода следует, что ПМ Анчурии пожала руки также (98-49=49) участникам саммита.

Автор: iaroshenko

Источник ^[2]