Zadanie

Keď Caligula s Krtkom sedeli pri večeri, tak si Krtko smutne povzdychol, ako mu chýba počítač, že by si rád spravil spreadsheet. Na to sa Caligula podivil, že také on v živote nevidel, tak sa Krtko hneď podujal mu vysvetľovať, čo to je. Caligulu to úplne nadchlo, takže sa rozhodol, že také nutne potrebuje. Tak Krtko zapojil všetky šedé bunky mozgové a vymyslel prístroj, na ktorom je navinutý papyrus tak, aby keď sa Caligula dostane na koniec tabuľky, mu to ďalej zobrazilo začiatok tabuľky. Krtkova tabuľka má \(2021\) riadkov a dokáže naraz zobraziť len \(90\) riadkov. Teda na začiatku zobrazuje len riadky \(1\) až \(90\). Prístroj tiež obsahuje dve tlačidlá – „hore“ a „dole“ – ktorými sa vždy vie posúvať o \(3\) riadky hore alebo dole1. Ak teda na začiatku stlačí tlačidlo „hore“, bude vidieť riadky \(2019\) až \(2021\) navrchu a potom riadky \(1\) až \(87\). Caligula si náhodne zvolil dvojicu rôznych riadkov. Aká je pravdepodobnosť, že ich vie zobraziť na obrazovke naraz? Aká by bola táto pravdepodobnosť pre tabuľku s \(2022\) riadkami?

  1. Teda ak stlačí „hore“, navrchu sa mu zobrazia tri predtým skryté riadky a spodné tri zmiznú. Pre „dole“ naopak.↩︎

Pozrime sa, ktoré kombinácie riadkov dokáže Krtkova tabuľka zobraziť. Zobrazenú časť tabuľky nazvime okno. To, ktoré riadky sú zobrazené, je jednoznačne dané najvrchnejším zobrazeným riadkom – zobrazený je tento riadok a \(89\) nasledujúcich riadkov. Takže otázkou je, ktoré riadky vieme dostať na vrch okna pomocou tlačidiel hore a dole. Na začiatku je najvrchnejší riadok \(1\). Postupným stláčaním tlačidla dole sa vždy posunieme o \(3\) riadky, takže najvrchnejšími riadkami budú postupne \(1,\ 4,\ 7,\ \dots\). Po \(k\) stlačeniach tlačidla dole sa posunieme o \(3k\) riadkov, takže najvrchnejším riadkom bude riadok \(3k+1\). Takto dostaneme všetky riadky zo zvyškom \(1\) po delení \(3\). Teraz sa chceme pozrieť, čo sa stane, keď prídeme na koniec tabuľky a „pretečieme“ znovu na začiatok. Celkový počet riadkov \(2021\) má zvyšok \(2\) po delení \(3\), takže riadok \(2020\) vieme dostať na vrch okna. Ďalší riadok by bol \(2020+3=2023\), ale uvedomíme si, že riadky \(2022,\ 2023\) sú už vlastne riadky \(1,\ 2\), takže sme na vrch dostali riadok \(2\). Ďalším opakovaním posunu dole dostaneme na vrch všetky riadky, ktoré majú zvyšok \(2\) po delení \(3\). Posledný taký riadok bude \(2021\) a ďalší riadok \(2021+3=2024\) je už vlastne riadok \(3\). Od neho ďalej dostaneme navrch dokonca aj všetky riadky, ktoré majú zvyšok \(0\) modulo \(3\). Takže v skutočnosti vieme dostať na vrch okna každý jeden riadok.

Teraz potrebujeme nejako uchopiť skutočnosť, že Caligula si volí náhodnú dvojicu riadkov. Môžeme si to predstaviť, že Caligula si náhodne zvolí jeden riadok a potom zo zvyšných \(2020\) riadkov si náhodne zvolí druhý riadok. Takto vie Caligula zvoliť každú dvojicu riadkov práve dvomi spôsobmi, takže každá dvojica riadkov má rovnakú pravdepodobnosť. Povedzme, že prvý zvolený riadok bol riadok \(n\). Zamyslime sa, ktorý riadok mohol Caligula zvoliť ako druhý, aby sa dal zobraziť spolu s riadkom \(n\). Takéto riadky nazvime zobraziteľné spolu s \(n\). Riadok \(n\) vieme dostať na vrch okna, takže \(89\) riadkov, ktoré nasledujú pod ním, sú zobraziteľné. Takisto riadok \(n\) vieme dostať na spodok okna, stačí dostať riadok \(n-89\) 1 navrch, takže \(89\) riadkov, ktoré sa nachádzajú nad ním, sú tiež zobraziteľné. Rozmyslite si, že žiadne iné riadky nie sú zobraziteľné spolu s \(n\), lebo sú príliš ďaleko od riadku \(n\). To máme spolu \(89+89=178\) zobraziteľných riadkov, pričom Caligula vyberá druhý riadok z \(2020\) možných. Preto pravdepodobnosť, že vybratá dvojica riadkov bude zobraziteľná, je \[p_n=\frac{178}{2020}=\frac{89}{1010},\] za podmienky, že prvý riadok bol vybratý riadok \(n\). Keďže však táto pravdepodobnosť je rovnaká pre všetky \(n\), aj celková pravdepodobnosť, že vieme zobraziť dvojicu vybratých riadkov naraz je \[\frac{89}{1010}.\]

Tabuľka s \(2022\) riadkami

Tak ako v predchádzajúcom prípade, na vrch okna vieme dostať všetky riadky zo zvyškom \(1\) modulo \(3\), keďže začíname na \(1\). Avšak teraz sú to jediné riadky, ktoré vieme dostať na vrch, pretože celkový počet riadkov \(2022\) je deliteľný \(3\). Naozaj, keď sme na riadku \(n\) a riadok \(n+3\) by už bol mimo tabuľky, tak krokom dole sa v skutočnosti posunieme na \(n+3-2022\), čo má stále rovnaký zvyšok modulo \(3\) ako \(n\). Podobne ak by \(n-3\) bol \(0\) alebo záporný, takže zvyšok vrchného riadku sa vždy zachováva.

Rozdeľme si tabuľku na trojice po sebe idúcich riadkov \(\{1, 2, 3 \},\ \{ 4, 5, 6 \},\ \dots, \{ 2020, 2021, 2022 \}\). Počet riadkov v okne (\(90\)) je tiež deliteľný tromi, takže v okne vždy máme zobrazených \(30\) celých trojíc, nikdy sa nestane, že by niektorá trojica bola zobrazená len čiastočne. Taktiež každú trojicu vieme dostať tak, že bude tvoriť vrchné tri riadky okna resp. spodné tri riadky. Povedzme, že Caligula zvolil ako prvý riadok \(n\). Tento riadok vieme dostať najvyššie tak, že jeho trojicu dáme na vrch tabuľky. Takto s ním vieme zobraziť \(29\) nasledujúcich trojíc. Najnižie bude, keď jeho trojica bude na spodku tabuľky, vtedy s ním zobrazíme \(29\) predchádzajúcich trojíc a v oboch prípadoch ešte samozrejme zobrazíme aj dva riadky z jeho trojice. To je spolu \(3 \cdot 29 + 3 \cdot 29 + 2 = 176\) zobraziteľných riadkov. Caligula druhý riadok vyberá spomedzi \(2021\) riadkov, takže pravdepodobnosť, že vyberie zobraziteľný, je \[\frac{176}{2021}.\]

Všimnime si ešte, že menší trik s rozdelením tabuľky na trojice, ktorý sme použili, nebol nutný. Mohli sme rozobrať \(3\) prípady podľa toho, aký zvyšok modulo \(3\) má prvý Caligulov vybratý riadok \(n\). Počty zobraziteľných riadkov pod ním a nad ním by boli síce v jednotlivých prípadoch rozdielne, ale celkový počet by bol vždy rovnaký, a to \(176\). My sme sa však šikovne vyhli rozoberaniu troch prípadov.

  1. Používame značenie, kde riadky \(0,\ -1,\ -2, \dots\) sú totožné s \(2021,\ 2020,\ 2019, \dots\) a riadky \(2022,\ 2023, \dots\) sú totožné s \(1,\ 2, \dots\) atď.↩

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ť.