Een klassieke combinatorische puzzel

Het is een klassieke puzzel van Edsger Dijkstra . Zonder het originele probleem te citeren maar het in tas en ballen te veranderen, is de puzzel:

Een tas bevat enkele zwarte en witte ballen. Het volgende proces moet zo lang mogelijk worden herhaald (ervan uitgaande dat we een oneindige voorraad zwarte en witte ballen hebben).

     
      
  • Selecteer willekeurig twee ballen uit de zak. Als ze dezelfde kleur hebben, gooi ze weg, maar plaats een extra zwarte bal erin.
  •   
  • Als ze uit verschillende kleuren bestaan, plaatst u de witte terug in de zak en gooit u de zwarte weg.
  •   

Zoals je kunt zien, reduceert elke iteratie van het proces het aantal ballen in de zak met één. Ook moet herhaling van het proces eindigen met exact één bal in de zak. De vraag is:

Wat, als er iets is, kan worden gezegd over de kleur van de definitieve bal op basis van het aantal witte ballen en het aantal zwarte ballen dat aanvankelijk in de tas was.

14
toegevoegd de auteur Tritium21, de bron
@f '' Je zou kunnen zeggen dat deze puzzel is ook een mogelijk duplicaat, maar ik heb geprobeerd origineel te blijven door de auteur van de puzzel te plaatsen en je kunt de reacties op het geaccepteerde antwoord lezen dat het uit een goed boek kwam :)
toegevoegd de auteur Erin Beierwaltes, de bron
@f '' Deze vraag is beter dan de mogelijk duplicaat : It geeft de bron van de puzzel, het is meer algemeen, beter geformuleerd ...
toegevoegd de auteur Jawad Al Shaikh, de bron

1 antwoord

Wat kan gezegd worden is dat

de pariteit van het aantal witte ballen verandert nooit. Daarom, als er aanvankelijk een oneven aantal witte ballen is, moet de laatste bal in de zak wit zijn; als een even getal is, moet de laatste bal zwart zijn.

De manier waarop de puzzel wordt vermeld is, denk ik, opzettelijk onduidelijk. Je zou op gelijkwaardige (en transparantere) manier kunnen zeggen: bij elke stap verwijder je een zwarte bal, of verwijder je twee witte en voeg je een zwarte toe . Dit maakt het ook een beetje meer expliciet dat

bij elke stap verandert de pariteit van het aantal zwarte ballen , wat natuurlijk moet omdat je telkens één bal verwijdert en de witte pariteit onveranderlijk is.

(Natuurlijk zijn de twee uitspraken niet helemaal hetzelfde als je om een ​​of andere reden geeft om waarschijnlijkheden, omdat je in de originele versie twee ballen willekeurig verwijdert en laat dat bepalen welke van de twee dingen je doet, maar de puzzel zelf is alleen geïnteresseerd in het slechtste geval.)

17
toegevoegd
Eigenlijk heb ik iets veranderd in tas en iets in ballen :)
toegevoegd de auteur Erin Beierwaltes, de bron
Hoe dan ook, je antwoord is absoluut correct. Het oorspronkelijke probleem heet The coffee can problem , ik las het in een boek genaamd Science of Programming van David Gries. Bekijk ook deze vraag .
toegevoegd de auteur Erin Beierwaltes, de bron
Ja, ik gaf je de schuld niet voor de verduistering van de vraag. Het is de schuld van Dijkstra.
toegevoegd de auteur Pankaj, de bron
En Gries's boek is erg leuk.
toegevoegd de auteur Pankaj, de bron
Programmeer vraag: oh, dat is grappig.
toegevoegd de auteur Pankaj, de bron