combinatoriek met emmers
Opgave - IMOSL 2009 dag 1 vraag 12
$5$ Lege emmers met een inhoud van $2$ liter staan op de hoekpunten van een regelmatige vijfhoek. Assepoester en haar boze stiefmoeder voeren afwisselend een stap uit. De stiefmoeder mag bij haar stap telkens $1$ liter water verdelen over de $5$ emmers zoals ze wil. Daarna mag Assepoester $2$ emmers die naast elkaar staan kiezen en ledigen. Indien een emmer kan overlopen door de stiefmoeder wint ze, in het andere geval Assepoester, wie heeft een winnende strategie?
- login om te reageren
Oplossing
$1$ emmer kan steeds in 1 stap geleegd worden
$2, 3$ of $4$ emmers kunnen steeds in $2$ stappen geleegd worden (of soms in $1$ stap igv $2$)
$5$ emmers kunnen steeds in $3$ stappen geleegd worden
Indien er vlak na een stap van assepoester meer dan $1$ liter zit in een emmer, wint de stiefmoeder.
Als assepoester steeds de volste emmer leegmaakt samen met de volste aangrenzende emmer en bij $2$ even volle emmers kijkt met welke emmer er in het totaal het meeste kan weggegoten worden (dus m.a.w. de emmer pakt waarnaast het meeste water in $1$ emmer staat) (bij een gelijke situatie wordt een willekeurige emmer geleegd), kan stiefmoeder niet winnen.
Om te winnen, moet stiefmoeder dus zorgen dat $2$ mekaar niet rakende emmers na haar beurt meer dan $1$ liter bevatten, om de eerder gestelde voorwaarde te kunnen volbrengen. Om dit mogelijk te maken, zouden ze de beurt ervoor meer dan $0,5l$ moeten bevat hebben. Dit betekent dan weer dat ze al minstens $2$ keer bijgevuld zijn op dat moment en dat ze op dat moment niet de volste emmers zijn, gezien dat zeker zou betekenen dat $1$ ervan geleegd wordt. Als een andere emmer echter voller is, grenst deze zeker aan één van de $2$ emmers die we eerder noemden, wat betekent dat, tenzij er nog een emmer voller is dan deze $2$ en rakend aan onze derde emmer, er toch $1$ van de $2$ leeggemaakt wordt (en er dus weer maar $1$ boven de $0,5l$ zit). Op deze manier moeten minstens $4$ emmers meer dan $0,5$ liter bevatten in dezelfde beurt. Deze kunnen echter niet op $1$ beurt gevuld zijn en per beurt worden er $2$ emmers geleegd, waardoor het onmogelijk is om deze 4 met de nodige vulling te bereiken (het maximum is $3$ boven de $0,5$ op eenzelfde moment). Als we dan onze redenering terug naar boven volgen, betekent dit met zekerheid dat assepoester zal winnen met de voorgestelde strategie.
***
Met wat hierboven staan, kan een elegantere oplossing worden geschreven waarbij we niet te ver terug moeten denken:
"Om te winnen, moet stiefmoeder dus zorgen dat $2$ mekaar niet rakende emmers na haar beurt meer dan $1$ liter bevatten"
We kunnen Assepoester laten zorgen dat de 2 niet rakene emmers samen minder dan $1$ liter bevatten alsook de derde.
***
elegante oplossing:
Assepoester kan altijd winnen door te zorgen voor het volgende:
$ABCDE$ is de vijfhoek in volgorde en schrijven $X$ voor de inhoud op die plaats in letters.
Na herorienteren, zorgt ze dat $A,E$ leeg zijn, de som van de inhouden in $B,D$ $\le 1$ en $C\le.$
Na een stap van de heks, ledigt Assepoester $B,C$ of $D,C$. Er geldt dat $A,E<1$ en $B+E$ en/of $A+D<1$ aangezien $A+B+E+D<1+1=2$ en het duivenhokprincipe, zodat $1$ van de $2$ koppels emmers ledigen voldoet. De overstaande emmer bevat dus terug max. $1$ liter, daar de heks een lege emmer niet met meer dan $1$ liter kan bijvullen.
De som van de $2$ buren is ook maximaal $1$ liter.
Aangezien bij de start aan de voorwaarde voldaan is, kan ze dit principe volhouden en wint Assepoester.