LV.NOL.2014.7.5 lv
Pilsētas ielu tīkls veido kvadrātveida režģi, kas sastāv no \(8 \times 8\) vienādām kvadrātiskām rūtiņām. Katrā no \(81\) rūtiņu stūriem ir autobusu pietura; citu pieturu nav. Kādu vismazāko skaitu autobusa maršrutu jāievieš, lai no katras pieturas varētu aizbraukt uz katru citu, izdarot ne vairāk kā vienu pārsēšanos? Pa katru maršrutu autobuss kursē abos virzienos; katrs maršruts drīkst saturēt augstākais vienu pagriezienu.
Atrisinājums
Katrs maršruts iet pa augstākais vienu horizontāli un vienu vertikāli. Ja maršrutu skaits nepārsniedz \(8\), tad atrastos vertikāle un horizontāle, pa kurām neiet neviens maršruts; uz šo ielu krustpunktu nevarētu aizbraukt.
Ar \(9\) maršrutiem pietiek. Piemēram, var ņemt visus maršrutus, katrs no kuriem satur pilnībā vienu vertikāli un visu augšējās horizontāles daļu pa labi no šīs vertikāles (skat. A4.zīm.).
