Problem B. 4200. (September 2009)

B. 4200. For a finite point set \(\displaystyle A\) in the plane, let \(\displaystyle v(A)\) denote the number of triangles in a triangulation of set \(\displaystyle A\), and let \(\displaystyle A+A=\{x+y\mid x,y\in A\}\), where the sum of two points is defined as the point whose position vector is the sum of the position vectors of the terms. Prove that \(\displaystyle v(A+A)\ge 4v(A)\).

Suggested by I. Ruzsa, Budapest

(5 pont)

Deadline expired on October 12, 2009.

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

Megoldás. Rögzítsük \(\displaystyle A\) egy tetszőleges \(\displaystyle \Delta\) háromszögelését. Megtartva az előző feladat jelöléseit, a \(\displaystyle \Delta\)-ban található háromszögek száma \(\displaystyle v(A)=2a+d-2\), ahol \(\displaystyle d=b+c\) az \(\displaystyle A\) halmaz \(\displaystyle C\) határára eső pontjainak száma. E háromszögek oldalai közül pontosan \(\displaystyle d\) darab helyezkedik el \(\displaystyle C\) határán, a többi \(\displaystyle C\) belsejében fut. Az ilyen szakaszok száma \(\displaystyle (3v(A)-d)/2=3a+d-3\), hiszen minden háromszögnek 3 oldala van, de a belül futó oldalszakaszokra két háromszög is illeszkedik.

Az \(\displaystyle A+A\) halmazt kicsinyítsük felére az origóból. Az így kapott \(\displaystyle A'\) halmazra nyilván \(\displaystyle v(A')=v(A+A)\). Az \(\displaystyle A'\) halmaz konvex burka szintén \(\displaystyle C\) lesz. Jelölje \(\displaystyle a'\) és \(\displaystyle d'\) az \(\displaystyle A'\) halmaz \(\displaystyle C\) belsejébe, illetve \(\displaystyle C\) határára eső pontjainak számát. Az \(\displaystyle A'\) halmaz pontjai éppen az \(\displaystyle xy\) (\(\displaystyle x=y\) esetén ponttá elfajuló) szakaszok felezőpontjai, ahol \(\displaystyle x,y\in A\). Az \(\displaystyle A'\) halmaz \(\displaystyle C\) határára eső elemei között szerepelnek az \(\displaystyle A\) halmaz \(\displaystyle C\) határára eső elemei, melyek \(\displaystyle C\) határát \(\displaystyle d\) szakaszra osztják. Szerepelnek továbbá ezen szakaszok felezőpontjai is, melyek az előzőekkel együtt \(\displaystyle C\) határát már \(\displaystyle 2d\) szakaszra osztják. Innen látszik, hogy \(\displaystyle d'\ge 2d\). Hasonlóképpen, az \(\displaystyle A'\) halmaz \(\displaystyle C\) belsejébe eső elemei között szerepelnek az \(\displaystyle A\) halmaz \(\displaystyle C\) belsejébe eső elemei, továbbá a \(\displaystyle \Delta\)-ban szereplő háromszögek \(\displaystyle C\) belsejében haladó oldalainak a felezőpontjai, melyek sem egymással, sem az előzőkkel nem esnek egybe. Ezért \(\displaystyle a'\ge a+(3a+d-3)=4a+d-3\). Mindent összevetve,

\(\displaystyle v(A+A)=v(A')=2a'+d'-2\ge 2(4a+d-3)+2d-2=4(2a+d-2)=4v(A).\)

Statistics:

20 students sent a solution.
5 points:	Ágoston Tamás, Damásdi Gábor, Dudás 002 Zsolt, Éles András, Kovács 729 Gergely, Márkus Bence, Mester Márton, Mészáros András, Perjési Gábor, Somogyi Ákos, Strenner Péter, Szabó 928 Attila, Weisz Ágoston.
4 points:	Keresztfalvi Tibor, Nagy Róbert.
3 points:	1 student.
2 points:	2 students.
1 point:	1 student.
0 point:	1 student.

Problems in Mathematics of KöMaL, September 2009