Opravovatelia

Štepi [email protected]

Krivoš [email protected]

Zaujíma nás iba, ktoré políčka sú párne a nepárne. Nad dvomi rovnakými políčkami je párne, takže v pyramídke (dve políčka vedľa seba a jedno nad nimi) vieme mať najviac dve nepárne. Z toho sa zdá, že párnych by mala byť aspoň tretina pyramídy. A naozaj, takúto konštrukciu vieme spraviť: označíme políčka v riadkoch postupne $A, B, C, A, B, C, \dots$ a začneme tak, aby prvé dve políčka v každom riadku boli iné ako to nad nimi. Potom za párne zvolíme to písmeno, ktorého je najmenej. Nech má pyramída $k=\frac{n(n+1)}{2}$ políčok, potom takto dostaneme najviac $\left\lfloor k / 3 \right\rfloor$ párnych (nemôže byť z každého čísla viac ako tretina). Toto rozdelenie parity vyhovuje, lebo v každej pyramídke bude práve jedno párne číslo, čo vždy sedí.

Ako dokážeme, že to nejde lepšie? Plán je taký, že si pyramídu rozdelíme na niekoľko disjunktných trojíc políčok a o každej trojici povieme, že v nej musí byť aspoň jedno párne políčko, takže dokopy párnych musí byť aspoň tretina. V trojici v tvare malej pyramídky naozaj musí byť aspoň jedno párne, ale nevieme celú pyramídu rozdeliť na takéto trojice.

Čo ale vieme, je rozdeliť pyramídu na trojice buď tvaru pyramídky, alebo tvaru troch políčok vedľa seba. Spravíme to tak, že každý riadok najprv vyplníme trojicami vedľa seba a potom zostávajúce miesta na koncoch riadkov vyplníme pyramídkami. Môže sa nám stať, že nám ostane jedno políčko neobsadené (ako na obrázku). Každopádne, máme takto presne $\left\lfloor n / 3 \right\rfloor$ trojíc.

Nazvime trojicu dobrá, ak nemá žiadne párne políčko, a zlá, ak má viac ako jedno párne políčko. Aby sme dostali menej párnych políčok než $\left\lfloor k / 3 \right\rfloor$, muselo by byť viac dobrých trojíc než zlých. Ale každá dobrá trojica musí mať nad sebou dve párne políčka, ktoré patria do tej istej trojice. Takže každá dobrá trojica má nad sebou (inú) zlú trojicu a teda párnych políčok je naozaj aspoň $\left\lfloor k / 3 \right\rfloor$.