Feladat: B.4855 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  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 Benedek ,  Németh Balázs ,  Saár Patrik ,  Szemerédi Levente ,  Tiszay Ádám ,  Tóth Balázs ,  Tóth Viktor ,  Vári-Kakas Andor ,  Velkey Vince ,  Weisz Máté 
Füzet: 2017/november, 472 - 473. oldal  PDF  |  MathML 
Témakör(ök): Feladat, Számelrendezések, Teljes indukció módszere, Logikai feladatok
Hivatkozás(ok):Feladatok: 2017/február: B.4855

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

 
Megoldás. Legyen k sora a táblázatnak. Bebizonyítom, hogy ha a táblázatnak van olyan oszlopa, amelyben pontosan n<k darab 0 vagy pontosan n darab 1-es van, akkor olyan oszlopa is létezik, amelyben kevesebb mint n darab, de legalább 1 darab 0 vagy kevesebb mint n darab, de legalább 1 darab 1-es van.
Legyen például az A oszlopban n darab 0 és k-n darab 1-es. Válasszunk ki kettőt ebből az A-ban nullás n sorból; legyenek ezek a c-edik és a d-edik sorok. Mivel a táblázat sorai mind különbözőek, lesz olyan oszlop, amelyikben különböző értéket vesz fel e két sor cellája ‐ legyen ez a B oszlop.
Ha van kettő olyan sor ‐ mondjuk az e-edik és az f-edik ‐ amelyek A oszlopában 1-es, a B-be eső oszlopában pedig két különböző szám áll, akkor a c-edik, d-edik, e-edik és f-edik sorok, valamint az A és B oszlopok által meghatározott 4×2-es résztáblázatban nincs két azonos sor. Ezért a B oszlopban azonos értéket vesz fel ez a k-n sor. Így a B oszlopban 0-ból vagy 1-ből legalább k-n+1 van, ezért a másik számból legfeljebb n-1, de legalább 1 darab. A bizonyított állítást ismételten alkalmazva az A helyett a B oszlopra stb., eljutunk addig, hogy az egyik oszlopban az egyik szám pontosan egyszer fordul elő.
A bizonyított állítást csak akkor nem tudnánk alkalmazni, ha feltételei a táblázat egyik oszlopára sem teljesülnek. Ez pontosan azt jelentené, hogy mindegyik oszlop vagy csupa 0, vagy csupa 1 elemből áll, azaz a táblázat valamennyi sora azonos.