Вторая математическая задача из фильма «Умница Уилл Хантинг»

Фильм «Умница Уилл Хантинг» рассказывает о тайном гении математики, которого сыграл Мэтт Дэймон. Сюжет повествует о том, как главный герой Уилл решает очень сложную математическую задачу, которая два года ставила в тупик профессоров математики из Массачусетского технологического института. Задача оказалась не только довольно простой, но и герой фильма всё равно допустил ошибку.

Задача, выписанная на доске, звучала так: «Нарисуйте все гомеоморфно неприводимые деревья размера n=10».

Позвольте мне объяснить это простым и понятным языком. Речь идёт обо всех возможных диаграммах, состоящих из десяти точек, соединённых линиями, от которых не может отходить ровно две другие линии (иначе диаграмма была бы сводимой), и не может быть замкнутых петель (иначе это не было бы деревом). «Гомеоморфно неприводимая» означает, что не имеет значения, под какими углами расположены линии, важно лишь, сколько линий отходит от каждой точки.

В фильме Уилл создает только восемь из десяти деревьев. Позвольте мне показать вам способ систематического решения этой задачи. Я буду рассматривать деревья как генеалогические древа, начиная с главы семьи.

Решение 1 – Девять детей. Это единственное решение, в котором всего два поколения.

Решение 2 – Трое детей с внуками разделили 6/0/0

6; font-family: 'Open Sans', sans-serif; color: #313131 !important; ">Обратите внимание, что не может быть ровно двух дочерних элементов, потому что тогда можно перейти от одного дочернего элемента к родительскому, а затем к другому дочернему элементу, что приведет к сокращению.

Решение 3 – Трое детей с внуками разделили 4/2/0

Обратите внимание, что ни у кого не может быть одного ребенка, иначе дерево было бы сокращаемым.

Решение 4 – Трое детей с внуками разделили 3/3/0

Решение 5 – Трое детей с внуками разделили 2/2/2

Решение 6 – Четверо детей с внуками разделили 5/0/0/0

Решение 7 – Четверо детей с внуками разделили 3/2/0/0

<

Помните, что у детей не может быть одного ребенка, иначе дерево можно было бы сократить.

6; font-family: 'Open Sans', sans-serif; color: #313131 !important; ">Решение 8 – Пятеро детей с внуками разделили 4/0/0/0

Можно было бы рассмотреть вариант с пятью детьми и внуками, разделенными по схеме 2/2/0/0, но это было бы гомеоморфно сведено к тому же дереву, что и решение 3 (мне потребовалось некоторое время, чтобы это понять).

Решение 9 – Три внука, внуки разделены 2/0/0. У одного из двух внуков четверо правнуков.

Решение 10 — Три внука, внуки разделены 2/2/0. У одного из двух внуков двое правнуков.

Я понимаю, что использую несколько упрощенных логических рассуждений, чтобы найти все десять решений. Однако, по крайней мере, я нашел все десять, в отличие от Уилла в фильме.

На следующей неделе я планирую обсудить ещё один фильм, где сцена с математикой была хорошо поставлена – «Дрянные девчонки».

Ссылки по теме:

Проблема в фильме «Умница Уилл Хантинг» – видео на YouTube от Numberfile

Решение вphp#s220" style="color:#a5341f;" target="_blank">MathProblems.info