Side 1 av 1
Julekalender #14
Lagt inn: 14/12-2017 23:22
av Gustav
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.
Re: Julekalender #14
Lagt inn: 18/12-2017 00:34
av alund
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.
Re: Julekalender #14
Lagt inn: 18/12-2017 00:37
av Gustav
Yes, helt riktig. Dette kan generaliseres til n antall farger, men da må man benytte et større antall punkter i gitteret.
Re: Julekalender #14
Lagt inn: 18/12-2017 00:58
av alund
[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.
Re: Julekalender #14
Lagt inn: 18/12-2017 01:37
av Gustav
Jepp, helt rett. Oppgaven er forøvrig fra Problem solving strategies av Engel.