Mattegåta
Fredrik och Mona har 1999 kronor i kontanter tillsammans och ingen av dem har några tjugolappar (de har alltså bara valörerna 1, 5, 10, 50, 100, 500, 1000 kronor). Fredrik ska köpa grisen i säcken av Mona och Mona tar inte kort. Grisen i säcken kostar ett helt antal kronor och det är inte mer än vad Fredrik har i cash.
Visa att Fredrik garanterat kan köpa grisen i säcken och få rätt summa i växel.
Diskussion
Det har kommit in två lösningar, som är ganska olika. Den första lösningen undersöker vad det kan finnas för valörer och sammanfattar allting i ett enda fall. Den andra lösningen säger inget om de konkreta valörerna, utan baserar sig på induktion. Välj själva vilken ni tycker bäst om!
Lösning 1 (av Erik Svensson)
Antag att Mona och Fredrik, av till synes måhända besynnerliga skäl, beslutar att Mona först av allt lånar ut alla sina pengar till Fredrik. Då vet vi att Fredrik har totalt 1999 kronor, och att han nu ska betala till Mona en viss summa pengar, som är summan av grispriset och pengarna han just lånat. Denna summa överstiger inte 1999 kronor, eftersom grisen kostade högst det Fredrik hade från början, vilket tillsammans med Monas pengar alltså blir högst den totala mängden pengar i rörelse, dvs 1999 kr.
Vi har därmed reducerat problemet till att handla om huruvida Fredik kan skriva varje tal under 2000 som en summa av de kontantvalörer som finns tillgängliga.
Låt oss studera fallet där Fredik har så många stora valörer som möjligt. Vi noterar att om han klarar det i det fallet, så går det även i alla andra fall, ty att byta ut en stor valör mot flera mindre kan uppenbart inte reducera antalet möjliga summor.
Fallet med maximala valörer är att Fredik innehar följande kontanter:
1x 1000 kr
1x 500 kr
4x 100 kr
1x 50 kr
4x 10 kr
1x 5 kr
4x 1 kr
Det är lätt att visa att varje tal under 2000 kan skrivas som en summa av ovanstående valörer. Varje tal 1-9 kan ju skrivas med bara enkronor för talen 1-4, med en femkrona för 5 och med en femkrona och resten enkronor för 6-9. På exakt samma sätt kan varje tiotal upp till hundra nås, och inom varje sånt tiotal kan vi nå varje ental med en- och femkronorna. På samma sätt kan vi även nå alla hundratal med 100- och 500-lapparna, och inom varje hundratal når vi varje 10-tal med 10- och 50-kronorna, och inom varje tiotal inom varje hundratal når vi varje ental med hjälp av 1- och 5-kronorna. Därmed kan varje tal upp till 1000 skrivas. Och vill vi ha varje tal upp till 2000 så lägger vi bara till 1000-lappen där den behövs.
Således kommer Fredik kunna betala Mona exakt rätt mängd pengar, vilket skulle bevisas.
Lösning 2 (av Johan Björklund)
Vi gör detta med induktion. Om Fredrik har 0 kr så är grisen gratis och vi är klara.
Antag att Fredrik kan köpa grisen om Fredrik har p kronor (och griskostnaden är ≤p). Om Fredrik har p+1>0 kronor så kan han givetvis köpa den om grisen är gratis. Om den inte är gratis så försöker han betala en krona.
Antag att den lägsta valören Fredrik har är m. Då gäller att 1999≡m-1 (mod m) då alla valörer delar 2000. Då varje valör delar ”nästa” valör så måste det då vara så att det finns m-1 kronor i lägre valörer (fördelat mellan Mona och Fredrik).
Men då Fredrik hade lägsta valör m så måste alla de m-1 kronorna tillhöra Mona. Om Fredrik ger sin m-sedel till Mona och får de m-1 kronorna tillbaka så har han p kronor kvar och har betalat av 1 krona på grisen, dvs vi är i det tidigare lösta fallet. Induktion ger att han alltid kan betala.