A B. 4855. feladat (2017. február)

B. 4855. Egy táblázatot 0 és 1 számokkal töltöttünk ki úgy, hogy nincs két azonos sor, azonban bármelyik két oszlop és négy sor által meghatározott \(\displaystyle 4\times 2\)-es résztáblázatban van két azonos sor. Igazoljuk, hogy van olyan oszlop, amelyben az egyik szám pontosan egyszer fordul elő.

Javasolta: Lelkes Ádám

(6 pont)

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

Megoldás. Az állítást a sorok számára vonatkozó teljes indukcióval igazoljuk. Ha csak 1 sor van, akkor az állítás nyilvánvalóan teljesül. Tegyük fel most, hogy a \(\displaystyle k\)-nál kevesebb sort tartalmazó táblázatokra már igazoltuk az állítást, és vegyünk egy a feltételeknek megfelelő táblázatot, amelynek \(\displaystyle k\) sora van. Legyen \(\displaystyle s\) a táblázat egy tetszőleges sora. Ha \(\displaystyle s\)-et elhagyjuk a táblázatból, akkor továbbra is kielégíti a feltételeket, így az indukciós feltevés szerint lesz olyan \(\displaystyle o\) oszlopa, amelyben a 0 vagy az 1 pontosan egyszer szerepel. A szimmetria miatt feltehetjük, hogy \(\displaystyle o\)-ban az 1-es szerepel pontosan egyszer, mondjuk az \(\displaystyle s'\) sorban. Ha az \(\displaystyle o\) oszlopba eső helyen az \(\displaystyle s\) sorban 0 van, akkor az \(\displaystyle o\) oszlopban az eredeti táblázatban is pontosan egy 1-es szerepel, és készen vagyunk. Tegyük fel tehát, hogy az eredeti táblázatban az \(\displaystyle o\) oszlop két 1-est tartalmaz: az \(\displaystyle s\) és az \(\displaystyle s'\) sorokban. A feltétel szerint nincs két azonos sor, így van egy olyan \(\displaystyle o'\ne o\) oszlop, amelynek \(\displaystyle s\)-beli és \(\displaystyle s'\)-beli eleme különböző, vagyis az egyik 0, a másik pedig 1. Ha \(\displaystyle o'\)-ben az \(\displaystyle s\)-be és \(\displaystyle s'\)-be eső elemeken kívül is lenne még 0 és 1 is, mondjuk a \(\displaystyle t,t'\) sorokban, akkor az \(\displaystyle s,s',t,t'\) sorok és \(\displaystyle o,o'\) oszlopok által meghatározott \(\displaystyle 4\times 2\)-es résztáblázatnak nem lenne két azonos sora. Így \(\displaystyle o'\)-ben az \(\displaystyle s,s'\) sorokon kívüli elemek között vagy a 0, vagy az 1 már nem szerepel, és így ez a szám az \(\displaystyle o'\) oszlopban pontosan egyszer fordul elő (az \(\displaystyle s\)-be vagy az \(\displaystyle s'\)-be eső mezőben). Ezzel az állítást igazoltuk.

Statisztika:

30 dolgozat érkezett.
6 pontot kapott:	Baran Zsuzsanna, Beke Csongor, Borbényi Márton, Döbröntei Dávid Bence, Fuisz Gábor, Gáspár Attila, Győrffy Ágoston, Imolay András, Janzer Orsolya Lili, Kerekes Anna, Klász Viktória, Kovács 246 Benedek, Németh 123 Balázs, Saár Patrik, Szemerédi Levente, Tiszay Ádám, Tóth 827 Balázs, Tóth Viktor, Vári-Kakas Andor, Velkey Vince, Weisz Máté.
5 pontot kapott:	Simon Dániel Gábor, Szabó 417 Dávid, Szabó Kristóf.
4 pontot kapott:	2 versenyző.
2 pontot kapott:	1 versenyző.
0 pontot kapott:	3 versenyző.

A KöMaL 2017. februári matematika feladatai