Julekalender #14

Her kan brukere av forum utfordre hverandre med morsomme oppgaver og nøtter man ønsker å dele med andre. Dette er altså ikke et sted for desperate skrik om hjelp, de kan man poste i de andre forumene, men et sted for problemløsing på tvers av trinn og fag.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

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.
alund
Noether
Noether
Innlegg: 48
Registrert: 31/03-2017 21:40

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.
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

Yes, helt riktig. Dette kan generaliseres til n antall farger, men da må man benytte et større antall punkter i gitteret.
alund
Noether
Noether
Innlegg: 48
Registrert: 31/03-2017 21:40

[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.
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

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