5. Zadatak
Dan je prirodni broj i konveksan mnogokut s vrhova. Svaka od stranica i dijagonala tog mnogokuta obojana je plavom ili crvenom bojom. Odredi najmanji takav da, za svako takvo bojanje, postoje tri vrha promatranog mnogokuta koja su međusobno spojena dužinama iste boje.
Rješenje
Za , stranice obojimo u jednu, npr. plavu boju, a dijagonale u drugu – crvenu boju. Tada je očito da ne postoji trokut čiji su vrhovi vrhovi tog četverokuta, a sve stranice su obojane u istu boju.
Za , stranice obojimo u jednu, npr. plavu boju, a dijagonale u drugu – crvenu boju. Tada je očito da ne postoji trokut čiji su vrhovi vrhovi tog peterokuta, a sve stranice su obojane u istu boju.
Time smo dokazali da je traženi .
Dokažimo sada da za svaki šesterokut vrijedi da, na koji god način obojali svaku od stranica i dijagonala tog šesterokuta u plavu ili crvenu boju, mora postojati barem jedan trokut čiji su vrhovi ujedno vrhovi tog šesterokuta i čije su stranice sve obojane u istu boju.
Uočimo jedan vrh tog šesterokuta, nazovimo ga A. Iz njega izlazi pet spojnica s drugim vrhovima koje su obojane ili u plavu ili u crvenu boju.
Kako je , prema Dirichletovom principu, postoji boja takva da su barem tri takve spojnice obojane u tu boju. Npr. neka je to crvena boja.
Označimo vrhove koji određuju te spojnice s vrhom A npr. s B, C i D, pa su crvene spojnice , i .
Ako je barem jedna od spojnica , ili obojana u crvenu boju, imamo istobojni (crveni) trokut.
Ako nije, onda je trokut istobojan (plavi).