Zadanie

Dante sa už-už chcel prevaliť na druhý bok, keď mu zazvonil telefón. „Mačka spadla do vírivky. Nasoľ chechtáky. Dnes v noci v Central Parku,“ zavrčal hlas jeho partnera Krumpľa. Dante zavrčal a zložil.

V tú noc sa chystala prestrelka medzi všetkými gangami v Central Parku a Dante to neplánoval nechať tak. V časoch detektíva Danteho si Hippies presadili svoje a Central Park bol prerobený do tvaru nekonečnej štvorčekovej siete, kde uprostred každého vrchola stál strom – považujeme ho za bod. Všetci členovia gangov – dokopy \(2020\) členov – sa rozostavili po sieti. Každý si chce vybrať jeden strom, zoťať ho a postaviť sa na jeho peň. Keďže však nikto nechce, aby mu nepriatelia – alebo hoci aj priatelia – zmizli z dohľadu, chcú sa rozostaviť tak, aby úsečka spájajúca ľubovoľných dvoch gangsterov neprechádzala žiadnym stromom ani pňom s iným gangstrom. Dante sa poškriabal na hlave a zamyslel sa: existuje vôbec také rozostavenie? Svoje tvrdenie zdôvodnite.

Po chvíli úvah (a prípadného hrania sa so štvorčekovým papierom alebo GeoGebrou) zrejme dôjdeme k záveru, že obsadiť viac ako štyri vrcholy je pomerne náročné. Vieme, že medzi ľubovoľnými dvoma obsadenými vrcholmi nemôže byť iný vrchol, či už obsadený, alebo nie.

Každý vrchol môžeme označiť \(x\)-ovou a \(y\)-ovou celočíselnou súradnicou, ktoré nám jasne určia jeho pozíciu. Zamyslime sa teda, čo pomocou súradníc vieme zistiť. Bude nás zaujímať najmä, kedy sa ľudia budú vidieť.

Pre jednoduchosť uvažujme, čo vidí človek, ktorý obsadil strom vo vrchole \(A=[0,0]\). Na aké vrcholy dovidí? Vieme, že ak sa pozerá nejakým smerom a uvidí vrchol (obsadený alebo nie), tým istým smerom už žiaden ďalší vrchol nevidí. Súradnice ďalších vrcholov týmto istým smerom musia byť násobkom súradníc najbližšieho vrchola. Napríklad ak vidí vrchol \([4, 5]\), nebude už vidieť vrcholy \([8, 10]\), \([12, 15]\) a tak ďalej. Môžeme teda povedať, že ak vieme súradnice nejakého bodu zapísať ako \([kx, ky]\), tento vrchol neuvidíme cez vrchol \([x, y]\). To znamená, že človek vo vrchole \([0, 0]\) nebude vidieť tie vrcholy, ktorých súradnice sú súdeliteľné.

Kedy sa dvaja ľudia vidia? Vo všeobecnosti nás bude zaujímať ich vzájomná poloha, teda rozdiel ich \(x\)-ových a \(y\)-ových súradníc. Presnejšie, ak je človek \(A\) vo vrchole \([a_x, a_y]\) a človek \(B\) vo vrchole \([b_x, b_y]\), tak sa pozrieme na rozdiely \(d_x = b_x - a_x\) a \(d_y = b_y - a_y\). Polohu človeka \(B\) si vieme vyjadriť aj ako \([a_x + d_x, a_y + d_y]\). Čo ak by čísla \(d_x\) a \(d_y\) mali spoločného deliteľa \(k > 1\), teda by platilo \(d_x = kx\) a \(d_y = ky\)? Potom by sa medzi ľuďmi \(A\) a \(B\) nachádzal vrchol \([a_x + x, a_y + y]\), cez ktorý by na seba nevideli. Preto musia byť rozdiely \(d_x\) a \(d_y\) nesúdeliteľné.1

Poďme teda ukázať, že \(2020\) ľudí nevieme rozmiestniť tak, aby na seba všetci videli. Ukážeme, že pri akomkoľvek rozmiestnení nájdeme dvoch ľudí, ktorí na seba nevidia. To znamená, že rozdiely ich súradníc sú súdeliteľné. Najjednoduchšie by bolo nájsť také rozdiely súradníc, ktoré by boli deliteľné dvomi. Zamyslime sa, kedy nastane takýto prípad. Nastane, keď majú obe \(x\)-ové súradnice rovnakú paritu, podobne aj \(y\)-ové (nie nutne tú istú ako \(x\)-ové). Každý bod má dve súradnice a každá môže byť párna alebo nepárna. To znamená, že máme štyri typy vrcholov v závislosti na ich parite. Ak obsadíme \(2020\) vrcholov, každý z nich vieme priradiť do niektorej z týchto štyroch skupín. Keďže bodov je viac než skupín, v aspoň jednej skupine musia byť aspoň dvaja ľudia.2 Títo dvaja majú rozdiely súradníc párne, teda na seba nevidia – presne v strede medzi nimi sa nachádza vrchol (či už so stromom alebo s človekom). Týmto sme dokázali, že neexistuje také rozostavenie, aby na seba všetci videli.

  1. Môžete si premyslieť, že v prípade, že sú \(d_x\) a \(d_y\) nesúdeliteľné, tak \(A\) a \(B\) naozaj na seba vidia. Z našich úvah to ešte nevyplýva. Avšak keďže ukazujeme neexistenciu rozostavania, tento fakt nepotrebujeme.↩︎

  2. Toto tvrdenie má aj svoj názov. Volá sa Dirichletov princíp a vo všeobecnosti hovorí, že ak máme nejaké predmety podelené do skupín a predmetov je viac ako skupín, tak existuje skupina s aspoň dvomi predmetmi. Takéto úvahy a cielené rozdeľovanie predmetov do skupín vie byť užitočné pri mnohých, aj náročnejších úlohách tohto typu. Záujemcom odporúčame si prečítať viac v Zbierke KMS na str. 67.↩︎

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