Мой друг получил письмо от рекрутера, ведущее на сайт с такой задачкой:
На саммите большой пятидесятки собрались представители пятидесяти государств. От каждого государства присутствовал президент и премьер-министр. В перерыве между [дискуссиями] участники обменялись дипломатическими рукопожатиями, при этом, так как рукопожатия совершались в дипломатических целях, ни один президент не обменивался рукопожатиями с премьер-министром своей страны.
На званом обеде, посвящённом закрытию саммита, президент Анчурии опросил всех участников, кто сколько сделал рукопожатий, и не получил ни одного повторяющегося ответа. Сколько рукопожатий сделала премьер-министр Анчурии?
Как оказалось, задача имеет единственное решение.
Саму ссылку на сайт вы легко найдете в гугле.
Оставляя в стороне обсуждение «альтернативных» способов рекрутинга (а также тот факт, что решение было «вшито» в javascript страницы), попробуем решить задачу по-настоящему.
На фото: картинка из википедии по запросу G50
Надеюсь, к этому моменту все успели попробовать решить самостоятельно (а кто-то даже и преуспел в этом).
Итак, всего у нас 100 участников. Возможные значения рукопожатий лежат в диапазоне от 0 (очевидно) до 98 (т.к. никто не жмет руку себе и ПР и ПМ одной страны не жмут руки друг другу). Всего 99 значений.
Согласно принипу Дирихле хотя бы одно значение рукопожатий повторяется дважды. Однако по условию все участники сообщили ПР Анчурии разные числа. Доверившись их честности и аккуратности подсчета, придем к первому выводу: сам ПР Анчурии имеет количество рукопожатий, равное числу рукопожатий одного из участников (конечно, мы предполагаем, что президенты не страдают шизофренией и не опрашивают сами себя; в противном случае условие задачи просто невозможно реализовать).
Далее заметим, что у нас все равно остается 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
