Sākums

LV.SOL.2005.7.5   lv

Futbola turnīrā piedalījās vismaz \(5\) komandas; katra ar katru citu spēlēja tieši vienu reizi. Jebkurām \(3\) komandām \(A\), \(B\), \(C\) ir spēkā sekojošais: ja \(A\) nezaudēja pret \(B\) un \(B\) nezaudēja pret \(C\), tad \(C\) nezaudēja pret \(A\). Pierādiet, ka visas spēles turnīrā beidzās neizšķirti.

Hide solution

Atrisinājums

To, ka \(X\) uzvarējusi pret \(Y\), apzīmēsim ar \(X\to Y\); to, ka \(X\) un \(Y\) nospēlējušas neizšķirti, apzīmēsim ar \(X\sim Y\); to, ka \(X\) nezaudēja pret \(Y\), apzīmēsim ar \(X\nleftarrow Y\).

Lemma. Nevienai komandai nav vairāk par \(1\) uzvaru un nav vairāk par \(1\) zaudējumu.

Pierādījums. Pieņemam, ka \(X\to Y\) un \(X\to Z\). Vai nu \(Y\nleftarrow Z\), vai \(Z\nleftarrow Y\). Varam pieņemt, ka \(Y\nleftarrow Z\). Tad \(X\nleftarrow Y\) un \(Y\nleftarrow Z\), tāpēc jābūt \(Z\nleftarrow X\) – pretruna.

Lemmas otro daļu pierāda līdzīgi.

Pieņemam pretējo tam, kas jāpierāda: eksistē tādas komandas \(A\) un \(B\), ka \(A\to B\). Ir vēl vismaz \(3\) citas komandas \(X\), \(Y\), \(Z\). Saskaņā ar lemmu ne pret vienu no tām \(A\) nav uzvarējusi un augstākais pret vienu no tām \(A\) ir zaudējusi. Tāpēc ar vismaz divām no tām \(A\) spēlējusi neizšķirti. Varam pieņemt, ka \(A\sim X\) un \(A\sim Y\). Tā kā \(X\nleftarrow A\) un \(A\nleftarrow B\), tad \(B\nleftarrow X\); līdzīgi \(B\nleftarrow Y\). Ar vismaz vienu no \(X\) un \(Y\) \(B\) nospēlēja neizšķirti; pieņemsim, ka \(B\sim X\). Iegūstam \(A\nleftarrow X\), \(X\nleftarrow B\), \(B\leftarrow A\) – pretruna ar uzdevuma nosacījumiem.