Combinaties (geldige) Torens van Hanoï

[puzzelmans]

Hallo,

Ben op zoek naar:

- dé formule voor het bepalen van het aantal mogelijke "opstellingen" met n (voor de eenvoud: 1 <= n <= 9) schijven (van verschillende diameter) verdeeld over drie stapels;

- idem voor het aantal "geldige" van deze opstellingen, waarbij dus nooit een grotere schijf bovenop een kleinere ligt;

- bij uitbreiding: de bepaling van het aantal "geldige" binnen de verzameling van mogelijke "oplossingen", mits het toepassen van één (of meer) eenvoudige(?) regel(s);

- bij gebrek hieraan, een - liefst eenvoudige - methode (algoritme) om de "geldige" deelverzameling te bepalen, bij voorkeur niet met "brute force", eventueel via bactracking;

Mvg,

Puzzelmans

[Jaimy11]

Hallo,

Ben op zoek naar:

- dé formule voor het bepalen van het aantal mogelijke "opstellingen" met n (voor de eenvoud: 1 <= n <= 9) schijven (van verschillende diameter) verdeeld over drie stapels;

- idem voor het aantal "geldige" van deze opstellingen, waarbij dus nooit een grotere schijf bovenop een kleinere ligt;

- bij uitbreiding: de bepaling van het aantal "geldige" binnen de verzameling van mogelijke "oplossingen", mits het toepassen van één (of meer) eenvoudige(?) regel(s);

- bij gebrek hieraan, een - liefst eenvoudige - methode (algoritme) om de "geldige" deelverzameling te bepalen, bij voorkeur niet met "brute force", eventueel via bactracking;

Mvg,

Puzzelmans

De formule is heel eenvoudig:

H(n)=2H(n-1)+1

Met:

H(n)= Toren met n schijven

H(n-1)= Toren met n-1 schijven

Wat wil je met de rest bereiken?

Ps. Uiteraard met H(1)=1

[puzzelmans]

Bedankt voor je antwoord, maar is dat niet de formule voor het (minimaal) aantal benodigde stappen om een toren van n schijven te verplaatsen naar een andere positie? Zonder recursie ook te berekenen als H(n) = 2^n - 1 ?

Wat ik graag zou weten is: op hoeveel manieren kan ik n schijven verdelen over 3 stapels (extra: wanneer de "volgorde" van de stapels al dan niet belangrijk is) ? En: hoeveel van deze "verdelingen" zijn "geldig" als "Hanoï-opstelling" ?

Het zou leuk zijn als ook het antwoord op de tweede vraag niet proefondervindelijk moet worden vastgesteld...

Mvg,

Puzzelmans

[tempelier]

Willekeurig is vrij gemakkelijk te vinden.

Stapel alles op eerste van de torens en kijk op hoeveel manieren dat kan.

Je kunt nu deze stapel in drie lagen verdelen de bovenste verplaats je naar een tweede toren met behoud van de volgorde en vervolgens de middelste laag naar de derde toren kijk nu op hoeveel manieren dit kan.

Zo' n laag kan natuurlijk leeg zijn.

Nu is het nog niet geheel klaar het hangt er nu van af wat er als verschillend gezien wordt.

Dus of het omwisselen van twee torens wel of niet als een verschillende mogelijkheid wordt gezien.

[puzzelmans]

Bedankt voor de tip !

Ik had echter gehoopt dat er een formule zou bestaan, i.p.v. een proefondervindelijke methode... Misschien zit die wel in de beschrijving verstopt: voor stap 1 zou dat m.i. het aantal permutaties van n elementen zijn, m.a.w. P(n) ofwel n!

Maar dan krijg ik het al moeilijk: op hoeveel manieren kan ik deze n elementen over 3 stapels verdelen, waarbij elke stapel benoemd is (dus de "volgorde" van de stapels is belangrijk), en van 0 tot n elemente mag bevatten ?

Ik vermoed dat de volgorde van de elementen per stapel niet belngrijk is in deze stap, omdat hiermee wel rekening gehouden is in de vorige... Tenzij je natuurlijk stap 1 overslaat, en bij het verdelen in stapels dus wél rekening houdt met de volgorde per stapel. Hmm... Help!

[kee]

Is dat geen herhalingscombinatie voor het tweede deel?

[kee]

- idem voor het aantal "geldige" van deze opstellingen, waarbij dus nooit een grotere schijf bovenop een kleinere ligt;

Variatie, herhalingsvariatie, combinatie, herhalingscombinatie. Welk van de vier ga je hiervoor gebruiken...

[tempelier]

Bedankt voor de tip !

Ik had echter gehoopt dat er een formule zou bestaan, i.p.v. een proefondervindelijke methode... Misschien zit die wel in de beschrijving verstopt: voor stap 1 zou dat m.i. het aantal permutaties van n elementen zijn, m.a.w. P(n) ofwel n!

Maar dan krijg ik het al moeilijk: op hoeveel manieren kan ik deze n elementen over 3 stapels verdelen, waarbij elke stapel benoemd is (dus de "volgorde" van de stapels is belangrijk), en van 0 tot n elemente mag bevatten ?

Ik vermoed dat de volgorde van de elementen per stapel niet belngrijk is in deze stap, omdat hiermee wel rekening gehouden is in de vorige... Tenzij je natuurlijk stap 1 overslaat, en bij het verdelen in stapels dus wél rekening houdt met de volgorde per stapel. Hmm... Help!

Die formule is er dus maar je moet hem wel afleiden.

Die stapels verdelen is ook niet zo moeilijk af te leiden zie het als twee snijvlakken die precies tussen twee schijven moeten worden aangebracht.

[puzzelmans]

Die formule is er dus maar je moet hem wel afleiden.

Die stapels verdelen is ook niet zo moeilijk af te leiden zie het als twee snijvlakken die precies tussen twee schijven moeten worden aangebracht.

Best grappig, ik had ook al zitten denken over één of andere metafoor, de plakjes/worst was er één van, maar echt geholpen heeft het toen niet... 't Is te lang geleden dat ik dit op school leerde en/of nog toepaste.

Nog maar eens proberen: hoe verdeel ik n plakjes over drie stapeltjes waarbij elk stapeltje 0 tot n plakjes mag bevatten? Volgens mij heb ik n+1 mogelijke "snij-vlakken", voor(bij) de uiteinden telt ook. Ook mogen de beide "gebruikte snij-vlakken" samenvallen. En dan val ik weer stil... Misschien moet ik toch maar eens eerst de theorie opfrissen?

[tempelier]

Je kunt het ook ander oplossen, misschien wel zo makkelijk.

Haal alle schijven van de torens, pak nu een willekeurig schijf en plaats die op een toren.

Dat geeft 3*n mogelijkheden

Pak daarna weer een schijf er zijn er dan (n-1) ovder en plaats die op een willekeurige toren enz.

[kee]

Nochtans ben je er zo wel hoor. Herinner je je een herhalingscombinatie uit de theorie?

Je hebt n+1 mogelijke snijvlakken.

Je kiest er 2 uit.

De gebruikte snijvlakken mogen samenvallen.

Dus:

Je kiest 2 keer uit n+1 met herhaling (gezien de snijvlakken mogen samenvallen). De volgorde waarin je de 2 snijvlakken kiest maakt niet uit (kies je eerst de ene, dan de andere, of maak je dezelfde keuze omgekeerd, dan is dit dezelfde opdeling). Een herhalingscombinatie dus.

Daarnaast voor je tweede punt: Heb je het antwoord voor de geldige opstellingen? Welk van de vier is hier geschikt?

[kee]

Je kunt het ook ander oplossen, misschien wel zo makkelijk.

Haal alle schijven van de torens, pak nu een willekeurig schijf en plaats die op een toren.

Dat geeft 3*n mogelijkheden

Pak daarna weer een schijf er zijn er dan (n-1) ovder en plaats die op een willekeurige toren enz.

Dit gaat niet werken. Je telt je mogelijkheden meer dan één keer.

[kee]

Daarnaast voor je tweede punt: Heb je het antwoord voor de geldige opstellingen? Welk van de vier is hier geschikt?

Een tip om het te zien: verdeel je schijven in drie stapels, een stapel voor de toren links, een stapel voor de middelste toren, een stapel voor de rechtse toren (mogen ook "lege stapels" zijn). Met elk zo'n verdeling van je schuiven komt precies één geldige opstelling overeen, namelijk de drie stapels geordend van groot naar klein.

[tempelier]

Dit gaat niet werken. Je telt je mogelijkheden meer dan één keer.

Klopt ja mijn metode deugt niet.

[puzzelmans]

Nochtans ben je er zo wel hoor. Herinner je je een herhalingscombinatie uit de theorie?

Je hebt n+1 mogelijke snijvlakken.

Je kiest er 2 uit.

De gebruikte snijvlakken mogen samenvallen.

Dus:

Je kiest 2 keer uit n+1 met herhaling (gezien de snijvlakken mogen samenvallen). De volgorde waarin je de 2 snijvlakken kiest maakt niet uit (kies je eerst de ene, dan de andere, of maak je dezelfde keuze omgekeerd, dan is dit dezelfde opdeling). Een herhalingscombinatie dus.

Bedankt voor deze - onontbeerlijke - tip !!!

Zo had ik het namelijk nog niet bekeken, d.w.z. vanuit de snijvlakken i.p.v. de schijven...

Mijn eerste "indruk" was evenwel dat hier enkele randgevallen (ten onrechte) herhaald zouden worden bij de te "telling"... Na enige bezinning heb ik mijn mening herzien, maar dat is (mede) de verklaring voor deze ietwat late reactie.

Mvg,

Puzzelmans