Problem K/C. 787. (November 2023)

K/C. 787. How many points of intersection can the diagonals of a convex 16-gon have, if the points of intersections are all distinct?

(5 pont)

Deadline expired on December 11, 2023.

Sorry, the solution is available only in Hungarian. Google translation

1. megoldás. Minden átlót azok az átlók metszenek el, amelyeknek a végpontjait az átló elválasztja.

Válasszunk ki egy csúcsot és nézzük meg, hogy az innen induló átlókon hány metszéspont lehet. \(\displaystyle 13\) átló indul ebből a csúcsból, a metszéspontok száma szerint hétféle, a főátlón kívül \(\displaystyle 6\)-\(\displaystyle 6\) db ugyanolyan típusú.

Az egyes átlókon a metszéspontok maximális számát megkapjuk, ha az elválasztott csúcsok számát összeszorozzuk. Az ábrán a jelölt csúcsból induló egyik átlón keletkezik \(\displaystyle 5\)–\(\displaystyle 9\) metszéspont.

A jelölt csúcsból induló átlókon legfeljebb

\(\displaystyle 1\cdot13+2\cdot12+3\cdot11+4\cdot10+5\cdot9+6\cdot8+7\cdot7+8\cdot6+9\cdot5+10\cdot4+11\cdot3+12\cdot2+13\cdot1=455\)

metszéspont lehet összesen.

Ez mind a 16 csúcsnál így van és ekkor minden vizsgált átlót mindkét végpontjából, tehát kétszer számoltunk, valamint a metszéspontokat is kétszer számoltuk, így a metszéspontok száma legfeljebb

\(\displaystyle 455\cdot16:2:2=1820.\)

2. megoldás. Bármely négy csúcs meghatároz egy konvex négyszöget, melynek átlói a szokszögnek is átlói és metszik egymást. Így az átlók metszéspontjai és a csúcsnégyesek között kölcsönösen egyértelmű megfeleltetés van. Vagyis annyi metszéspont lehetséges, ahányféleképpen a 16 csúcs közül négyet kiválaszthatunk.

Így legfeljebb \(\displaystyle \binom{16}{4}=1820\) metszéspontja lehet az átlóknak.

Statistics:

198 students sent a solution.
5 points:	72 students.
4 points:	13 students.
3 points:	28 students.
2 points:	15 students.
1 point:	14 students.
0 point:	3 students.
Not shown because of missing birth date or parental permission:	47 solutions.

Problems in Mathematics of KöMaL, November 2023