Feladat: 8.25.
a) A sík pontjait kiszíneztük két
színnel. Igazoljuk, hogy lesz olyan téglalap, amelynek
csúcsai azonos szín?ek.
b) Oldjuk meg a feladatot, ha n színnel
színezünk!
c) Az a) és b) feladatrészben is elegendő, ha
k
(azaz előre rögzített véges sok) pontot színezünk ki.
Adjunk meg megfelelő
k számot az egyik és a másik esetben
is!
Megoldás: 8.25
a) Egy
3×7-es pontrács színezése
során biztosan kialakul ilyen téglalap, ez 21 pontot
jelent.
b) Egy
(n+1)×(n·(
n+1
2
)+1)-es pontrács esetén minden sorban van legalább
két azonos szín? pont. Minden sorban kiválasztunk
két aazonos szín? pontot és a sor mellé
írjuk oda, mely szín és melyik pontpár.
Ezekből
n illetve
(
n+1
2
) van, így a megadott
pontrács jó lesz. Persze ennél nagyvonalúbbak is
lehetünk, ha a pontrácsunk mérete
(n+1)×(
nn+1
+1). Ebben az esetben lesz két azonosan
színezett sor.