Sākums

LV.AMO.2017.12.4   lv

Astoņi tenisisti piedalās turnīrā, kurā katram ar katru paredzēts izspēlēt vienu spēli. Turnīra laikā ir iestājies tāds brīdis, kad katrs tenisists ir nospēlējis tieši trīs spēles. Pierādīt, ka visus astoņus tenisistus var sadalīt četros pāros tā, ka nevienā pārī tenisisti vēl nav savā starpā nospēlējuši turnīrā paredzēto spēli!

Hide solution

Atrisinājums-1

Izveidosim grafu, kur virsotnes (punkti) ir tenisisti, bet šķautne (līnija) divas virsotnes saista tad un tikai tad, ja atbilstošie tenisisti turnīrā vēl savu spēli nav izspēlējuši. Tā kā katram tenisistam pavisam jāizspēlē septiņas spēles, bet izspēlētas ir trīs, tad katra virsotne ir tieši četru šķautņu galapunkts (skat. 38.att.).

Pierādīsim, ka šajā grafā eksistē Hamiltona cikls, tas ir, ceļš, kas iet pa tā šķautnēm, katrā virsotnē iegriežoties tieši vienu reizi, un beigās atgriežas sākotnējā virsotnē.

Atradīsim šajā grafā garāko ceļu, tas ir, garāko virsotņu virkni \(v_{1}v_{2} \ldots v_{k}\), tādu, ka \(v_{i}\) un \(v_{i+1}\) ir saistītas. Parādīsim, ka šo ceļu var pārtaisīt par ciklu. Visas četras šķautnes, kas iziet no virsotnes \(v_{1}\) iet uz kādu no virsotnēm \(v_{2}, \ldots, v_{k}\), jo, ja tās ietu uz kādu virsotni, kas neietilpst garākajā ceļā, tad šo ceļu varētu pagarināt. Tā kā \(k \leq 8\), tad no tā varam secināt, ka starp virsotnēm \(v_{2}, \ldots, v_{k}\) ir ne vairāk kā \(3\), kas nav saistītas ar \(v_{1}\). Tas pats ir spēkā arī virsotnei \(v_{k}\), visas četras šķautnes no tās iet uz kādu no virsotnēm \(v_{1}, \ldots, v_{k-1}\). Apzīmēsim tās ar \(v_{i_{1}},\ v_{i_{2}},\ v_{i_{3}}\) un \(v_{i_{4}}\). Tad kāda no virsotnēm \(v_{i_{1}+1},\ v_{i_{2}+1},\ v_{i_{3}+1},\ v_{i_{4}+1}\) noteikti ir saistīta ar \(v_{1}\), jo starp virsotnēm \(v_{2}, \ldots, v_{k}\) ir ne vairāk kā \(3\), kas nav saistītas ar \(v_{1}\).

Esam pierādījuši, ka ir tāda virsotne \(v_{i}(1 \leq i < k)\), ka \(v_{1}\) ir saistīta ar \(v_{i+1}\), bet \(v_{i}\) ir saistīta ar \(v_{k}\). Tas nozīmē, ka sakārtojot mūsu garākā ceļa virsotnes secībā \(v_{1} \ldots v_{i}v_{k}v_{k-1} \ldots v_{i+1} v_{1}\) tās veido ciklu.

Pierādīsim, ka šajā ciklā ietilpst visas \(8\) virsotnes. Pieņemsim pretējo, ka ārpus šī cikla ir vēl kāda virsotne \(v\). Tā noteikti ir saistīta ar kādu no šī cikla virsotnēm \(v_{j}\) (jo ciklā ir vismaz \(5\) virsotnes), bet, ja tā, tad pārgriežot ciklu pie virsotnes \(v_{j}\) un pieliekot galā virsotni \(v\), mēs iegūtu celu, kas ir garāks nekā sākotnējais - pretruna. Tātad mēs esam ieguvuši Hamiltona ciklu - ceļu, kas iet cauri visām virsotnēm, katrā iegriežoties tieši vienu reizi. Apzīmēsim virsotnes šajā ciklā ar \(v_{1}v_{2} \ldots v_{8}\). Tad, atgriežoties pie tenisistiem, tos var salikt pa pāriem \(v_{1}-v_{2};\ v_{3}-v_{4};\ v_{5}-v_{6};\ v_{7}-v_{8}\), kas vēl nav spēlējuši savā starpā.

Piezīme. Dīraka teorēma apgalvo, ka, ja grafā ar \(n\) virsotnēm, no katras iziet vismaz \(\frac{n}{2}\) šķautnes, tad šajā grafā eksistē Hamiltona cikls. Šajā uzdevumā pēc būtības tika pierādīts šīs teorēmas speciālgadījums pie \(n=8\).

Atrisinājums-2

Tāpat kā iepriekšējajā atrisinājumā izveidosim grafu, kura virsotnes ir spēlētāji un tās ir saistītas ar šķautni tad un tikai tad, ja šie spēlētāji vēl nav spēlējuši spēli savā starpā.

Izvēlēsimies patvaļīgu spēlētāju \(A\), pieņemsim, ka tas ir spēlējis ar spēlētājiem \(B_{1},\ B_{2}\) un \(B_{3}\) un nav spēlējis ar spēlētājiem \(C_{1},\ C_{2},\ C_{3},\ C_{4}\) (skat. 39.att.). Sauksim jebkuru no \(B_{1},\ B_{2},\ B_{3}\) par \(B\) - virsotni, bet jebkuru no \(C_{1},\ C_{2},\ C_{3},\ C_{4}\) - par \(C\) - virsotni.

Katra no \(B\) - virsotnēm ir saistīta ar vismaz divām \(C\) - virsotnēm, jo tā ir saistīta ar četrām virsotnēm, nav saistīta ar \(A\) un ir saistīta ar lielākais divām citām \(B\) - virsotnēm.

Nav iespējams, ka visas \(B\) - virsotnes ir saistītas ar vienām un tām pašām divām \(C\) - virsotnēm un nav saistītas ar abām pārējām \(C\) - virsotnēm (skat. 40.att.). Šajā gadījumā virsotnes \(C_{3}\) un \(C_{4}\) jau ir saistītas ar \(4\) citām virsotnēm, tātad tās nav saistītas ne ar \(C_{1}\), ne \(C_{2}\). Bet tādā gadījumā \(C_{1}\), var būt saistīta vēl tikai ar \(C_{2}\), kas dod tai lielākais \(2\) šķautnes, kaut gan jābūt \(4\).

Tātad katra no \(B\) - virsotnēm ir saistīta ar vismaz divām \(C\) - virsotnēm un tās nav visiem vienas un tās pašas divas. Izvēlēsimies divas \(B\) - virsotnes, tā lai tās ir saistītas katra ar divām \(C\) - virsotnēm, bet ne ar vienām un tām pašām. Pieņemsim, ka tās ir \(B_{1}\) un \(B_{2}\), un pieņemsim, ka \(B_{1}\) ir saistīta ar \(C_{1}\) un \(C_{2}\), bet \(B_{2}\) ar \(C_{2}\) un \(C_{3}\) (skat. 41.att.). (Gadījums, kad \(B_{2}\) ir saistīta ar \(C_{3}\) un \(C_{4}\) ir analogs).

Tādā gadījumā virsotnei \(B_{3}\) varam ņemt patvaļīgu pāri no \(C\) - virsotnēm, ar ko tā ir saistīta.

Ja šī virsotne ir \(C_{2}\) (vai \(C_{4}\)), tad varam salikt pārus \(B_{3}-C_{2}\) (vai \(C_{4}\)), \(B_{1}-C_{1},\ B_{2}-C_{3}\).

Ja šī virsotne ir \(C_{1}\) - tad varam salikt pārus \(B_{3}-C_{1},\ B_{1}-C_{2},\ B_{2}-C_{3}\).

Ja šī virsotne ir \(C_{3}\) - tad varam salikt pārus \(B_{3}-C_{3},\ B_{1}-C_{1},\ B_{2}-C_{2}\).

Pēdējā \(C\) - virsotne būs pārī ar virsotni \(A\).

Tad, atgriežoties pie tenisistiem, tos var salikt pa pāriem, kas vēl nav spēlējuši savā starpā.