Fargelegging av planet

[Karl_Erik]

Anta at planet fargelegges i r farger.

(i) Vis at om r=3 finnes to punkter i avstand 1 fra hverandre med lik farge.

(ii) Vis at om r=7 behøver det ikke å finnes to punkter i avstand 1 fra hverandre med lik farge.

(Det er i følge Wikipedia ikke kjent om en alltid kan finne to slike punkter for r=4, 5 eller 6.)

[FredrikM]

Gjør i)

Om påstanden er feil, kan man fylle planet med likesidete trekanter hvor hvert gjørne er merket med R,B, eller G (rød, blå, grønn).

Tegn én slik trekant i planet. Da er alle nabo-trekantene unikt bestemt. F.eks trekanten som grenser til kanten med hjørner B,G ha tredje hjørne R. Men fortsetter vi slik, kommer vi over en selvmotsigelse. (jeg fikk f.eks en trekant RRB)

[Karl_Erik]

Gjør i)

Om påstanden er feil, kan man fylle planet med likesidete trekanter hvor hvert gjørne er merket med R,B, eller G (rød, blå, grønn).

Tegn én slik trekant i planet. Da er alle nabo-trekantene unikt bestemt. F.eks trekanten som grenser til kanten med hjørner B,G ha tredje hjørne R. Men fortsetter vi slik, kommer vi over en selvmotsigelse. (jeg fikk f.eks en trekant RRB)

Jeg har tegnet mønsteret forholdsvis stort, men klarer ikke finne noen selvmotsigelse. Kan du tegne en figur i paint eller noe?

[Gustav]

Jeg trur man kan vise i) ved å se på den såkalte Moser spindle enhetsgrafen, altså at det er umulig å fargelegge den med kun 3 farger.

Altså denne grafen: http://mathworld.wolfram.com/images/eps ... le_700.gif

[FredrikM]

Jeg har tegnet mønsteret forholdsvis stort, men klarer ikke finne noen selvmotsigelse. Kan du tegne en figur i paint eller noe?

Jeg er visst dårlig å tegne likesidete trekanter

[Charlatan]

Jeg trur man kan vise i) ved å se på den såkalte Moser spindle enhetsgrafen, altså at det er umulig å fargelegge den med kun 3 farger.

Altså denne grafen: http://mathworld.wolfram.com/images/eps ... le_700.gif

Hva mener du? Viser ikke dette at det er mulig å fargelegge denne grafens hjørner slik at ingen av fargene er av avstand 1 med hverandre? Jeg ser ikke hvordan det skal vise at det er umulig å farge planet med 3 farger. Mulig jeg misforstår.

[Gustav]

Jeg trur man kan vise i) ved å se på den såkalte Moser spindle enhetsgrafen, altså at det er umulig å fargelegge den med kun 3 farger.

Altså denne grafen: http://mathworld.wolfram.com/images/eps ... le_700.gif

Hva mener du? Viser ikke dette at det er mulig å fargelegge denne grafens hjørner slik at ingen av fargene er av avstand 1 med hverandre? Jeg ser ikke hvordan det skal vise at det er umulig å farge planet med 3 farger. Mulig jeg misforstår.

På figuren er det brukt 4 farger.. Med 3 farger går det ikke.

Hvis vi i planet velger oss hjørnene i figuren i linken, vil det være umulig å fargelegge hjørnene med kun 3 farger slik at alle par av nabohjørner er av ulik farge.

[Charlatan]

Ah, selvsagt, tenker ikke alltid klart. Fin løsning, forresten.

[Karl_Erik]

Det er selvfølgelig helt riktig.

[Gustav]

ii) r=7. Fargene er angitt med nummer på figuren (det er kun de nummererte fargene i midten av figuren under som skal betraktes (ikke de i kantene, som kun er til "pynt"))



Her er diagonalene til hvert heksagon 1 og mønsteret er translasjonssymmetrisk.

Betrakter vi hvert heksagon(med alt inni) som en lukket delmengde av planet, farger vi første det indre i hvert heksagon slik det er angitt på figuren. Hjørnene farges slik det er angitt med prikker på figuren. Hver kant kan farges i samme farge som en av naboheksagonene.

(Eventuelt kunne man på en enklere måte farget høyst én kant i hvert heksagon med samme farge som det som er innenfor heksagonet.. )

[Karl_Erik]

Dette ser helt riktig ut. Jeg tok begge oppgavene fra Wikipediaartikkelen, og det står forøvrig flere interessante resultater om problemet der om en er interessert.