växel – Mattebloggen

Lösningen till problemet för de yngre vecka 47

Mattegåta

I ett visst spel används mynt som är värda 1, 15 och 50 Hello Kitty-dollar. En spelare köpte ett svärd och fick i växel ett mynt fler än vad han betalade. Vilket är det minsta antalet dollar som svärdet kunde kosta?

Diskussion

Vid en första anblick verkar det vara konstigt varför 50 dollar-myntet överhuvudtaget är viktig för uppgiften. Det verkar ju rimligt att försöka handskas med så få mynt som möjligt, det vill säga betala med 15 dollar och få två stycker 1 dollar-mynt tillbaka. Det skulle ge priset 13 dollar.

Men det är inte säkert att det är det absolut minsta priset! Tänk på hur det kan bli om spelaren betalar med två mynt och får tre mynt tillbaka. Till exempel kan han betala 1+50 dollar och få 15+15+15 tillbaka. Och då kostar ju svärdet 6 dollar, vilket redan är lägre!

Då kanske det går att få ner priset ännu mer? Nu får vi ta och resonera ordentlig om hur betalningen kunde sett ut. Till exempel verkar det onödigt om spelar betalar med några 15 dollar-mynt och får också några tillbaka, det skapar bara onödig växling. Alltså kan vi reducera till fallen då mynt av olika sort var betalt respektive växel.

Vad finns det då för varianter? Som i exemplet ovan så går det att betala med 1 och 50 dollar-mynt och få bara 15 dollar-mynt tillbaka. I lösningen nedan ser vi att det inte blir fler signifikanta fall än så.

Lösning 1

Vi kan räkna med att spelaren betalade med några sorter mynt och fick bara andra sorter tillbaka i växel.

-Han kunde betala med valutorna på 1 och 15 dollar, och få bara 50 dollar-mynt tillbaka, men då skulle han få tillbaka mer än vad han betalade (eftersom han fick ett fler mynt i växel).
-Han kunde betala med valutorna på 15 och 50 dollar, och få bara 1 dollar-mynt tillbaka, men då skulle svärdet kosta åtminstone 13 dollar.
-Signifikant fall I. Han kunde betala med valutorna på 1 och 50 dollar, och få bara 15 dollar-mynt tillbaka.
-Han kunde betala med 1 dollar-mynt, och få bara 15 och 50 dollar-mynt tillbaka, men då skulle han få tillbaka mycket mer än vad han betalade.
-Han kunde betala med 50 dollar-mynt, och få bara 1 och 15 dollar-mynt tillbaka, men då skulle svärdet kosta åtminstone 20 dollar.
-Signifikant fall II. Han kunde betala med 15 dollar-mynt, och få bara 1 och 50 dollar-mynt tillbaka.

Om det är signifikant fall I, antag att han betalade a stycken 1 dollar-mynt och b stycken 50 dollar-mynt. Då fick han a+b+1 stycken 15-dollar mynt tillbaka. Då kan vi uttrycka priset:

a*1+b*50-(a+b+1)*15=priset

a*1+b*50-a*15-b*15-15=priset

b*35-a*14=priset+15

Notera att vänsterledet är delbart med 7, så högerledet måste vara det också. Så det minsta talet högerledet kan vara är 21, alltså är minsta priset i det här fallet 6 Hello Kitty dollar!

Om det är det signifikanta fallet II får vi i princip samma ekvation om vi antar att spelaren fick tillbaka a stycken 1 dollat-mynt och b stycken 50 dollar-mynt (då betalade han a+b-1 stycken 15 dollar-mynt). Även där blir minsta svaret 6 dollar.

Så 6 Hello Kitty dollar är det minsta svärdet kunde kosta! Det kunde ske genom att spelaren betalade 50 dollar och 1 dollar och fick tillbaka tre mynt värda 15 dollar var.

Lösning 2

Lösning 1 ger en idé till en annan lösning. Idén handlar om att delbarhet med 7 är intressant. Talen 1, 15 och 50 ger alla nämligen rest 1 vid division med 7.

Så om vi kollar hur mycket det blir kvar när vi tar bort så mycket sjuor som möjligt både från betalningen och växeln, så blir resten alltid 1 större för växeln (eller om betalningen hade rest 6 vid division med 7 kommer växeln att inte ge någon rest alls).

Svärdet ska kompensera för den skillnaden. Eftersom svärdets pris ska adderas till växeln för att få betalningen, måste priset ge rest 6 vid division med 7. Det minsta sådana talet är 6.

Matteproblem för de yngre vecka 47

Mattegåta

Lösningen till problemet för de äldre vecka 37

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.

Matteproblem för de äldre vecka 37

Mattegåta

Visa att Fredrik garanterat kan köpa grisen i säcken och få rätt summa i växel.