matematikk.net

Hvert punkt i planet farges rød eller blå. Vis at det må finnes et rektangel slik at alle hjørnene har samme farge.

Hint:

[+] Skjult tekst

Betrakt et gitter av punkter i planet bestående av $3\times 9$ punkter som er farget rød eller blå, og bruk Dueboksprinsippet anvendt på radene i gitteret.

Tar hintet, med 9 rader og 3 kolonner.

Dueboksprinsippet sier at hver rad har minst to likefargede punkt (2 farger, 3 punkt).

Der er [tex]2^3=8[/tex] mulige fargekombinasjoner for hver rad, og siden vi betrakter 9 rader, vil etter dueboksprinsippet minst to av dem ha samme kombinasjon. Om vi ser på to likefargede rader, kan de danne et rektangel med to likefargede punkt i hver rad, slik at alle hjørnene har lik farge.

Det må finnes et slikt rektangel i et [tex]3\times 9[/tex] gitter, og dermed også i planet.

Yes, helt riktig. Dette kan generaliseres til n antall farger, men da må man benytte et større antall punkter i gitteret.

[tex]n+1[/tex] kolonner og [tex]n^{n+1}+1[/tex] rader?

Hver rad vil ha minst to likefargede punkt etter dueboksprinsippet.

Der er [tex]n^{n+1}[/tex] mulige fargekombinasjoner for hver rad, og siden der er [tex]n^{n+1}+1[/tex] rader, vil minst to ha samme fargekombinasjon, og danne et rektangel med de likefargede punktene i hver rad for å få likefargede hjørner.

Jepp, helt rett. Oppgaven er forøvrig fra Problem solving strategies av Engel.