kms - fórum o príkladoch

3. príklad 1. letnej série 2016/2017

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čí.

Naspäť na príklady | Napíš príspevok