Zadanie
Keď vedúci konečne vošli do vlaku, zistili, že ich vozeň má \(100\) sedadiel očíslovaných číslami \(1\) až \(100\), ktoré sú rozmiestnené do mriežky \(10 \times 10\). Dokážte, že Mati a Danko si vedia sadnúť na \(2\) susediace sedadlá (vedľa seba alebo tesne za sebou), ktorých čísla majú rozdiel aspoň \(6\), bez ohľadu na to, ako sú sedadlá očíslované.
Zamyslime sa na začiatok nad tým, prečo by malo platiť, že si Mati a Danko vedia sadnúť na \(2\) susediace sedadlá, ktorých čísla sa líšia aspoň o \(6\). Čo by muselo platiť, ak by to tak nebolo? Potom by všetky dvojice susediacich sedadiel museli mať čísla s rozdielom nanajvýš \(5\), čo je veľmi málo. Intuitívne, s takýmito malými rozdielmi by mohol byť problém vojsť do vozňa sedadlá s veľmi odlišnými číslami – najextrémnejší prípad sú sedadlá \(1\) a \(100\). Zrejme by museli byť ďaleko od seba, ak by sa to vôbec dalo.
Poďme teda tvrdenie dokázať poriadne. Použijeme techniku nazývanú dôkaz sporom. Budeme predpokladať opak dokazovaného tvrdenia, teda že Mati a Danko si nevedia sadnúť na dve sedadlá podľa zadania, a dospejeme k niečomu, čo zrejme nemôže byť pravda. To bude znamenať, že náš predpoklad bol nepravdivý, a teda Mati a Danko si vedia sadnúť na vhodné sedadlá.
Nech teda každé dve susedné sedadlá majú rozdiel čísel nanajvýš \(5\). Pozrime sa na polohu sedadla \(1\), polohu sedadla \(100\) a cestu medzi nimi. Cestou rozumieme postupnosť sedadiel od jedného k druhému, kde po sebe idúce sedadlá na ceste sú vedľa seba alebo tesne za sebou. Uvážime ľubovoľnú z najkratších ciest medzi sedadlami \(1\) a \(100\). Jedna z týchto ciest vyzerá tak, že najskôr ide o niekoľko sedadiel (možno nula) v jednom smere a potom o niekoľko sedadiel (možno nula) v kolmom smere.
Je jednoduché si rozmyslieť, že sedadlá \(1\) a \(100\) budú od seba najďalej, ak budú v protiľahlých rohoch vozňa. Cesta medzi protiľahlými rohmi obsahuje \(19\) sedadiel vrátane krajných, cesta medzi sedadlami \(1\) a \(100\) má teda takúto dĺžku alebo menšiu.
Označme si čísla sedadiel na tejto ceste ako \(a_1 = 1, a_2, a_3, \dots, a_n=100\), pričom \(n \leq 19\). Z nášho predpokladu plynie, že \[\begin{align} a_2 &\leq a_1 + 5 = 6 = 1 + 1 \cdot 5, \\ a_3 &\leq a_2 + 5 \leq 11 = 1 + 2 \cdot 5, \\ a_4 &\leq a_3 + 5 \leq 16 = 1 + 3 \cdot 5, \\ &\vdots \\ a_n &\leq 1 + (n-1) \cdot 5 \leq 1 + 18\cdot 5 = 91.\end{align}\]
Zjednodušene povedané, cesta začína sedadlom \(1\) a obsahuje najviac \(18\) krokov na ďalšie sedadlo, pričom každý krok zvýši číslo sedadla najviac o \(5\). Z toho plynie, že posledné sedadlo má číslo najviac \(1 + 18\cdot 5 = 91\). Jeho číslo však má byť rovné \(100\). Došli sme teda ku sporu s naším predpokladom, že rozdiel čísel každých dvoch susedných sedadiel je najviac \(5\).
To znamená, že existujú dve susedné sedadlá, ktorých rozdiel čísel je aspoň \(6\) a Mati s Dankom si na ne vedia sadnúť.
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.