Zadanie
Centrum New Yorku sa skladá z \(n\) severojužných a \(n\) západovýchodných ciest, ktoré tvoria štvorčekovú sieť \((n-1)\times(n-1)\) štvorcových blokov. V každej z \(n^2\) križovatiek sa nachádza autobusová zastávka. Po uliciach premávajú autobusové linky so zastávkami vo všetkých križovatkách. Trasa každej linky obsahuje najviac jednu zákrutu a je obojsmerná. Koľko najmenej liniek je potrebných na to, aby sa dalo medzi ľubovoľnými dvomi zastávkami cestovať na najviac jeden prestup? Výsledok určte v závislosti od celého čísla \(n \ge 2\). Nezabudnite zdôvodniť, prečo menej liniek nestačí.
Riešenie tejto úlohy a úloh podobného typu zvyčajne pozostáva z dvoch častí: potrebujeme ukázať, že pre náš výsledok vieme nájsť riešenie a tiež nájsť a popísať dôvod, prečo to nevieme spraviť lepšie.
Začať môžeme napríklad tým, že zistíme, koľko najmenej liniek je potrebných k tomu, aby bola každá zastávka obslúžená. Vieme, že štvorčeková sieť centra New Yorku sa skladá z \(n\) riadkov a \(n\) stĺpcov. Každá linka môže mať maximálne \(1\) zákrutu, teda sa nemôže stať, aby jedna linka prešla v dvoch rôznych riadkoch alebo stĺpcoch aspoň dve políčka. Môže prejsť jeden celý riadok/stĺpec, ale z nejakého iného riadka/stĺpca vie obsadiť maximálne jedno políčko. Čo z toho vyplýva? Ak by sme chceli \(n\) riadkov/stĺpcov obsadiť menej ako \(n\) linkami, nejaký riadok/stĺpec by sme nutne nemohli obsadiť celý, pretože bude existovať riadok/stĺpec, pre ktorý každá linka obsadila maximálne jedno políčko, teda celkovo maximálne \(n-1\) políčok. Preto potrebujeme aspoň \(n\) liniek.
Teraz ešte potrebujeme ukázať, že pre \(n\) liniek naozaj zadanie splniť vieme. Ak chceme, aby sa medzi ľubovoľnými dvomi zastávkami dalo cestovať na jeden prestup, potom musí mať každá dvojica liniek nejakú spoločnú zastávku. Ak by nejaké dve linky \(A\) a \(B\) nemali spoločnú zastávku (využijeme fakt, že linku zrušiť nemôžeme, pretože pre \(n-1\) liniek to nejde, z čoho vyplýva, že na každej linke existuje zastávka, na ktorej jazdí len jedna linka, inak by sme ju mohli zrušiť), potom by sa zo zastávky, na ktorej jazdí len linka \(A\) nedalo dostať do zastávky, na ktorej jazdí len linka \(B\) na jeden prestup. Ako jedno z jednoduchších riešení sa ukazuje možnosť, že by v centre New Yorku bola jedna hlavná stanica, kde by stáli všetky linky. Potom by stačilo, aby cestujúci prestúpil na nej a na jeden prestup sa tak dostane hocikam. Ako by takáto štvorčeková sieť mohla vyzerať?
Ako hlavnú stanicu si určíme bod, ktorý je úplne najviac vpravo dole. Linku \(1\) zavedieme z ľavého horného rohu cez ľavý dolný roh a potom do pravého dolného rohu, spravíme tak linku podobnú písmenu L. Následne linka \(2\) začne zo zastávky o jedna vpravo od začiatku linky \(1\), opäť ide najviac na juh, ako môže, a potom na západ až do hlavnej stanice. Takto skonštruujeme linky od \(1\) až po \(n\), kde linka \(n\) bude už len severojužná linka v poslednom stĺpci. Z toho, ako sme si linky a hlavnú stanicu zadefinovali, je jasné, že naša sieť bude spĺňať zadanie a teda je príklad vyriešený.
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ť.