|
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 sora a táblázatnak. Bebizonyítom, hogy ha a táblázatnak van olyan oszlopa, amelyben pontosan darab vagy pontosan darab -es van, akkor olyan oszlopa is létezik, amelyben kevesebb mint darab, de legalább 1 darab vagy kevesebb mint darab, de legalább 1 darab -es van. Legyen például az oszlopban darab és darab -es. Válasszunk ki kettőt ebből az -ban nullás sorból; legyenek ezek a -edik és a -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 oszlop. Ha van kettő olyan sor ‐ mondjuk az -edik és az -edik ‐ amelyek oszlopában -es, a -be eső oszlopában pedig két különböző szám áll, akkor a -edik, -edik, -edik és -edik sorok, valamint az és oszlopok által meghatározott -es résztáblázatban nincs két azonos sor. Ezért a oszlopban azonos értéket vesz fel ez a sor. Így a oszlopban 0-ból vagy 1-ből legalább van, ezért a másik számból legfeljebb , de legalább 1 darab. A bizonyított állítást ismételten alkalmazva az helyett a 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. |
|