Sākums

LV.SOL.2013.12.4   lv

Lauka forma ir taisnstūris ar malu garumiem \(4\ \mathrm{km}\) un \(6\ \mathrm{km}\). Tajā ir uzceltas \(5\) mājas. Pierādīt, ka, neatkarīgi no māju izvietojuma, varēs uzbūvēt ceļus, pa kuriem no jebkuras mājas var nokļūt uz jebkuru citu un ceļu kopējais garums nepārsniegs \(15\ \mathrm{km}\).

Hide solution

Atrisinājums

Apskatām nogriezni, kas savieno taisnstūra to malu, kuru garums ir \(4\) km, viduspunktus. Gadījumā, ja kādas mājas attālums līdz šim nogrieznim nepārsniedz \(1\) km, tad, uzbūvējot ceļu pa šo nogriezni, un no katras mājas īsāko ceļu līdz šim nogrieznim, kopējais izbūvēto ceļu garums nepārsniegs \(6+1+4\cdot2=15\) km. Ja attālums no katras mājas līdz novilktajam nogrieznim pārsniedz \(1\) km, tad nogriezni pārbīdīsim par \(1\) km uz to pusi, kur ir vairāk māju (nogriežņa vienā pusē būs vismaz \(3\) mājas). Uzbūvējot no katras mājas īsāko nogriezni līdz šim nogrieznim, kopējais garums nepārsniegs \(6+3\cdot1+2\cdot3=15\) km.