WisFaq!

Aantal paardensprongen nodig om een schaakbordvak te bereiken

Hallo ik vroeg me laatst af of er een relatie F(x,y) bestaat, waarin:
F (x,y)= minimaal aantal stappen van beginpositie naar willekeurig eindpostitie.
x= aantal horizontale vlakken naar links dan wel rechts.
y= aantal verticale vlakken omhoog of naar beneden.

Op het moment heb ik er een gevonden echter klopt deze alleen niet voor x=+/-1 en voor x=+/-2. Bij mij komt er dan:
F(1,1)=1 i.p.v 3
F(2,2)=2 i.p.v 4
Voor de rest klopt het wel.

Voorwaarden:
C=2|y|-|x|
MOD(a,b)=MOD(variabele;deler)=rest (of remainder)

|x|=|y| Kies x altijd als grootste en y als kleinste coordinaat; Bijv bij F(2,3) bereken F(3,2)
x =ongelijk aan +/- 1
x =ongelijk aan +/- 2

Relatie (die ongetwijfeld nog verfijnt kan worden)
C=0 F(x,y)=[(|x|+MOD(|C|;4))/2]
C0 F(x,y)= [(|x|+|y|+4-2*MOD(C-1;3))/3]

Ik ben benieuwd of er ook een exacte oplossing voor dit probleem bestaat om te zien welke "fout" ik bega.

Oke hopelijk dat iemand me hierbij opweg kan helpen. In iedergeval alvast bedankt.

Groeten Wytze

Wytze Hoekstra
12-9-2005

Antwoord

Dag Wytze,

Eerst een afspraak: de zet die bestaat uit twee vakjes naar rechts en een naar boven, noem ik rechtsboven, wat dus niet hetzelfde is als bovenrechts (=2 naar boven, 1 naar rechts)

Je begint alvast goed door de symmetrie te gebruiken en dus enkel de situaties te beschouwen waarvoor x en y positief zijn, en xy.

Ook is het goed om naar de rechte y=x/2 te kijken: boven deze rechte zal het aantal zetten grofweg (x+y)/3 zijn, onder deze rechte zal het aantal zetten grofweg x/2 zijn.

Maar als ik jouw formules bekijk, kan het dan niet zijn dat daar niet-gehele getallen uitkomen? Of bedoel je met [x ] het grootste geheel getal, kleiner dan of gelijk aan x?

Om eerlijk te zijn, ik zie niet goed in hoe je komt aan die C mod 4 en C-1 mod 3? Ik zou het eerder modulo 6 aanpakken: bijvoorbeeld voor het geval C0:
° x+y = 0 of 3 mod 6: dan brengt elke zet je drie vakken dichter bij het doel, je kan het doel bereiken door een juiste combinatie van sprongen naar rechtsboven en naar bovenrechts, dus dat zijn dan (x+y)/3 sprongen.
° x+y = 1 mod 6: dan weet je zeker dat het in een oneven aantal zetten zal moeten, en in meer zetten dan (x+y-1)/3. Kan het in (x+y+2)/3? Antwoord is ja: immers, je kan in (x+y-1)/3 zetten het vakje bereiken dat links ligt van het doel. In de route die je daarvoor volgt zit minstens 1 sprong naar rechtsboven, vervang die door een sprong naar bovenrechts en een sprong naar rechtsonder, en je bent in het doel.
° Deze redenering maak je voor alle gevallen x+y = ... mod 6: je kijkt of je een even of oneven aantal sprongen nodig hebt, je weet ook hoeveel sprongen je MINSTENS zal nodig hebben, en je probeert dan een manier te vinden om het in dat aantal sprongen te doen. Zelf kwam ik dan op dit resultaat:
x+y=0 mod 6 Þ (x+y)/3
x+y=1 mod 6 Þ (x+y+2)/3
x+y=2 mod 6 Þ (x+y+4)/3
x+y=3 mod 6 Þ (x+y)/3
x+y=4 mod 6 Þ (x+y+2)/3
x+y=5 mod 6 Þ (x+y+4)/3
Merk op dat je dit ook kan opschrijven als
x+y=0 mod 3 Þ (x+y)/3
x+y=1 mod 3 Þ (x+y+2)/3
x+y=2 mod 3 Þ (x+y+4)/3
Dus dat verklaart die modulo3-elementen in jouw formule dus toch...

Voor het geval C0 kan je een analoge redenering maken: de gevallen die je onderscheidt zijn dan
° x = 0 mod 2 en y = x/2 mod 2
° x = 0 mod 2 en y ¹ x/2 mod 2
° x = 1 mod 2 en y = (x-1)/2 mod 2
° x = 1 mod 2 en y = (x+1)/2 mod 2

De formules die ik dan bekom hebben hetzelfde gebrek als de jouwe, namelijk voor F(2,2) en F(1,0) (die bedoelde je toch he?) geven ze een te laag resultaat. Dat komt omdat de redenering er gekomen is door te zeggen: 'bekijk de route om naar punt A te gaan, vervang in die route de zet a door de twee zetten b en g, en dan kom je uit in het doel, punt B'. Maar als in de route van O naar A geen zet a voorkomt, klopt deze constructie niet....

(2,2) en (1,0) zijn denk ik wel de enige punten waarvoor het niet klopt. Ik vrees dat er niks anders opzit dan de functie F in deze twee punten afzonderlijk te bepalen als zijnde 4 resp. 3.

Groeten,
Christophe.

Christophe
18-9-2005