Atrisinājums

Apzīmēsim festivāla dalībniekus ar punktiem un, ja divi spēlētāji sava starpā ir izspēlējuši šaha partiju, tad atbilstošos punktus savienosim ar nogriezni. Tātad mums jānoskaidro, kāds ir mazākais novilkto nogriežņu skaits.

Ar \(f(n)\) apzīmēsim mazāko nogriežņu skaitu kas novilkti starp \(n\) punktiem un kam būtu spēkā uzdevumā dotā īpašība - starp katriem trim punktiem ir novilkts vismaz viens nogrieznis.

Apskatām \(n+1\) punktu. Izmetot jebkuru vienu punktu, ir jābūt spēkā īpašībai \(f(n+1)-d(i) \geq f(n)\), kur \(d(i)-i\)-tajā punktā ieejošo nogriežņu skaits. Saskaitot šīs nevienādības visiem \(n+1\) punktiem, iegūstam, ka \((n+1)f(n+1)-\sum d(i) \geq(n+1)f(n)\). Tā kā katrs nogrieznis ieskaitīts tieši divas reizes, tad \(\sum d(i)=2 f(n+1)\). Tātad

\[\begin{align*} & (n+1) f(n+1)-2f(n+1) \geq(n+1)f(n) \\ & f(n+1) \geq \frac{(n+1)f(n)}{n-1} \tag{*} \end{align*}\]

Zināms, ka \(f(3)=1\). Ievērojot, ka nogriežņu skaits ir naturāls skaitlis, pēc formulas (*) iegūstam, ka \(f(4) \geq 2\), \(f(5) \geq 4, f(6) \geq 6, f(7) \geq 9, f(8) \geq 12 \ldots\). Ar matemātiskās indukcijas metodi pierādīsim, ka visiem naturāliem \(k \geq 3\) izpildās \(f(2k) \geq k(k-1)\) un \(f(2k-1) \geq(k-1)^{2}\). *Indukcijas bāze.* \(f(3)=1,\ f(4)=2\). *Induktīvais pieņēmums.* Pieņemsim, ka katram \(k\) (\(2 \leq k \leq i\)) izpildās nevienādības \(f(2k) \geq k(k-1)\) un \(f(2k-1) \geq(k-1)^{2}\). *Induktīvā pāreja.* Pierādīsim, ka minētās sakarības ir spēkā arī pie \(k=i+1\). Pēc pieņēmuma \(f(2i) \geq i(i-1), i>1\). No (*) seko, ka

\[f(2i+1) \geq \frac{f(2i) \cdot(2i+1)}{2i-1} \geq \frac{i(i-1)(2i+1)}{2i-1}=\frac{2i^{3}-i^{2}-i}{2i-1}=\frac{i^{2}(2i-1)-i}{2i-1}=i^{2}-\frac{i}{2i-1}>i^{2}-1\]

Tātad \(f(2i+1) \geq i^{2}\). No (*) seko, ka

\[f(2(i+1))=f(2i+1+1) \geq \frac{2(i+1)f(2i+1)}{2i+1-1}=\frac{2(i+1)f(2i+1)}{2i} \geq \frac{(i+1)i^{2}}{i}=i(i+1)\]

Līdz ar to ir pierādīts, ka \(f(2k) \geq k(k-1)\) un \(f(2k-1) \geq(k-1)^{2}\) visiem naturāliem \(k \geq 3\). Tagad atliek aprakstīt, ka šāda situācija ir iespējama, t.i., starp \(2014\) punktiem, ievērojot uzdevuma nosacījumus, novilkti \(1013042\) nogriežņi. Ievērojam, ka \(f(2014)=f(2 \cdot 1007) \geq 1007 \cdot 1006=1013042\). Sadalām visus \(2014\) punktus divās vienāda izmēra grupās (katrā grupā \(1007\) punkti) un starp visiem vienas grupas punktiem novelkam visus nogriežņus. Katrā grupā nogriežņu skaits ir \(\frac{1007 \cdot 1006}{2}\), kopējais nogriežņu skaits ir \(\frac{1007 \cdot 1006}{2} \cdot 2=1007 \cdot 1006\). Tādējādi ir iegūts tieši vajadzīgais nogriežņu skaits. Izvēloties jebkurus trīs punktus, no Dirihlē principa seko, ka divi no šiem punktiem pieder vienai no izveidotajām divām grupām, līdz ar to starp šiem diviem vienas grupas punktiem ir novilkts nogrieznis. Tātad starp jebkuriem trīs punktiem ir novilkts vismaz viens nogrieznis.