Комбинаторика на ИТМО: способы, графы, логика, клетки, комбигео

Подсказка 1

Нам дали уж слишком какое-то магическое число, но каждое его слагаемое похоже на какой-то комбинаторный подсчёт. Может быть, у нас получится объяснить, как получить каждое из этих слагаемых?

Подсказка 2

1-ое слагаемое: эта формула нам так и кричит, что в ней выбрали 4 вершины многоугольника без учёта их порядка. А как выбор 4-ёх вершин связан с диагоналями?

Подсказка 3

2-ое слагаемое: с помощью какого предположения было получено первое слагаемое? Заметьте, что почти каждое следующее слагаемое стоит со знаком минус, а значит, они как-то уточняют нашу первоначальную оценку.

Подсказка 4

2-ое слагаемое: давайте вспомним, что у нас в условии правильный многоугольник, попробуйте порисовать разные правильные многоугольники и диагонали в них, чтобы найти такую точку, в которой всегда пересекаются много диагоналей, что это за точка?

Подсказка 5

2-ое слагаемое: верно, это центр нашего многоугольника. Остаётся только посчитать, сколько раз мы посчитали её и вычесть так, чтобы по итогу в нашем подсчёте точка осталась учтена.

Подсказка 6

3-е слагаемое: оно явно содержит похожие диагонали на те, которые мы выбирали, когда рассуждали про центр, потому что в нём тоже фигурирует n/2. Может быть стоит опять порассуждать про такие диагонали?

Подсказка 7

3-е слагаемое: первый множитель в слагаемом это n/2, давайте тогда зафиксируем какую-то диагональ, проходящую через центр многоугольника. Попробуйте понять, что означают остальные множители, последовательно распутывая, за что отвечает каждый из множителей.

Подсказка 8

3-е слагаемое: верно, слева и справа от диагонали осталось по n/2-1 точке. А значит, вторым действием мы скорее всего выбрали с одной из сторон одну из точек. Почему тогда последний множитель не такой же, а имеет на 2 точки меньше? Понятно, что, выкинув 2 точки с другой стороны, мы запретили какие-то 2 диагонали, остаётся понять - какие?

Подсказка 9

3-е слагаемое: кажется, что пока наши рассуждения задают только пару диагоналей и проблем не видно, но можно ли как-то для этой пары найти однозначно третью диагональ, которая бы проходила через их точку пересечения?

Подсказка 10

3-е слагаемое: да, можно, если отразить симметрично вторую диагональ относительно "центральной".

Подсказка 11

3-е слагаемое: а вы заметили, что на самом деле это слагаемое содержит в себе удвоенное количество ситуаций, про которые мы рассуждали? Ведь, когда мы брали диагональ-1 с концами по разные стороны от "центральной" диагонали и отражали её, то получалась диагональ-2, которая тоже может быть посчитана нашими рассуждениями, а так как симметричная для 2-ой диагонали - 1-ая, то мы посчитали всё дважды. А сколько раз мы посчитали такие ситуации в 1-ом слагаемом?

Подсказка 12

Верно, по 3 раза, потому что там мы выбираем неупорядоченную пару диагоналей, а в наших рассуждениях мы получали неупорядоченные тройки диагоналей (если учесть, что мы посчитали их дважды), а значит 1 наша тройка содержит по 3 пары. Но вычесть всё равно придётся удвоенное количество, поэтому мы победили!!!