Uzdevums

LV.NOL.2011.5.3 lv

Četrdesmitvietīgs autobuss veica reisu no pilsētas \(A\) uz pilsētu \(G\), pa ceļam pieturot pilsētās \(B, C, D, E\) un \(F\) (iespējams, citā secībā). Katrā pilsētā iekāpušo un/vai izkāpušo pasažieru skaits parādīts tabulā:

Pilsēta	Izkāpa	Iekāpa
\(A\)	-	\(34\)
\(B\)	\(23\)	\(30\)
\(C\)	\(28\)	\(29\)
\(D\)	\(21\)	\(32\)
\(E\)	\(26\)	\(14\)
\(F\)	\(35\)	\(22\)
\(G\)	\(28\)	-

Noteikt, kādā secībā tika apmeklētas pilsētas \(B, C, D, E\) un \(F\), ja zināms, ka nevienā brīdī autobusā netika pārvadāts vairāk pasažieru kā autobusā ir vietu!

Hide solution

Atrisinājums

Ievērosim trīs nosacījumus, kuriem jābūt spēkā visu ceļojuma laiku: autobusā nevienā brīdī nedrīkst būt vairāk par \(40\) pasažieriem, nevienā pieturā no autobusa nevar izkāpt vairāk pasažieru, nekā ir autobusā un katru pilsētu var apmeklēt ne vairāk kā vienreiz.

Pirmā pilsēta ir \(A\) un, izbraucot no tās, autobusā ir \(34\) pasažieri, bet pēdējā ir \(G\), iebraucot tajā autobusā bija \(28\) pasažieri.

Otrā pilsēta var būt \(C\), tad pēc maršruta \(AC\) nobraukšanas autobusā ir \(35\) pasažieri (apzīmēsim to \(AC\) (\(35\))) vai arī otrā pilsēta var būt \(E\), tātad \(AE\) (\(22\)).

Analizēsim iespējamos šo maršrutu turpinājumus:

\(ACE\) (\(23\)) \(\rightarrow\) \(ACEB\) (\(30\)) vai \(ACED\) (\(34\)), taču neviens no šiem maršrutiem nav tālāk turpināms.
\(ACF\) (\(22\)) \(\rightarrow\) \(ACFD\) (\(33\)) \(\rightarrow\) \(ACFDB\) (\(40\)) \(\rightarrow\) \(ACFDBE\) (\(28\)) \(\rightarrow\) \(ACFDBEG\) (\(0\))
\(ACF\) (\(22\)) \(\rightarrow\) \(ACFD\) (\(33\)) \(\rightarrow\) \(ACFDE\) (\(21\))- maršruts nav turpināms.
\(AED\) (\(33\)) \(\rightarrow\) \(AEDB\) (\(40\)) \(\rightarrow\) \(AEDBF\) (\(27\))- maršruts nav turpināms.
\(AED\) (\(33\)) \(\rightarrow\) \(AEDC\) (\(34\))- maršruts nav turpināms.

Tātad vienīgais maršruts, kas apmierina visus noteikumus, ir \(ACFDBEG\).