9. príklad - Vzorové riešenie
Zadanie
Pierre a Mária majú 10 papierikov očíslovaných od 1 do 10. Dokážte, že keď si ich ľubovoľne rozdelia tak, že každý si zoberie 5 kartičiek, tak aspoň jeden z nich bude vedieť zo svojich čísel vybrať tri, ktoré tvoria aritmetickú postupnosť.
Poznámka: Tri čísla a<b<c tvoria aritmetickú postupnosť, ak susedné členy majú rovnaký rozdiel, teda b-a=c-b (napríklad 1, 2, 3 alebo 2, 5, 8).Vzorové riešenie
Budeme dokazovať toto tvrdenie sporom. Pokúsime sa teda kartičky rozdeliť tak, aby ani Pierre ani Mária postupnosť nemali, a zistíme, že sa to nedá.
Keďže rozdeľujeme všetky kartičky, tak každý bude mať na konci 5 kartičiek. Preto ak ukážeme, že jeden z nich nemôže mať nejakú kartičku, určite ju musí mať ten druhý.
Môžeme si všimnúť, že ak by jeden hráč mal 3 a 5, tak by vytvoril postupnosť s: (1, 3, 5), aj s 4 (3, 4, 5) aj so 7 (3, 5, 7), teda druhý hráč musí mať 1, 4 aj 7. To ale nefunguje, lebo 1, 4, 7 je tiež aritmetická postupnosť, a teda ak ju nechceme vytvoriť, žiaden hráč nemôže mať aj 3 aj 5.
To isté vieme povedať o dvojiciach 4 a 6, 5 a 7, 6 a 8:
- 4 a 6 nemôžu byť s 2, 5 ani 8, ktoré potom tvoria postupnosť u druhého hráča
- 5 a 7 nemôžu byť s 3, 6 ani 9, ktoré tvoria postupnosť
- 6 a 8 nemôžu byť s 4, 7 ani 10, ktoré tvoria postupnosť
Teda dvojice 3 a 5, 4 a 6, 5 a 7 ani 6 a 8 nemôže mať jeden hráč. To znamená, že ten hráč, ktorý bude mať 5 nebude mať 3 ani 7 - bude ich musieť mať druhý hráč. Podobne ten čo bude mať 6 nemôže mať 4 ani 8, a teda má obe druhý hráč.
Pozrime sa teraz na možnosti, ako môžu byť rozdelené dvojice 3 a 7, 4 a 8. Najprv na možnosť, kde má všetky tieto čísla jeden hráč, a neskôr na druhú možnosť kde 3, 7 má jeden a 4, 8 má druhý.
Ak má jeden z nich 3, 4, 7, 8, tak nemôže mať:
- 1 (1, 4, 7 je postupnosť)
- 2 (2, 3, 4 je postupnosť)
- 5 (3, 4, 5 je postupnosť)
- 6 (6, 7, 8 je postupnosť)
- 9 (7, 8, 9 je postupnosť)
- 10 (4, 7, 10 je postupnosť)
To boli ale všetky zvyšné kartičky, a teda nech má hocijakú štvrtú kartičku, vytvorí postupnosť.
Vieme preto, že jeden hráč musí mať 7, 3 a druhý 8, 4. Poďme to skúsiť.
Ten kto má 7, 3 (nazveme ho prvý) nemôže mať 5, lebo 3, 5, 7 je postupnosť. Druhý teda musí mať 5, a potom nemôže mať 6, lebo už má 4, 8 a 4, 5, 6 by bola postupnosť. Teda prvý musí mať 6, preto nemôže mať 9, lebo by to vznikla postupnosť 3, 6, 9. Ak druhý musí mať 9, tak nemôže mať 10, lebo 8, 9, 10 je postupnosť. Prvý musí mať 10, a preto nemôže mať 2, lebo 2, 6 ,10 je postupnosť. Ak ale druhý musí mať 2 dostane postupnosť 2, 5, 8, a teda sa postupnosti nedá vyhnúť ani tu.
Odpoveď: Zistili sme, že vo všetkých možnostiach nám vznikne postupnosť, ktorú budeme vedieť vybrať z kartičiek jedného hráča.