Problem B. 4869. (April 2017)

B. 4869. Let \(\displaystyle A\) be a finite set of real numbers. A partition of the elements of \(\displaystyle A\) into at least two subsets is said to be a tiling if the (pairwise disjoint) subsets have at least two elements each, and are obtained from each other by a translation. Prove that \(\displaystyle A\) has an even number of tilings.

(5 pont)

Deadline expired on May 10, 2017.

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

Megoldás. Az általánosság megszorítása nélkül feltehetjük, hogy \(\displaystyle 0\in A\) és hogy \(\displaystyle A\) minden eleme nemnegatív valós szám. (Máskülönben \(\displaystyle A\) legkisebb elemét \(\displaystyle a_0\)-val jelölve áttérhetünk az \(\displaystyle A'=A-a_0=\{a-a_0:a\in A\}\) halmazra, amelynek nyilvánvalóan ugyanannyi parkettázása van, mint \(\displaystyle A\)-nak, nemnegatívak az elemei, és eleme a 0.) Először megmutatjuk, hogy \(\displaystyle A\) egy parkettázását már egyértelműen meghatározza a 0-t tartalmazó ,,parketta''. Tegyük fel ugyanis, hogy a \(\displaystyle 0\in B\subseteq A\) halmaz eltoltjaival lefedtük \(\displaystyle A\)-t. Ekkor az egyik parketta \(\displaystyle B\), a többivel \(\displaystyle A\setminus B\)-t kell lefednünk (átfedések nélkül). Legyen \(\displaystyle c\) az \(\displaystyle A\setminus B\) halmaz legkisebb eleme. Ezt csak a \(\displaystyle B+c\) eltolttal tudjuk lefedni (hiszen \(\displaystyle A\setminus B\)-n kívüli elemet nem fedhetünk le). Vagyis ezután az \(\displaystyle (A\setminus B)\setminus (B+c)\) halmazt kell \(\displaystyle B\) eltoltjaival lefednünk. Az előzőekhez hasonlóan a parkettázás egyértelműen folytatható, így (ha az egyáltalán lehetséges) a parkettázás egyértelmű.

Tegyük fel, hogy egy \(\displaystyle B=\{b_1,b_2,\dots,b_k\}\) halmaz (ahol \(\displaystyle b_1=0\)) alkalmas eltoltjaival parkettázható \(\displaystyle A\), vagyis \(\displaystyle |B|=k\geq 2\) és \(\displaystyle A\) előáll a páronként diszjunkt \(\displaystyle B+c_1, B+c_2, \dots, B+c_l\) halmazok uniójaként (legyen \(\displaystyle c_1=0\)), ahol \(\displaystyle l\geq 2\). Ez azt jelenti, hogy az \(\displaystyle A\) halmaz elemei éppen a \(\displaystyle b_i+c_j\) alakú összegek, ahol \(\displaystyle 1\leq i\leq k\) és \(\displaystyle 1\leq j\leq l\), és ez a \(\displaystyle kl\) darab összeg mind különböző. Ekkor viszont a \(\displaystyle C+b_1,C+b_2,\dots,C+b_k\) halmazok is az \(\displaystyle A\) halmaz egy parkettázást alkotják, így a 0-t tartalmazó \(\displaystyle C=C+b_1\) is meghatároz egy parkettázást. Tehát a 0-t tartalmazó \(\displaystyle B\) halmaz által meghatározott parkettázás megad nekünk egy parkettázást a 0-t szintén tartalmazó \(\displaystyle C\) halmaz eltoltjaival is. Világos, hogy a \(\displaystyle C\) által meghatározott parkettázáshoz pedig ily módon a \(\displaystyle B\) által meghatározott parkettázást rendeljük, vagyis a parkettázásokat párokba osztottuk. Egyedül azt kell megvizsgálnunk, hogy lehetséges-e \(\displaystyle B=C\), vagyis van-e olyan parkettázás, amelynek a párja saját maga. Ha \(\displaystyle B=C=\{b_1,b_2,\dots,b_k\}\) lenne, akkor a \(\displaystyle b_i+b_j\) összegeknek (\(\displaystyle 1\leq i,j\leq k\)) mind különbözőnek kellene lennie, azonban \(\displaystyle b_1+b_2=b_2+b_1\) mutatja (feltevésünk szerint \(\displaystyle k\geq 2\)), hogy ez nem lehetséges.

Statistics:

43 students sent a solution.
5 points:	Baran Zsuzsanna, Beke Csongor, Borbényi Márton, Csahók Tímea, Döbröntei Dávid Bence, Gáspár Attila, Győrffy Ágoston, Jánosik Áron, Janzer Orsolya Lili, Kerekes Anna, Kiss Gergely, Kocsis Júlia, Kovács 246 Benedek, Kőrösi Ákos, Kővári Péter Viktor, Lakatos Ádám, Mikulás Zsófia, Nagy Nándor, Németh 123 Balázs, Noszály Áron, Póta Balázs, Saár Patrik, Schrettner Jakab, Szabó 417 Dávid, Szakály Marcell, Szemerédi Levente, Tóth 827 Balázs, Tóth Viktor, Várkonyi Dorka, Weisz Máté.
4 points:	Csiszár Zoltán, Daróczi Sándor, Fraknói Ádám, Fuisz Gábor, Fülöp Anna Tácia, Imolay András, Simon Dániel Gábor, Soós 314 Máté, Szabó Kristóf, Tiszay Ádám, Vári-Kakas Andor, Zólomy Kristóf.
3 points:	1 student.

Problems in Mathematics of KöMaL, April 2017