Wiskundemeisjes

Ionica & Jeanine
 
Slik Internetbureau Rotterdam Internetbureau Rotterdam



Categorieën

Archief

Een gemene gastheer


In Leestip,Puzzels, door Ionica

Op een conferentiediner moeten 48 mannelijke wiskundigen -geen van allen op de hoogte van tafel-etiquette- een grote, ronde tafel delen. De tafel is al gedekt en tussen elke twee borden ligt een servet. De gastheer plaatst de wiskundigen één voor één. Zodra een wiskundige gaat zitten, pakt hij een servet links of rechts van zijn bord. Als er aan elke kant nog een servet ligt, dan kiest hij er willekeurig één van de twee. De gastheer ziet niet welke servet de wiskundige pakt. Hoe moet de gastheer de wiskundigen neerzetten om het verwachte aantal wiskundigen zonder servet zo groot mogelijk te maken?



Het meest voor de hand liggende antwoord is niet het juiste! Deze leuke puzzel komt wederom van Peter Winkler. In zijn warm aanbevolen boek Mathematical Puzzles: A Connoisseur's Collection vertelt Winkler de oorsprong van deze puzzel.

This problem can be traced to a particular event. Princeton mathematician John H. Conway came to Bell Labs on March 30, 2001 to give a “General Research Colloquium.” At lunchtime, [Winkler] found himself sitting between Conway and computer scientist Rob Pike (now of Google), and the napkins and coffee cups were as described in the puzzle. Conway asked how many diners would be without napkins if they were seated in random order, and Pike said: “Here’s an easier question—what’s the worst order?”

De vraag van Conway is trouwens echt een stuk moeilijker!

15 reacties op “Een gemene gastheer”

  1. Anthony:

    Ik zal als eerste reageren- jullie hebben in ieder geval al één persoon enthousiast gemaakt, ik heb zojuist zowel dit boek als z'n opvolger besteld voor nog geen 35 euro. Ben nu toch wel erg benieuwd naar de oplossing van het probleem met de gevangenen dat in die link genoemd wordt!

    Tony

  2. Vincent:

    Wacht even, mag de gastheer bepalen wie waar zit, of in welke volgorde de mensen gaan zitten? In het eerste geval moet je toch iets meer weten over wie links- of rechtshandig is of wie een hekel heeft aan wie...

  3. Ionica:

    De gastheer plaatst de wiskundigen, dus hij wijst echt aan op welke stoel ze moeten zitten. Over links-of rechtshandigheid maakt hij zich niet druk en hij neemt aan dat alle wiskundigen elkaar reuzeaardig vinden.

  4. Vincent:

    Ok. Ik denk dat ik het antwoord al weet, maar wat ik bedoelde is: krijgen ze allemaal van te voren een kaartje (uitnodiging of zo) waarop staat op welke stoel ze mogen gaan zitten en kunnen ze dus allemaal tegelijk naar binnen gaan, zo snel mogelijk naar hun stoel rennen en aan een servet beginnen te trekken (dat met een beetje pech hun buurman ook net beetgegrepen heeft)

    of:

    moeten ze op de avond zelf eerst een uur netjes in de rij staan om een voor een van de gastheer persoonlijk te horen te krijgen waar ze moeten gaan zitten, zodat de eerste persoon (al is het maar voor even) kan genieten van een leven zonder slechtgemanierde tafelgenoten en ongehinderd een servet kan uitzoeken?

  5. Ionica:

    Ah! Het is optie twee.

  6. Koen:

    Het lijkt me heel simpel, hij kan iedereen behalve 1 neerzetten op de goede plek.
    Zet er 1 gewoon neer, en dan de volgende telkens rechts ernaast. (Of linksom, maar ik ben rechts vandaar... :P)
    De 1e kiest een servet, rechts van hem wordt iemand neergezet. Als de 1e het servet rechts heeft gepakt kan de 2e alleen ook naar rechts pakken en de 3e (daar weer rechts van) ook. Ga je zo rond dan heeft iedereen een servet.
    Pakt de 1e het servet links van hem en wordt er rechts iemand neergezet dan kan die kiezen uit links of rechts. Kiest hij rechts dan heeft de 3e geen keus meer en kiest altijd rechts, dan blijft het servet tussen 1 en 2 over en heeft de laatste geen servet.

    Het is dus maximaal 1 persoon zonder servet, hoe groot de tafel ook is..?

  7. Marco:

    Ha Koen, let even op de titel van het stukje. Dit is een gemene gastheer en hij wil dat zoveel mogelijk mensen geen servet hebben.

  8. Koen:

    Haha... Ja, sorry hoor... :)

    De kans is het grootst dat je geen servet kunt pakken als je al 2 mensen naast je hebt, dus moet je 1 man neerzetten en dan 1 overslaan, 1 neerzetten etc. Tenminste, dat is mijn 1e gedachte...
    Ik kom er op terug... ;)

  9. Marco:

    Koen? Ik wacht...

    Ha, weer geslaagd voor de spamfiltertoets!

  10. Jan:

    Google heeft op de site books.google.nl het hele (oudste) boek online gezet. intikken op deze site volstaat: derde hit.

  11. Jan:

    Google heeft op de site books.google.nl het hele (oudste) boek online gezet. Peter Winkler puzzles intikken op deze site volstaat: derde hit.

  12. Koen:

    Marco, sorry, ik was het even vergeten!!

    Goed dan!
    Aangezien je minstens 2 mensen nodig hebt om voor een 3e persoon de servetten weg te nemen is het maximum wat toevallig zonder servet zou kunnen zitten 1/3 van het gezelschap. Ik denk dus dat er groepen van 3 gemaakt moeten worden. De gastheer moet dan om de 3 stoelen iemand neerzetten, 1 bezet, 2 leeg. In 1 rondje dus 16 wiskundigen. Dan zet hij de overgebleven plekken gewoon vol. Ik kan het alleen niet bewijzen of verder verklaren, maar in mijn probeersels lijkt dit het meest "evil".

    Jammer trouwens dat het antwoord niet na een week of wat ook op de site staat...

  13. Marco:

    Ha Koen, misschien beter dat het antwoord niet op de site staat, zo blijven we nog even doorpuzzelen! Volgens mij kan het eviller (wow, wat zou de taaltoets hiervan vinden?), maar ik heb nu geen tijd.

  14. Koen:

    Door in QBasic (jaha... programmeren old-school) een testje los te laten met 10 personen blijkt na 10000 keer testen dat de gastheer het beste de mensen om en om neer kan zetten. Maar vraag me niet waarom...
    (QBasic verhinderd mij met simpel programmeren meer dan 10 gasten te testen)

    Resultaten met 10 personen aan tafel:
    open plekken tussen de gasten - gemiddeld aantal zonder servet
    0 - 0,5
    1 - 1,25
    2 - 1,19
    3 - 1,25
    4 - 0,94

    Maar aangezien 10 niet deelbaar is door 3 ook een test voor 9 mensen aan tafel
    0 - 0,50
    1 - 1,12
    2 - 1,13
    3 - 0,90

    Marco, al meer tijd?

  15. Marco:

    Ha Koen,

    De optimale strategie blijkt wat ingewikkelder dan ik dacht, maar hier is 'ie.

    SPOILERWAARSCHUWING!!!
    Ik heb geprobeerd de spoiler-plugin te gebruiken, maar de leesbaarheid laat wat te wensen over. Zo moet je de muis apart over elke paragraaf houden en kan je maar 1 paragraaf tegelijk lezen. Daarom nu een oplossing zonder balkjes. Ik laat trouwens nog wel wat te puzzelen over. En wie weet heeft er iemand een mooier bewijs dan ik. Zo ben ik wel benieuwd naar de oplossing in het boek.

    De strategie: maak eerst een rondje met telkens 1 gast en 3 lege stoelen. Daarna een tweede ronde met naast elke gast die in de eerste ronde geplaatst is, een nieuwe gast. Nu blijft een kwart van de stoelen over, en worden de laatste gasten verdeeld.

    Ga je als gast tijdens de laatste ronde zitten, dan is er een kans van 3/4 dat het servet aan je linkerkant door je linkerbuur gepakt is. Er is namelijk een kans van 1/2 dat de eerste-ronde-gast twee plaatsen links van je naar rechts greep en een kans van 1/4 dat hij naar links greep, maar je directe linkerbuur naar rechts.
    Omdat je aan elke kant een kans van 3/4 hebt dat je servet weg is, heb je een kans van (3/4)^2=9/16 dat je de avond zonder servet moet doorbrengen.
    Dit verhaal geldt voor een kwart van de 48 gasten, dus de verwachtingswaarde van het aantal gasten zonder servet is 12*9/16=27/4.

    Maar waarom is dit optimaal? Noem een gast een Leider als hij geplaatst wordt tussen twee lege stoelen en een Laatste als hij geplaatst wordt tussen twee reeds geplaatste gasten. Voor elke Laatste is de kans dat hij zonder servet komt te zitten gelijk aan

    \[\]


    waarbij \(\) (respectievelijk \(\)) de afstand is tot de eerste Leider links (respectievelijk rechts) van hem.
    Bij iedere Laatste hoort een Groep, bestaande uit alle gasten links van hem tot en met de dichtstbijzijnde Leider aan zijn linkerkant (inclusief) en alle gasten rechts van hem tot de dichtstbijzijnde Leider aan zijn rechterkant (exclusief). Iedere gast zit dus in precies 1 Groep. De Groep horend bij een Laatste bestaat uit \(\) personen en de verwachtingswaarde van het aantal personen zonder servet in die Groep is \(\).
    Het verwachte deel mensen zonder servet in een Groep is dus

    \[\]

    Bijvoorbeeld, in een Groep met \(\) hebben gemiddeld 9 op de 64 gasten geen servet. Nu kun je laten zien dat voor alle positieve gehele getallen a en b het getal \(\) kleiner dan 9/64 is, behalve voor \(\). Bijvoorbeeld door een tabel te maken voor alle a en b van 1 tot en met 6 en door op te merken dat, als \(\) of \(\) groter is dan 6, dan geldt
    \(\).

    Conclusie: als er alleen Groepen zijn met \(\), zoals in bovenstaande strategie, dan heeft gemiddeld 9/64 deel van de gasten geen servet. Als er niet alleen Groepen zijn met \(\), dan heeft gemiddeld minder dan 9/64 deel van de gasten geen servet. Dus de bovenstaande strategie is optimaal voor de gemene gastheer.

    Dit argument werkt alleen als het aantal gasten deelbaar door 4 is en tenminste 8 is (zoals 48). Met andere aantallen gasten is een aantal uitzonderingsregels en wat meer rekenwerk nodig.

Plaats een reactie


Je kunt LaTeX gebruiken in je reactie.
Gelieve antwoorden op puzzels tussen [SPOILER] en [/SPOILER] te plaatsen.