Moordenaars

Ik heb eigenlijk een telprobleem, maar daar ging iets mis dus vraag ik het hier.

stel ik heb 4 moordenaars. en 10 cellen op een rijtje. Ik wil de moordenaars in de cellen doen, maar er is 1 voorwaarde dat ze niet naast elkaar in een cel mogen want dan vermoorden ze elkaar meteen.

vraag: hoeveel mogelijke indelingen heb ik als de volgorde waarin de moordenaars staan er niet toe doet. dus a,b,c,d = c,d,b,a

ik stel het me als volgt voor. tussen de cellen maak ik een duidelijke dikke scheidingslijn zodat de volgende indeling mogelijk is.
0= gevangene 1 = scheidingslijn

0110111011110 de vraag is denk ik te vertalen naar. hoeveel van dit soort "codes"zijn mogelijk zonder 2 nullen naast elkaar? Dit betekent dan ook dat er elke keer minstens 2 streepjes naast elkaar moeten. verder kom ik eigenlijk niet?

graag uw inzicht!

dennis
Student hbo - donderdag 10 januari 2013

Antwoord

Het werken met scheidingswanden is inderdaad zo gek nog niet.
Eerst kijken we even naar een telprobleem dat zich in de beantwoording van je vraag voordoet.
Je kent vast wel vragen zoals 'hoeveel woorden kun je maken met de letters van het woord banaan?"
De telling loopt dan als volgt: de 6 letters kun je op 6! door elkaar haspelen (permuteren) dus zijn er in eerste instantie 6! = 720 woorden.
Onderlinge verwisseling van de a's levert echter geen nieuw woord op. Die 3 a's laten zich op 3! = 6 manieren permuteren en daarom zijn er 6!/3! = 120 woorden.

Nu de aanpak met scheidingswanden.
Stel je hebt 5 vakjes en 3 identieke knikkers. Op hoeveel manieren kunnen de knikkers over de vakjes worden verdeeld?
Deze telling kan als volgt verlopen.
De 5 vakjes kun je weergeven d.m.v. 4 scheidingswanden met daar ergens tussenin 3 letters k.
Zo'n verdeling zou bijv. kunnen zijn k | |kk | | of
| | k | k | k
Je ziet dat er steeds 7 symbolen op een rij staan, namelijk 4 streepjes (de scheidingswand) en 3 letters k (de knikkers).
Op de manier van het banaan-voorbeeld kun je deze 7 symbolen op 7! manieren rangschikken maar onderlinge verwisseling van de streepjes of de letters levert niets nieuws op.
In totaal zijn er dus 7!/(3!.4!) = 35 manieren.

Ten slotte je vraag.
Zet de 4 moordenaars m naast elkaar. Dus m m m m
Tussen deze kooien moet in ieder geval één lege kooi L komen. Zet er dus één L tussen.
Je hebt nu dus m L m L m L m
Je had 10 kooien dus er zijn er nog 3 over. Die 3 kun je verdelen zoals je wilt. Daarvoor heb je 5 vakken (net als in telprobleem 2). Er zijn dus 35 manieren in totaal.

Dit zijn ze:

{m, L, m, L, m, L, m, L, L, L}, {m, L, m, L, m, L, L, m, L, L},
{m, L, m, L, m, L, L, L, m, L}, {m, L, m, L, m, L, L, L, L, m},
{m, L, m, L, L, m, L, m, L, L}, {m, L, m, L, L, m, L, L, m, L},
{m, L, m, L, L, m, L, L, L, m}, {m, L, m, L, L, L, m, L, m, L},
{m, L, m, L, L, L, m, L, L, m}, {m, L, m, L, L, L, L, m, L, m},
{m, L, L, m, L, m, L, m, L, L}, {m, L, L, m, L, m, L, L, m, L},
{m, L, L, m, L, m, L, L, L, m}, {m, L, L, m, L, L, m, L, m, L},
{m, L, L, m, L, L, m, L, L, m}, {m, L, L, m, L, L, L, m, L, m},
{m, L, L, L, m, L, m, L, m, L}, {m, L, L, L, m, L, m, L, L, m},
{m, L, L, L, m, L, L, m, L, m}, {m, L, L, L, L, m, L, m, L, m},
{L, m, L, m, L, m, L, m, L, L}, {L, m, L, m, L, m, L, L, m, L},
{L, m, L, m, L, m, L, L, L, m}, {L, m, L, m, L, L, m, L, m, L},
{L, m, L, m, L, L, m, L, L, m}, {L, m, L, m, L, L, L, m, L, m},
{L, m, L, L, m, L, m, L, m, L}, {L, m, L, L, m, L, m, L, L, m},
{L, m, L, L, m, L, L, m, L, m}, {L, m, L, L, L, m, L, m, L, m},
{L, L, m, L, m, L, m, L, m, L}, {L, L, m, L, m, L, m, L, L, m},
{L, L, m, L, m, L, L, m, L, m}, {L, L, m, L, L, m, L, m, L, m},
{L, L, L, m, L, m, L, m, L, m},

MBL
zondag 13 januari 2013

©2001-2024 WisFaq