Диагонали многоугольника

[wpoms.]

В правильном многоугольнике со 134 сторонами проведено 67 диагоналей, так, что из каждой вершины выходит ровно одна диагональ. Назовем длиной диагонали количество сторон многоугольника, заключенных между вершинами, которые она соединяет, не превосходящее 67. Если длины диагоналей расположить в порядке возрастания, получится последовательность из 67 чисел `(d_1, d_2,..., d_67)`. Можно ли сделать так, что: (a) $(d_1,...,d_{67}) =(\underbrace{2,...,2}_{6},\underbrace{3,...,3}_{61})$? (b) $(d_1 ,...,d_{67}) = (\underbrace{3,..., 3}_{8}, \underbrace{6,..., 6}_{55}, \underbrace{8,..., 8}_{4})$ ?

@темы: Комбинаторика

Comments

[Adjirranirr]

Лемма.
Независимо от расположения диагоналей, для `2n`-угольника справедливо
`\sum_{i} d_i \equiv n\ \text{mod} 2`

Для четырехугольника единственное возможное расположение диагоналей — накрест. Тогда `sum_{i} d_i = 2 + 2 = 4 \equiv 2\ \text{mod} 2`.
Предположим, что для `n` выполняется `sum_{i} d_i \equiv n\ \text{mod} 2`.
Рассмотрим `2(n + 1)`-угольник с `(n+1)` диагональю. Уберем из него произвольную диагональ вместе с ее вершинами; тогда останется `2n`-угольник, для которого выполняется предположение.
Если убранная диагональ имела нечетную «длину» `2k + 1`, то между ее концами находилось четное число точек, составляющих множество `M`. «Длина» любой диагонали с вершинами, ни одна из которых не принадлежит множеству `M`, изменилась на `2`; «длина» диагонали, у которой обе вершины принадлежали `M`, не изменилась. При этом, количество диагоналей ровно с одной вершиной из множества `M` четно, так как в противном случае `M` содержит нечетное количество точек. Длина диагонали ровно с одной вершиной из `M` изменилась на `1`. Так как таких диагоналей четное число, то суммарное изменение «длин» всех диагоналей есть четное число. Тогда, так как `sum_{i = 1}^{n} d_i^((n)) \equiv n\ \text{mod}2`, то для `2(n + 1)`-угольника справедливо
`sum_{i} d_i^((n+1)) \equiv sum_{i} d_i^((n)) + (2k + 1) \text {mod} 2 \equiv n + 1\ \text{mod}2`.
Если же убранная диагональ была четной, то множество `M` точек, лежащих между ее концами, содержит нечетное количество точек, и, аналогично, суммарное изменение «длин» будет нечетным (так как диагоналей, ровно одна вершина которых принадлежит `M`, нечетное количество).
Таким образом,
`sum_{i = 1}^{n + 1} d_i^((n+1)) \equiv n + 1\ \text{mod}2`, и по теореме о математической индукции, `AA n : sum_{i} d_i \equiv n\ \text{mod} 2`.

(a)

Можно.

Можно:
14 вершин заполним диагоналями следующим образом:

Остальные `130 - 14 = 120` вершин заполняются диагоналями «длины» `3` группами по `6`:



(b)

Нельзя.

Нельзя, так как
`3*8 + 6*55 + 8*4 = 386 != 1 \text {mod} 2`.

[Гость]

Владелец дневника видит IP-адреса пользователей, оставивших комментарии!