Kongeflytting

[daofeishi]

Noam Elkies kjører for tiden et problemløsningsseminar med oss. Her følger en oppgave derfra:

Finn antall måter en konge kan flyttes fra e1 til e8 på et normalt sjakkbrett i nøyaktig 7 trekk.



Husk, i ett trekk kan du flytte en konge til én av naborutene horisontalt, vertikalt eller diagonalt.

Én mulighet er altså e1 -> e2 -> e3 -> e4 -> e5 -> e6 -> e7 -> e8
En annen mulighet er e1 -> d2 -> e3 -> f4 -> g5 -> f6 -> e7 -> e8


Her bør det finnes en del ulike løsningsmåter.

[fish]

Rent umiddelbart ville jeg tro at man må kunne tenkte trinomisk i dette tilfellet. Vi har tre typer flyttinger. Antall flyttinger på skrå mot høyre må det være like mange av som dem på skrå mot venstre. Vi burde da få at det søkte antallet blir

[tex]\frac{7!}{1!\cdot 3!\cdot 3!}+\frac{7!}{3!\cdot 2!\cdot 2!}+\frac{7!}{5!\cdot 1!\cdot 1!}+\frac{7!}{7!\cdot 0!\cdot 0!}=393[/tex]

Vi kan legge merke til at det er plass til tre høyreflyttinger på rad fra starten.

[daofeishi]

Stemmer det

[Karl_Erik]

Om man setter et tall i hver rute som angir antall måter man kan komme seg til den ruten på som en del av en gyldig reise fra e1 til e8 ser man straks at tallet i en rute må være summen av tallene i de tre rutene under. Da kan man enkelt fylle ut rutene og komme fram til svaret 393. Vet dog ikke helt hvordan jeg kan generalisere dette til en eksplisitt formel for ruter på n trekk fra e1 til e(n+1).

[daofeishi]

Generalisering til n trekk kan fort bli komplisert, siden det er restriksjonene paa antall trekk som gjoer svaret enkelt i dette tilfellet.

Hvis du vil generalisere til n trekk fra e1 til e(n+1), som du foreslaar Karl Erik, saa kan fish sin loesning benyttes