Старобългарска задача

[Румен Симеонов]

Старобългарска задача, според едно момиче-пъпешче:
https://artofproblemsolving.com/communi ... 4p13514379

[ptj]

Или аз не разбирам нещо или проблема е прекалено елементарен.

Броя на диагоналите в правилен n-ъгълник излизащи от всеки връх е точно n-3 (без самия връх и двата му съседни).

Те са четни точно когато [tex]n \ge 4[/tex] и е нечетно.

[grav]

Триангулация на правилен [tex]n[/tex]-ъгълник се нарича напълно четна ако броя от диагоналите излизащи от всеки връх е четен. Да се намерят всички [tex]n[/tex], за които съществува напълно четна триангулация на правилен [tex]n[/tex]-ъгълник.

[ptj]

О.К.
Доколкото разбрах триангулация е всяко разделяне на триъгълници посредством свързване на върхове, като няма пресичащи се диагонали.

Хипотезата ми е , че n е степен на 2. Доказването на съшествуването е много лесно, докато обратната част иска малко изглаждане...

[Гост]

n ъгълник-page-001.jpg (132.33 KiB) Прегледано 233 пъти

[ptj]

Браво, перфектна идея.

Грешката в моята хипотеза бе, че от n-ъгълник минавах към 2n-ъгълник, без да съобразя че миминалния отговарящ n-ъгълник е с 3 върха.

Доказателството на обратната хипотеза е със същата картинка (за индукцията), но с премахване на 3 върха.

С подобно спускане може да стигнем до n-ъгълник с 3,4 или 5 върха. За всеки от последните два триангулацията е само една (с точност до симетрии и ротации) и не отговаря на условието на задачата.

П.П. Може би не е много добре да приемам 3-ъгълника за 0-лева триангулация, защото той няма диагонали.

Както и да е, 6 ъгълника отговаря на условието на задачата.

Интересно е също дали тази задача може да се реши с някои теореми от теория на графите.