Sākums

LV.SOL.2004.7.5   lv

Karnevāla zālē karājas \(6\) lampas. Dažas no tām savienotas ar lentām (katra lenta savieno \(2\) lampas un nepieskaras citām). Pavisam ir vismaz \(7\) lentas. No katrām trim lampām vismaz divas savienotas ar lentu; katras \(2\) lampas savieno augstākais viena lenta.

Pierādīt: ir tādas trīs lampas, kas visas savienotas ar lentām cita ar citu.

Hide solution

Atrisinājums

Ja katrai lampai būtu piestiprināti ne vairāk kā \(2\) lentu gali, tad lentu būtu ne vairāk kā \(\frac{6\cdot 2}{2}=6\) – pretruna. Tātad ir lampa \(A\), kurai piestiprinātas (vismaz) \(3\) lentas; pieņemsim, ka tās iet uz lampām \(x\), \(y\), \(z\). Vismaz divas no lampām \(x\), \(y\), \(z\) savienotas ar lentu; tās kopā ar \(A\) veido meklējamo trijnieku.