Probleem van een Olympiabeheerder
Opgave - BxMO 2018 dag 1 vraag 2
In het land Heptanomisma worden vier verschillende munten en drie verschillende bankbiljetten gebruikt; hun waardes zijn zeven verschillende (strikt) positieve gehele getallen.
De waarde van het kleinste bankbiljet is (strikt) groter dan de som van de waardes van de vier verschillende munten.
Een toerist in het bezit van precies één munt van elke waarde en precies één bankbiljet van elke waarde kan het boek over numismatologie dat hij wil kopen, niet betalen.
De wiskundig georiënteerde boekhandelaar vertelt de toerist echter dat hij het boek mag kopen voor een prijs naar keuze, mits hij deze prijs op meerdere manieren kan betalen.
(De toerist kan een prijs op meerdere manieren betalen als er twee verschillende deelverzamelingen van zijn munten en bankbiljetten zijn die elk evenveel waard zijn als deze prijs.)
Bewijs dat de toerist het boek kan kopen als de waarde van elk bankbiljet (strikt) kleiner dan $49$ is.
Bewijs dat het zou kunnen dat de toerist met lege handen de boekwinkel moet verlaten als de waarde van het grootste bankbiljet $49$ is.
- login om te reageren
Oplossing
Oplossing voor b)
We bewijzen $3,6,12,24,47,48,49$ een configuratie is.
Merk namelijk op dat $47$ het enige getal $2 \pmod 3$ is en $49$ het enige getal $1 \pmod 3$.
Stel dat er 2 disjuncte (gelijke elementen verwijderd) verzamelingen $A$ en $B$ zijn met gelijke som.
Daar hun som gelijk is modulo $3$, betekent dit dat $47,49$ of beide voorkomen in dezelfde verzameling, of niet.
We bekijken nu deze 2 gevallen.
1) De verzameling $A$ bevat zowel $47$ als $49$.
Dan is de som van elementen in $B$ hoogstens $q 3+6+12+24+48 = 93$ en dat is kleiner dan $47+49$, dus de $2$ verzamelingen kunnen niet dezelfde som hebben.
2)
Merk op dat $3,6,12,24,48 = 3 \cdot 1, 3 \cdot 2, 3 \cdot 4, 3 \cdot 8, 3 \cdot 16$.
Na alle elementen van $A$ en $B$ te delen door $3$, krijgen we $1,2,4,8,16$ als getallen. Aangezien elk getal uniek te schrijven is in het binair stelsel, kunnen A en B geen gelijke som hebben.
We concluderen dus dat er een voorbeeld is waarbij de toerist het boek niet op 2 manieren kan betalen bij deze configuratie.