Du er nyansatt sjef for en generalisert sjakkbrettfabrikk, men har dessverre glemt hvordan sjakkbrett egentlig ser ut. Alt du husker er at sjakkbrett er [tex]n \times n[/tex]-rutenett, at hver rute skal være enten hvit eller svart, og at for alle '2x2-kvadrater' av fire ruter skal eksakt to være hvite, og eksakt to være svarte.
Da du tidligere også var matematiker spør du deg selv naturligvis følgende spørsmål:
Gitt disse reglene, på hvor mange måter du kan fargelegge [tex]n \times n[/tex]-rutenettene på slik at de danner et sjakkbrett?
(To fargelegginger anses som forskjellige selv om de kan 'roteres' oppå hverandre eller lignende - det 'vanlige' sjakkbrettet og det sjakkbrettet vi får dersom alle hvite felter blir svarte og alle svarte felter blir hvite er altså to forskjellige fargelegginger. Om n=2 er det altså seks mulige fargelegginger.)
Sjakkbrettfargelegginger
Moderators: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
Hvis vi lar [tex]T_n[/tex] denotere antall måter å ordne et slikt nxn brett på, stemmer det at [tex]T_{2n} = 2^{2n+1}-2^{n+1}+2[/tex], og [tex]T_{2n+1} = 2T_{2n}+2[/tex] ?
Hadde vært greit å vite dette før jeg eventuelt legger ut en langdratt løsning.
Hadde vært greit å vite dette før jeg eventuelt legger ut en langdratt løsning.
Ja, men det finnes garanterte enklere måter å vise dette på. Noen av observasjonene kan forøvrig bevises med induksjon, men jeg har ikke nevnt dette.
Vanskelig å forklare uten tegning, men bruker tall i stedet: 0 er hvitt og 1 er svart. Vi lar de seks forskjellige 2x2 brikkene
10 01 10 01 11 00
01 10 10 01 00 11
være [tex]A_1, A_2, B_1, B_2, C_1[/tex] og [tex]C_2[/tex] respektivt. Vi prøver å finne de forskjellige mulighetene for et 2n x 2n-brett.
Noen observasjoner:
1) De eneste horisontale "naboene" til [tex]B_i[/tex] er [tex]B_i[/tex] selv.
2) De eneste vertikale naboene til [tex]C_i[/tex] er [tex]C_i[/tex].
3) [tex]A_1A_2[/tex] og [tex]A_2A_1[/tex] inneholder [tex]C_2[/tex] og [tex]C_1[/tex] respektivt.
4)
[tex]A_1 \ A_2[/tex]
[tex]A_2 \ A_1[/tex] inneholder [tex]B_2[/tex] og [tex]B_1[/tex] respektivt.
5) 1) og 2) medfører at dersom [tex]B_1[/tex] eller [tex]B_2[/tex] er inneholdt i brettet så danner de hele horisontale rekker. Det samme gjør [tex]C_1[/tex] og [tex]C_2[/tex] i vertikale rekker. Det betyr at B'ene og C'ene ikke kan være inneholdt i samme brett.
Betrakt 2n x 2n brettet som et nxn-brett av disse brikkene, vi kaller disse brikkene bestanddelene. Selv om 2nx2n-brettet inneholder en av disse 2x2-brikkene betyr altså ikke det at brikken er en bestanddel av nxn-brettet.
Vi har tre muligheter av 5):
a) Brettet består utelukkende av [tex]A_1[/tex] og [tex]A_2[/tex] (det teller ikke at f.eks [tex]B_1[/tex] er inneholdt i en slik konfigurasjon)
b) Brettet består av utelukkende [tex]A_1, A_2, B_1[/tex] og [tex]B_2[/tex].
c) Brettet består av utelukkende [tex]A_1, A_2, C_1[/tex] og [tex]C_2[/tex].
Av rotasjonssymmetri er det like mange konfigurasjoner av formen b) og c), så jeg argumenterer ut ifra b):
Ettersom [tex]A_1A_2[/tex] og [tex]A_2A_1[/tex] inneholder [tex]C_2[/tex] og [tex]C_1[/tex], må [tex]A_1[/tex] og [tex]A_2[/tex] eksistere som hele horisontale rekker av 5). Det holder altså å telle hvor mange måter slike rekker kan dannes av [tex]A_1[/tex], [tex]A_2[/tex], [tex]B_1[/tex] og [tex]B_2[/tex]-brikkene, ettersom det er enkelt å se at enhver slik måte danner et mulig brett. Det er n rekker, og vi har 4 muligheter for hver av dem. Det gir oss [tex]4^n[/tex] muligheter. Vi trekker ifra de [tex]2^n[/tex] mulighetene hvor hverken [tex]B_1[/tex] eller [tex]B_2[/tex] er med. b) danner altså [tex]4^n-2^n[/tex] muligheter, og det samme gjør c).
a): Av 3) og 4) ser vi at 5) medfører at [tex]A_1[/tex] og [tex]A_2[/tex] enten må danne vertikale eller horisontale rekker av identiske brikker. Dette kan gjøres på [tex]2 \cdot 2^n[/tex] måter, men vi har telt mulighetene hvor brettet består utelukkende av [tex]A_1[/tex], eller utelukkende av [tex]A_2[/tex] to ganger, så a) danner [tex]2 \cdot 2^{n}-2[/tex] muligheter.
Summen blir altså [tex]2(4^n-2^n)+2 \cdot 2^n - 2 = 2^{2n+1}-2[/tex] forskjellige konfigurasjoner for et 2nx2n-brett.
[tex]T_n = 2^{n+1}-2[/tex] stemmer i hvert fall for partallige n.
Legg nå til de rutene som skal til slik at vi får et 2n+1x2n+1-brett på toppen og til høyre for vårt 2nx2n-brett. Vi ser at vi kan danne 2 forskjellige brett for hver mulighet av b). Grunnen til dette er at vi kun kan danne to forskjellige 2x2-brikker i hjørnet øverst til høyre, og en slik brikke determinerer brettet.
For a) deler vi opp i de tilfellene det er horisontale rekker, og der det er vertikale rekker. Vi ser at vi kan danne to forskjellige 2x2-brikker i hjørnet øverst til høyre. Dersom brettet består utelukkende av [tex]A_1[/tex] eller [tex]A_2[/tex] ser vi at vi kan lage 3 forskjellige brett ved å variere brikken i hjørnet.
Summen av muligheter blir altså [tex]2(2(4^n-2^n)) + 2(2 \cdot 2^{n}-2-2)+3 \cdot 2 = 2^{2n+2}-2[/tex].
Formelen [tex]T_n[/tex] stemmer altså også for odde n.
Vanskelig å forklare uten tegning, men bruker tall i stedet: 0 er hvitt og 1 er svart. Vi lar de seks forskjellige 2x2 brikkene
10 01 10 01 11 00
01 10 10 01 00 11
være [tex]A_1, A_2, B_1, B_2, C_1[/tex] og [tex]C_2[/tex] respektivt. Vi prøver å finne de forskjellige mulighetene for et 2n x 2n-brett.
Noen observasjoner:
1) De eneste horisontale "naboene" til [tex]B_i[/tex] er [tex]B_i[/tex] selv.
2) De eneste vertikale naboene til [tex]C_i[/tex] er [tex]C_i[/tex].
3) [tex]A_1A_2[/tex] og [tex]A_2A_1[/tex] inneholder [tex]C_2[/tex] og [tex]C_1[/tex] respektivt.
4)
[tex]A_1 \ A_2[/tex]
[tex]A_2 \ A_1[/tex] inneholder [tex]B_2[/tex] og [tex]B_1[/tex] respektivt.
5) 1) og 2) medfører at dersom [tex]B_1[/tex] eller [tex]B_2[/tex] er inneholdt i brettet så danner de hele horisontale rekker. Det samme gjør [tex]C_1[/tex] og [tex]C_2[/tex] i vertikale rekker. Det betyr at B'ene og C'ene ikke kan være inneholdt i samme brett.
Betrakt 2n x 2n brettet som et nxn-brett av disse brikkene, vi kaller disse brikkene bestanddelene. Selv om 2nx2n-brettet inneholder en av disse 2x2-brikkene betyr altså ikke det at brikken er en bestanddel av nxn-brettet.
Vi har tre muligheter av 5):
a) Brettet består utelukkende av [tex]A_1[/tex] og [tex]A_2[/tex] (det teller ikke at f.eks [tex]B_1[/tex] er inneholdt i en slik konfigurasjon)
b) Brettet består av utelukkende [tex]A_1, A_2, B_1[/tex] og [tex]B_2[/tex].
c) Brettet består av utelukkende [tex]A_1, A_2, C_1[/tex] og [tex]C_2[/tex].
Av rotasjonssymmetri er det like mange konfigurasjoner av formen b) og c), så jeg argumenterer ut ifra b):
Ettersom [tex]A_1A_2[/tex] og [tex]A_2A_1[/tex] inneholder [tex]C_2[/tex] og [tex]C_1[/tex], må [tex]A_1[/tex] og [tex]A_2[/tex] eksistere som hele horisontale rekker av 5). Det holder altså å telle hvor mange måter slike rekker kan dannes av [tex]A_1[/tex], [tex]A_2[/tex], [tex]B_1[/tex] og [tex]B_2[/tex]-brikkene, ettersom det er enkelt å se at enhver slik måte danner et mulig brett. Det er n rekker, og vi har 4 muligheter for hver av dem. Det gir oss [tex]4^n[/tex] muligheter. Vi trekker ifra de [tex]2^n[/tex] mulighetene hvor hverken [tex]B_1[/tex] eller [tex]B_2[/tex] er med. b) danner altså [tex]4^n-2^n[/tex] muligheter, og det samme gjør c).
a): Av 3) og 4) ser vi at 5) medfører at [tex]A_1[/tex] og [tex]A_2[/tex] enten må danne vertikale eller horisontale rekker av identiske brikker. Dette kan gjøres på [tex]2 \cdot 2^n[/tex] måter, men vi har telt mulighetene hvor brettet består utelukkende av [tex]A_1[/tex], eller utelukkende av [tex]A_2[/tex] to ganger, så a) danner [tex]2 \cdot 2^{n}-2[/tex] muligheter.
Summen blir altså [tex]2(4^n-2^n)+2 \cdot 2^n - 2 = 2^{2n+1}-2[/tex] forskjellige konfigurasjoner for et 2nx2n-brett.
[tex]T_n = 2^{n+1}-2[/tex] stemmer i hvert fall for partallige n.
Legg nå til de rutene som skal til slik at vi får et 2n+1x2n+1-brett på toppen og til høyre for vårt 2nx2n-brett. Vi ser at vi kan danne 2 forskjellige brett for hver mulighet av b). Grunnen til dette er at vi kun kan danne to forskjellige 2x2-brikker i hjørnet øverst til høyre, og en slik brikke determinerer brettet.
For a) deler vi opp i de tilfellene det er horisontale rekker, og der det er vertikale rekker. Vi ser at vi kan danne to forskjellige 2x2-brikker i hjørnet øverst til høyre. Dersom brettet består utelukkende av [tex]A_1[/tex] eller [tex]A_2[/tex] ser vi at vi kan lage 3 forskjellige brett ved å variere brikken i hjørnet.
Summen av muligheter blir altså [tex]2(2(4^n-2^n)) + 2(2 \cdot 2^{n}-2-2)+3 \cdot 2 = 2^{2n+2}-2[/tex].
Formelen [tex]T_n[/tex] stemmer altså også for odde n.
... og her er en enklere måte:
Anta formelen [tex]T_n = 2^{n+1}-2[/tex] stemmer for n = k. Dersom [tex]B_1, B_2, C_1 [/tex] eller [tex]C_2[/tex] som definert er inneholdt i k+1xk+1 brettet, ser vi at vi har to muligheter for å fylle ut resten, som vi ser av å betrakte hjørnebrikken. Grunnen er at kxk-underbrettet determinerer en av sidene på k+1xk+1 av 1) og 2).
Dersom de ikke er det, er brettet som et vanlig sjakkbrett, eller med inverterte farger, dvs to muligheter. For hver av dem er det tre muligheter ved å betrakte hjørnebrikken.
Det betyr at antall måter å fargelegge k+1xk+1-brettet er [tex]2(T_k-2)+6=2T_k+2=T_{k+1}[/tex].
Siden det stemmer for n = 2, så stemmer den for enhver n.
Anta formelen [tex]T_n = 2^{n+1}-2[/tex] stemmer for n = k. Dersom [tex]B_1, B_2, C_1 [/tex] eller [tex]C_2[/tex] som definert er inneholdt i k+1xk+1 brettet, ser vi at vi har to muligheter for å fylle ut resten, som vi ser av å betrakte hjørnebrikken. Grunnen er at kxk-underbrettet determinerer en av sidene på k+1xk+1 av 1) og 2).
Dersom de ikke er det, er brettet som et vanlig sjakkbrett, eller med inverterte farger, dvs to muligheter. For hver av dem er det tre muligheter ved å betrakte hjørnebrikken.
Det betyr at antall måter å fargelegge k+1xk+1-brettet er [tex]2(T_k-2)+6=2T_k+2=T_{k+1}[/tex].
Siden det stemmer for n = 2, så stemmer den for enhver n.
Jeg har ikke sett over den første løsningen din helt, men den andre ser ihvertfall riktig ut. Om jeg ikke misforstår den er den mer eller mindre lik min, men jeg droppet induksjonstrinnet ved å betrakte den første raden av et blankt [tex]n \times n[/tex]-brett. Denne kan fylles ut på [/tex]2^n[/tex] måter. Hvis det er to felter med lik farge ved siden av hverandre må av din observasjon 1/2 er de to kolonnene entydig bestemt. Vi ser også at om tre av fire ruter i en 2x2-firkant er fylt ut er den fjerde også entydig bestemt, så nabokolonnene er også entydig bestemt, og fortsetter vi sånn er hele brettet bestemt av den første raden hvis det er to likefargede ruter ved siden av hverandre.
Hvis dette ikke er tilfellet har raden en alternerende fargelegging, som kan gjøres på to måter. Hvis dette er tilfellet må raden over også ha en alternerende fargelegging, og så videre for alle radene over. Hver av disse kan velges på to måter, så da vi har to valg i hver av de n radene blir dette [tex]2^n[/tex] muligheter. Altså blir det totale antallet [tex]2^n -2 + 2^n = 2^{n+1}-2[/tex].
Hvis dette ikke er tilfellet har raden en alternerende fargelegging, som kan gjøres på to måter. Hvis dette er tilfellet må raden over også ha en alternerende fargelegging, og så videre for alle radene over. Hver av disse kan velges på to måter, så da vi har to valg i hver av de n radene blir dette [tex]2^n[/tex] muligheter. Altså blir det totale antallet [tex]2^n -2 + 2^n = 2^{n+1}-2[/tex].