Damstenen verleggen

[Da_Ward]

Damstenen verleggen






Op het 4x4 bord liggen de genummerde damstenen 1 t/m 16 in een verkeerde volgorde






5 |15 | 8 | 2
13| 7 | 11 | 14
4 | 10 | 1 | 6
16 | 9 | 3 | 12
zo in deze volgorde staan ze.
hoe kan ik makkelijk uitrekenen hoe ik dat kan doen??



Een zet in dit spel bestaat uit het verwisselen van positie van twee damstenen.

Hoeveel zetten zijn minstens nodig om de stenen in de juiste volgorde te krijgen?



1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
zo moeten ze komen te staan!


En, kan het bij een andere beginstand nog meer zetten vergen om tot de juiste volgorde te komen?


Ik snap echt helemaal niks van deze som, hulp zou echt heel fijn zijn!!!!
alvast bedankt

[luijs]

Of je dit kunt uitrekenen weet ik niet, maar ik kan wel het maximale aantal zetten geven (tenminste, als je geen fouten maakt).

Stel ze liggen zo:

2 | 3 | 4 | 5
6 | 7 | 8 | 9
10|11|12|13
14|15|16| 1

Dan zet je eerst 1 op de goede plek, 2 komt dan op de laatste plek.
Dan zet je 2 op de goede plek, 3 komt dan op de laatste plek.
etc
Dan zet je 15 op de goede plek, 16 komt dan op de laatste plek.
Klaar.

15 zetten maximaal. Want met de laatste zet leg je altijd 2 stenen goed.

[Da_Ward]

Hmm, dat klopt wel, aangezien elke 'zet' 2 stenen mag veranderen. Dus anngezien je de laatste dan nog 2 over hebt, dus in totaal heb je 30 stenen veranderd? :

steen 1 -» goede plaats
steen 2 -» laatste plaats
dus een zet.
dus dat klopt,
maar nu die andere nog...

[Da_Ward]

Hmm, dat klopt wel, aangezien elke 'zet' 2 stenen mag veranderen. Dus anngezien je de laatste dan nog 2 over hebt, dus in totaal heb je 30 stenen veranderd? :

steen 1 -» goede plaats
steen 2 -» laatste plaats
dus een zet.
dus dat klopt,
maar nu die andere nog...

En toen kwam ik dus op deze redenering kijken of die klopt:

in mijn eerste situatie ( de lastige vraag ) staan 15 stenen op de foute plaats (10 niet). in Luijs situatie staan 16 stenen op de verkeerde plaats, omdat je in de laatste zet 2 stenen goed zet moet er 1 vanaf.
15 stenen dus - 1 = 14 zetten heb je nodig
in Luijs situatie: 16 stenen fout- 1 = 15 zetten, kan deze redenering kloppen?

[luijs]

Kan kloppen, maar hoeft niet.

Kijk hier maar eens naar:

2 | 1 | 4 | 3
6 | 5 | 8 | 7
10| 9|12|11
14|13|16|15

16 cijfers op de verkeerde plek.
Dus volgens jouw redenering moeten er 15 zetten gedaan worden.
Maar je kunt in 8 zetten alles goed maken, aangezien er elke keer 2 cijfers op de goede plek komen.

Dus... Volgens mij moet je gewoon proberen..?

Je hebt in ieder geval minstens 1 zet nodig per 2 verkeerde getallen, en max (verkeerde.getallen - 1) aantal zetten.

[luijs]

Per 'cirkeltje' dat je kunt maken trek je 1 af van het totale aantal verkeerd geplaatste stenen.

In mijn eerste voorbeeld is er 1 cirkeltje.

Cirkeltje:
Begin bij een plek waar een verkeerd getal staat.
Ga dan naar de plek waar dat getal hoort te staan en kijk welk getal daar staat.
Ga dan naar die plek en kijk welk getal daar staat.
Etc.
Uiteindelijk kom je weer bij je begin-getal uit.

Dat is één cirkeltje.
Per cirkeltje kun je 1 keer omwisselen van het totaal aantal verkeerd geplaatste stenen afhalen.
(in voorbeeld 1 was dat 16 - 1 = 15)


Nu in voorbeeld 2:

Als ik begin op plek 1, staat daar cijfer 2.
Ga naar plek 2, daar staat cijfer 1.
Dus, ga weer naar plek 1.
Cirkeltje rond.

En zo zijn er in dat voorbeeld 8 cirkeltjes op 16 verkeerd geplaatste stenen.

16 - 8 = 8


Nu dit voorbeeld:

2 | 3 | 1 | 5
6 | 7 | 8 | 9
5 |10|11|12
13|14|15|16

Er zijn hier 9 verkeerd geplaatste stenen.

Kijken hoeveel 'cirkeltjes' er zijn.

2-3-1 is een cirkeltje
5-6-7-8-9 is een cirkeltje
totaal 2 cirkeltjes.

9 - 2 = 7 zetten nodig om alles goed te krijgen.

Pas dit nu maar toe op jouw eigen voorbeeld.

Succes, en ik hoop dat je er iets aan hebt!!



PS: ik gebruik hier geloof ik niet de officiele termen van de wiskunde, maar dit moet een hulpmiddel zijn om het op te kunnen lossen. Vraag je docent maar wat de officiele stelregel is (of de officiele benaming) en post dit dan weer hier, dan weet ik dat ook weer!

[Pierewiet]

2 | 1 | 4 | 3
6 | 5 | 8 | 7
10| 9|12|11
14|13|16|15

In deze situatie heb je precies het minimale aantal zetten, hezelfde aantal zetten wanneer de cijfers in de volgorde 16 t/m 1 zouden liggen en in de volgorde 1 t/m 16 gelegd worden.
Het aantal zetten ligt, afhankelijk van de ligging, tussen 8 en 15.

[Sjoerd Job]

Damstenen verleggen

Op het 4x4 bord liggen de genummerde damstenen 1 t/m 16 in een verkeerde volgorde

5 |15 | 8 | 2
13| 7 | 11 | 14
4 | 10 | 1 | 6
16 | 9 | 3 | 12
zo in deze volgorde staan ze.
hoe kan ik makkelijk uitrekenen hoe ik dat kan doen??

Een zet in dit spel bestaat uit het verwisselen van positie van twee damstenen.

Hoeveel zetten zijn minstens nodig om de stenen in de juiste volgorde te krijgen?



1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
zo moeten ze komen te staan!


En, kan het bij een andere beginstand nog meer zetten vergen om tot de juiste volgorde te komen?


Ik snap echt helemaal niks van deze som, hulp zou echt heel fijn zijn!!!!
alvast bedankt

Nu, logica zegt dat er maximaal 16 zetten nodig zijn.
Om het minimaal aantal zetten te vinden is lastiger. Men zou het kunnen gaan beredeneren, maar als je ook nog op zoek wilt naar een lastigere verwisseling, zou ik een oplosser schrijven, die een lijst van posities mee kan krijgen. Dat vertaalt dit probleem naar een simpele waslijst controleren. Hoe snel dat gaat, tsja, dat is de vraag.

Eerst eens even kijken hoeveel mogelijke rangschikkingen er zijn.
16 stenen, 16 plaatsen, volgorde doet er toe. 16! (lees: 16-faculteit) mogelijkheden. Aardig wat.

Nu heb ik gesteld dat er maximaal 16 verwisselingen nodig zijn, om de puzzel op te lossen. (Zet 1 op z'n plek, zet 2 op z'n plek, etc).

Nu vind ik dit probleem interessant genoeg om er in mijn vrije tijd mee te gaan prutsen, dus heb ik misschien over een paar weken wel een oplossing

[Da_Ward]

ok, mijn beredenering klopte niet.
als je het minimale getal wilt mag je toch helemaal niet van faculteit afgaan? dat is toch heel wat anders..?
Nu gaan we uit van de MAXIMALE aantal zetten. Het probleem is dat het minimale, moeilijker is.
Want je kan bijv. als je een steen net iets anders neerzet, en niet direct op de goede plaats een zet minder creëren waardoor deze opgave onmogelijk lijkt!
Er moet een bepaalde logica achter zitten anders zou ik deze som niet mee naar huis krijgen. Maar aangezien hij eerst wil dat ik de som maak en dan pas de uitleg krijg kan ik ook niet ver komen.

Kijk je naar dit figuur:
2 | 1 | 4 | 3
6 | 5 | 8 | 7
10| 9|12|11
14|13|16|15

Je hebt inderdaad 16 plekken op de verkeerde, maar:
2 - 1 4 - 3 je hoeft maar een keer te switchen. Als je bijv:
3 - 1 4 - 2 dan heb je direct al meer zetten nodig. het kan natuurlijk ook zo zijn dat er geen logica achter zit, maar zoals ik al zei, dan lijkt het onmogelijk! Erg moeilijk deze opgave..

[luijs]

Kijk je naar dit figuur:
2 | 1 | 4 | 3
6 | 5 | 8 | 7
10| 9|12|11
14|13|16|15

Je hebt inderdaad 16 plekken op de verkeerde, maar:
2 - 1 4 - 3 je hoeft maar een keer te switchen. Als je bijv:
3 - 1 4 - 2 dan heb je direct al meer zetten nodig. het kan natuurlijk ook zo zijn dat er geen logica achter zit, maar zoals ik al zei, dan lijkt het onmogelijk! Erg moeilijk deze opgave..

We gaan maar weer eens een cirkeltje maken.
(cirkels zijn de mooiste figuren... *zucht*...)

Met jouw 3142:

Begin op plek 1. Daar ligt steen 3
Ga naar plek 3. Daar ligt steen 4
Ga naar plek 4. Daar ligt steen 2
Ga naar plek 2. Daar ligt steen 1
Ga naar plek 1. Daar ben je al geweest.
Cirkeltje rond.

Per "cirkeltje" trek je 1 zet af van het totale aantal verkeerde stenen.

4 verkeerde stenen
1 cirkeltje
--------------------------
4 - 1 = 3 zetten nodig om het goed te leggen


In het voorbeeld 2143:
Ga naar plek 1. Daar ligt steen 2
Ga naar plek 2. Daar ligt steen 1
Cirkeltje rond.
Ga naar plek 3. Daar ligt steen 4
Ga naar plek 4. Daar ligt steen 3
Cirkeltje rond.

4 verkeerde stenen
2 cirkeltjes
--------------
4 - 2 = 2 zetten nodig om het goed te leggen


En daar heb je je algoritme.

[Da_Ward]

en kan je die ook toepassen bij mijn allereerste som?