matematikk.net

Vi har et uendelig stort ruteark, delt inn i ruter.

Vi faregelegger et utvalg av disse rutene, og gjennomfører følgende algoritme flere ganger.
- For enhver rute defineres ruten selv, ruten direkte over og direkte til høyre, i alt 3 ruter, som rutens område, uavhengig om den er fargelagt eller ikke.
- Dersom en rute har 2 eller flere ruter i ditt område, fargelegges den dersom den er tom, og las være dersom den er farget.
- Dersom en rute har 1 eller færre ruter i sitt område, hviskes fargen bort dersom den er fargelagt, og las være dersom den er tom.

Hver gang denne algoritmen utføres, sier vi har en generasjon har forløpt.

Vis at uansett hvordan n ruter fargelegges, vil ingen ruter være fargelagt når n generasjoner har forløpt.

Så, for det generelle tilfellet, del rutenettet som inneholder de n fargede rutene inn i så små rektangler som mulig slik at ingen par av rektangler har noe felles sidekant eller hjørne. (Det vil si slik at det er minst en rute mellom alle, slik at rektanglene viskes ut 'uavhengig av hverandre'.) Det holder da å vise at slike rektangler dør ut innen det påkrevde antallet generasjoner, i og med at vi med flere uavhengige rektangler bare får bedre tid på oss.

Vi legger først merke til at om vi har et rektangel i rutenettet med sidelengder a og b og ingen fargede ruter utenfor dette, vil ruten øverst til høyre nødvendigvis dø ut med en gang. Neste generasjon vil de to rutene til venstre og under den avdøde også dø, og vi ser at for hver generasjon vil denne grusomme dødslinja flytte seg enda et felt nedover. Altså har vi vist lemmaet at et slikt rektangel dø ut i løpet av (høyst) [tex]a+b-1[/tex] generasjoner. (Grensen følger ganske enkelt ved å telle etter hvor lang tid linja bruker på å nå nederste høyre hjørne.)

Dette er ikke tilstrekkelig, men går vi dette nærmere etter i sømmene ser vi at dersom dødslinja på sin ferd kan hoppe over en rad tar prosessen en generasjon mindre. Mer formelt: Nummererer vi så dødslinjene slik at linja som inneholder den øverste ruta til høyre kalles linje 1, linja som inneholder ruten under og ruten til venstre får nummer 2 og så videre slik at linja som inneholder ruta nederst til venstre får nummer [tex]a+b-1[/tex] ser vi at for hver [tex]i[/tex] slik at [tex]i[/tex] er tom etter [tex]i-1[/tex] generasjoner kan vi redusere den øvre grensen vår med 1. Legger også merke til at dersom det er [tex]k[/tex] fargede ruter på en linje [tex]i[/tex] kan disse kun påvirke linjer fram til linje [tex]i+k-1[/tex].

Disse observasjonene totalt gir oss det vi trenger. Det er [tex]a+b-1[/tex] rader som dødslinja vår må gjennom. k fargelagte ruter i en linje kan høyst påvirke de k neste lionjene, så er det N ruter fargelagte ruter totalt vil alt være utdødd innen N generasjoner.

Dette ser bra ut.