10. príklad - Vzorové riešenie

Spočiatku si uvedomme tri veci: Za prvé, vieme si vtaky predstaviť ako body na nejakej úsečke, za druhé, my netušíme v akom poradí sa jednotlivé vtáky vyskytujú, a za tretie, vzdialenosti medzi nimi môžu byť naozaj ľubovoľné. Teda je naozaj ťažké pracovať reálne so vzdialenosťami medzi nimi.

Preto my tento problém obídeme tak, že len rozdelíme celkovú vzdialenosť medzi najľavejším a najpravejším vtákom na zdialenosti medzi každou dvojicou susedných vtákov a následne ukážeme, že každá takáto vzdialenosť je zahrrnutá vo viacerých rôznopohlavných dvociciach ako v rovnakopohlavných.

Pozrime na nejakú "medzeru" medzi dvoma susednými vtákmi. Vľavo od nej je nejaké množstvo holubov A a holubíc B a vpravo od nej je n-A holubov a n-B holubíc. Teda takých párov, ktoré sú medzi vtákmi rovnakých pohlaví a ich vzájomná vzdialenosť obsahuje túto medzeru (teda má jedného vtáka naľavo a druhého napravo od nej) je A\times (n-A) pre holuby a B\times (n-B) pre holubice. Dokopy je to teda A\times (n-A)+B\times (n-B)

Teraz sa pozrime na dvojice medzi vtákmi rôznych pohlaví ktorých vzájomná vzdialenosť tiež obsahuje túto medzeru. Párov kde je holub vľavo a holubica vpravo od tejto medzery je A\times (n-B) a takých kde je holub vpravo a holubica vľavo je B\times (n-A). Dokopy teda A\times (n-B)+B\times (n-A)

Teraz ukážeme sériou ekvivalentných úprav, že viac rôznopohlavných dvojíc zahŕňa túto medzeru ako rovnakopohlavných.

A\times(n-B)+B\times(n-A) \ \square \ A\times(n-A)+B\times(n-B) \\ n\times(A+B) -2AB \ \square \ n\times(A+B)-A^2-B^2 \ \ \ \ /+A^2+B^2-n\times(A+B) \\ A^2-2AB+B^2 \ \square \ 0 \\ (A-B)^2 \geq 0 \implies A\times(n-B)+B\times(n-A) \geq A\times(n-A)+B\times(n-B)