Feil i julenøtt

Aldri så galt at det ikke er godt for noe, heter det. Slik er det også med fjorårets julenøtter (TU nr. 45/02). Når de er gale, får man i hvert fall testet at leserne er våkne og følger med. Dessverre ble det en feil nøtteklassikeren med streker og prikker. Vi skrev at oppgaven kunne la seg løse med syv streker, men det riktige er selvsagt seks som flere har påpekt. Bernt S. Andersen var den første til å fortelle oss det, og han la ved en fin skisse som viser riktig svar:

Vi sender Bernt et sett pentominoer som takk for innsatsen.

Matteprofessor Harald E. Krogstad ved NTNU oppdaget også feilen, og gikk et skritt videre. Han har startet å utvikle en generell teori for oppgaver av denne type:

For å løse 3x3 "underveis" må vi komme inn med et strek mot et hjørne, enten parallelt med en sidekant, eller 135 grader på. For 4x4 kan vi først ta en sidekant, så den påfølgende. Deretter kan vi gå inn mot den resterende 3x3 parallelt med en sidekant, og følgelig trenge bare 6 streker! Det er også en annen variant som snur rekkefølgen på 3x3-løsningen. Siden starten på 4x4 også er strek inn mot et hjørne parallelt med en sidekant, vil samme ide ved induksjon (!) vise at minste antall streker for nxn er mindre eller lik 2(n-1) (når n2). Det gjenstår å vise at dette antallet er det minst mulige. Vi vet dermed atn=1 : 1 strekn=2 : 3 strekern=3 : 4 strekern 2 : # streker 2(n-1)Tusenkroners-spørsmålet er altså om det kan finnes en eller annen n slik at # streker 2(n-1)!Det er ikke spesielt sannsynlig, men en vet aldri før vi hoster opp et bevis, - eller et moteksempel.

Krogstad anbefaler disse nettsidene: www.mathpuzzle.com/dots.html. Krogstad får også pentomino-premie for utvikling av strek-prikk-teorien.

Er det noen av TU-leserne som kan kaste lys over spørsmålet?

Arne Asphjell