Algebra

Analyse

Bewijzen

De grafische rekenmachine

Discrete wiskunde

Fundamenten

Meetkunde

Oppervlakte en inhoud

Rekenen

Schoolwiskunde

Statistiek en kansrekenen

Telproblemen

Toegepaste wiskunde

Van alles en nog wat


\require{AMSmath}

Dinertje

Ik heb het volgende vraagstuk over mezelf afgeroepen. Het betreft een bijzonder dinertje:

Ik (A) nodig 3 gasten uit, vriendin B doet hetzelfde, en vriend C ook. Ieder ontvangt zijn eigen gasten voor een aperitief. Daarna vertrekken 2 gasten naar een andere locatie voor het voorgerecht. Vervolgens wordt er weer gewisseld voor het tussengerecht en ook het hoofdgerecht.

Eigenlijk zijn er dus 4 rondes te gaan. Maar na 2 rondes loopt het al spaak: het liefst zou ik willen, dat mensen niet meer dan 1x bij dezelfde personen aan tafel zitten. En, alle gasten moeten op de verschillende locaties komen.

Is dit een vraag die wiskundig valt op te lossen?

Cees l
Iets anders - maandag 9 januari 2023

Antwoord

We kunnen het vraagstuk systematisch aanpakken door een negenhoek te tekenen, zie de figuur hieronder. De hoekpunten stellen de gasten voor. De gasten van persoon A noem ik A1, A2 en A3. De gasten van persoon B zijn dan B1 t/m B3, zo ook de gasten C1 t/m C3. Door steeds verbindingen te tekenen tussen drie hoekpunten kunnen we aangeven welke drie gasten bij elkaar aan tafel zitten.

q97510img1.gif

In de linker figuur zien we dat de gasten van persoon A, B en C in de eerste ronde inderdaad bij elkaar aan tafel zitten. Door systematisch andere driehoeken te tekenen, vinden we combinaties van gasten, zodanig dat elke gast één keer met elke andere gast aan tafel zit. Dit lukt precies in 4 rondes (de 4 negenhoeken hierboven). Uitgeschreven is dit:

Ronde 1:
Groep 1: A1 A2 A3
Groep 2: B1 B2 B3
Groep 3: C1 C2 C3

Ronde 2:
Groep 1: A1 B2 C3
Groep 2: A2 B3 C1
Groep 3: A3 B1 C2

Ronde 3:
Groep 1: A1 B1 C1
Groep 2: A2 B2 C2
Groep 3: A3 B3 C3

Ronde 4:
Groep 1: A1 B3 C2
Groep 2: A2 B1 C3
Groep 3: A3 B2 C1

Nu willen we ook dat alle gasten alle locaties een keer bezoeken. De locaties kunnen we aangeven door de drie driehoeken in elke ronde een specifieke kleur te geven: rood, blauw en groen. Als we de gasten A1, B1 en C1 na de eerste ronde doorschuiven in de richting rood- $>$ blauw- $>$ groen- $>$ rood, dan zien we dat gasten A3, B3 en C3 in tegenovergestelde richting draaien. De gasten A2, B2 en C2 blijven zitten.

In ronde 3 moet A1 naar locatie groen. Ook B1 en C1 komen hiermee op locatie groen. A2 is al twee keer rood geweest en moet dus doorschuiven. Groen is al bezet, dus A2 gaat naar blauw. Hiermee komen B2 en C2 ook op blauw. Voor rood blijven dan over A3, B3 en C3.

Echter, hiermee is onvermijdelijk dat B2 al drie keer op locatie blauw zit. In de laatste ronde kan deze gast naar groen of rood, maar één locatie kan hij niet bezoeken.

De conclusie is dus:

Het is wel mogelijk dat alle gasten minstens één keer met elke andere gast aan tafel zit (het wordt zelfs precies één keer), maar hierbij kan niet elke gast ook elke locatie minstens één keer bezoeken.

Opmerkingen:
  • De keuzes om bv A1 drie keer te laten doorschuiven lijkt een inperking van mogelijkheden, maar door verwisselen en/of spiegelen van gasten en/of figuren kunnen andere keuzes toch worden teruggebracht tot deze keuzes.
  • Dit type probleem wordt het 'social golfer problem' genoemd, zie bv. Math Games: Social Golfer Problem. Op het internet vind je een online calculator om oplossingen te genereren.

GHvD
woensdag 11 januari 2023

©2001-2024 WisFaq