A B. 4869. feladat (2017. április)

B. 4869. Legyen \(\displaystyle A\) a valós számok egy véges halmaza. Azt mondjuk, hogy \(\displaystyle A\) elemeinek legalább két csoportba osztása egy parkettázás, ha az így kapott (páronként diszjunkt) részhalmazok legalább két eleműek és egymás eltoltjai. Bizonyítsuk be, hogy \(\displaystyle A\)-nak páros sok parkettázása van.

(5 pont)

A beküldési határidő 2017. május 10-én LEJÁRT.

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.

Statisztika:

43 dolgozat érkezett.
5 pontot kapott:	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 pontot kapott:	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 pontot kapott:	1 versenyző.

A KöMaL 2017. áprilisi matematika feladatai