Давайте решим интересную задачу, на которую мое внимание обратил Лоуренс Брайан. Спасибо, Лоуренс :)

(На приведенном выше графике показано 8 человек, то есть 4 пары, где H и G являются ведущими, а супруги ведущими)

Поиск в Google после ее решения обнаружил видео на YouTube, которое несколько экстравагантно называет «НЕВОЗМОЖНОЙ головоломкой с рукопожатием». На самом деле это выполнимо, и это хороший пример того, как решить проблему, разбив ее на более мелкие проблемы.

Постановка задачи

Мистер и миссис Брайан приглашают на ужин еще четыре пары. В начале вечера руки дрожат. Г-н Брайан отмечает, что никто из остальных девяти человек не пожал столько рук. Так как же пожали руки мистеру Брайану? Сколько встряхнула миссис Брайан? (Ясно, что нельзя здороваться ни с супругой, ни с самим собой.)

Подход

Мы собираемся уменьшить это до меньшей проблемы, а затем повторно применять ту же логику каждый раз. Идея состоит в том, что мы можем удалить кого-то из «графа» рукопожатий и сосредоточиться на рукопожатиях, которые сделали все остальные. Мы можем это сделать и отслеживать, сколько рук сделали мистер и миссис Брайан. В частности, мы собираемся «удалить» людей из графика рукопожатий по два за раз (оказывается, в их парах) после, когда мы определили, пожали ли руки мистер и миссис Брайан. Затем мы выясним, на что похож новый график рукопожатия, и будем повторять, пока не закончим.

Я говорю «граф», потому что математический объект, используемый для представления таких проблем, обычно является графом. Люди в этом случае будут представлены в виде вершин, а рукопожатия - в виде ребер.

Решение

Из этих 9 человек один пожал 0 рук, один пожал 1, один пожал 2,… один пожал 8 рук.

Один человек пожал 8 рук. Исключая себя и своего супруга, это должно означать, что они пожали руки всем остальным. Итак, супруга этого человека не пожалела руки. Это означает, что наш главный герой пожал хотя бы 1 руку. Кроме того, миссис Брайан не удалили, поэтому она пожала хотя бы одну руку.

Теперь давайте удалим этого человека и его супругу из «графика». Осталось 8 человек, еще 7 человек и наш главный герой Май Брайан. Количество рукопожатий каждого оставшегося человека уменьшается на единицу для этой подгруппы людей, поскольку каждый из них пожал руку человеку, который пожал 8 рук. Таким образом, человек, который пожал больше всего рук, пожал 6 рук. Повторяется та же логика, поскольку этот человек, следовательно, должен был пожал всем, кроме своей руки и руки своего супруга. Наши главные герои, мистер и миссис Брайан, теперь по 2 рукопожатия, и у нас осталось 6 человек: наш главный герой мистер Брайан и еще 5 человек.

Теперь мы удалим человека, указанного в предыдущем абзаце, и его супругу из графика рукопожатий. У всех них количество рукопожатий уменьшилось на 1, так как все они пожали руку человеку, которого удалили вместе с их супругой, в предыдущем абзаце. Главный человек пожал 4 руки. По той же логике, мы можем удалить их и их супругу, мистера и миссис Брайан, которые пожали руки всего 3 раза, и осталось 4 человека.

Наконец, у нас есть четыре человека, и один человек, который не был мистером Брайаном, пожал две руки этим четырем людям, и, таким образом, супруга этого человека не пожал руки этим четырем. Добавление в последнее рукопожатие мистера Брайана заканчивается четырьмя рукопожатиями, как и миссис Брайан.