Mattebloggen

Det finns 25 ostbitar. Går det alltid att välja en bit, skära den i två delar på så sätt att osten nu kan läggas i två kassar så att den uppskurna ostens delar hamnar i olika kassar och det finns lika många ostbitar i varje kasse och osten i kassarna väger lika mycket?

Svar:

Ja, det går faktiskt alltid att göra.

Diskussion:

Om 25 bitar är lite svårt att föreställa sig, är det klokt att först tänka på ett mindre antal bitar. Det är en väldigt vanlig lösningsmetod för sådana här svåra problem.

Hur skulle vi göra med en bit? Det är väl ganska enkelt – vi skär den i två lika stora bitar såklart! Det går inte på något annat sätt om de olika bitarna måste väga lika mycket.

Två bitar funkar inte för uppgiften. Det går ju inte att skära en bit itu, och sedan lägga de tre bitarna i två kassar så att det är lika många bitar i varje kasse.

Hur skulle vi kunna göra med tre bitar då? Vi måste fundera på vilken som ska delas upp i två. De som är viktigt nu förstås är hur mycket bitarna väger och hur vikterna förhåller sig till varandra. Kanske ska vi dela upp den lättaste i två delar? Eller den tyngsta? Eller den mellesta? Eller olika beroende på situation? Vad tror ni?

Vi tänker oss några hypotetiska situationer, kanske med bitar som väger 1g, 100g och 100000000g. Då ser vi att i alla fall här så kan inte den minsta biten vara den som delas och inte heller den mellersta. De är helt enkelt för små för att kunna kompensera skillnaden mellan de andra två bitarna. Den största går däremot bra att dela – ska man vara exakt så måste vi dela den i bitar som väger 50000049,5g och 49999950,5g, men de exakta talen är inte det viktiga. Poängen är att de går eftersom den största biten är större än skillnaden mellan de andra två, så den funkar att dela itu för att kompensera.

Vi provar samma idé med 25 bitar.

Lösning:

Ordna bitar efter vikt, från lägst till högst. Börja nu lägga bitarna på en balansvåg: varannan på ena skålen och varannan på andra skålen. En observation vi nu kan göra är att skålen med den nyaste biten är alltid tyngst (eller väger lika mycket som andra skålen). Den andra observationen vi kan göra är att skillnaden skålarna emellan är inte större än vad den nyaste biten väger.

Vi kan bevisa de här påståenden med hjälp av matematisk induktion.

Lägg på den första biten på vänstra skålen. Förstås är den skålen nu tyngst. Men skillnaden skålarna emellan är inte större (just nu faktiskt exakt lika stor) än den här första biten.

Och nu induktionssteget. Låt observationerna gälla när vi lagt på n bitar. Säg att den sista biten vi lade på hamnade på skålen A.

Vi lägger nu den n+1:a biten på skålen B. Varför är det skålen B som är tyngst nu (eller lika tung som skålen A)? Jo, för att förut var skålen A tyngst (enligt induktionsantagandet) och skillnaden i vikt var som mest vad n:te biten väger. Men n+1:a biten väger mer (eller lika mycket)! Så skålen B måste väga tyngst nu.

Men hur mycket tyngre? Ja, inte mer än vad n+1:a biten väger i alla fall, eftersom det nyss var skålen A som var tyngst. Så har vi bevisat att observationerna gäller även när vi lagt på n+1 bitar.

Därför kan vi dra slutsatsen att ni vi lagt på 24 lättaste bitar (varannan på första skålen, varannan på andra), så kommer andra skålen vara tyngst (eller väga lika mycket som den första), samt att skillnaden i vikt är inte större än 24:e biten. Så den 25:e biten (som är minst lika stor som den 24:e) kan nu delas upp i två delar för att kompensera denna skillnad.

Rent praktiskt så mäter vi upp denna skillnad på den 25:e biten och skär upp det som är kvar i två lika stora delar. På så sätt får vi två bitar som har just den skillnaden i vikt som vi vill ha. Lägg den största på den lätta skålen, den minsta på den tunga. Det enda som återstår är att lägga bitarna från skålarna i två kassar :)

Vargen bjöd hem de tre små grisarna och Rödluvan för att titta på film. Efter att de var klara gick Vargen till köket, räknade alla kex och upptäckte att det saknades två. Men han har en stor balansvåg hemma som han kan använda. Hur kan med hjälp av två vägningar bestämma, vem som åt upp kexen? Alla kex väger lika mycket, alla grisar (i alla fall när de precis hade kommit till Vargen) också. Vargen vet även att Rödluvan bantar, så hon kunde max äta upp ett kex.

Diskussion:

Låt oss se rent teoretiskt, ifall lösningen är möjlig. Vi har två vägningar på oss, och varje vägning kan ge tre resultat: lika, första skålen väger mer eller andra skålen väger mer.

På så sätt har vi 9 teoretiska utfall efter 2 vägningar, man kan skriva upp dem som en lista, där vägningsresultaten står i ordning:

1. första väger mer, första väger mer

2. första väger mer, lika

3. första väger mer, andra väger mer

4. lika, första väger mer

5. lika, lika

6. lika, andra väger mer

7. andra väger mer, första väger mer

8. andra väger mer, lika

9. andra väger mer, andra väger mer

Å andra sidan har Vargen också 9 olika brottskombinationer:

1. gris 1 åt ett kex, gris 2 åt ett kex

2. gris 1 åt ett kex, gris 3 åt ett kex

3. gris 2 åt ett kex, gris 3 åt ett kex

4. gris 1 åt två kex

5. gris 2 åt två kex

6. gris 3 åt två kex

7. gris 1 åt ett kex, Rödluvan åt ett kex

8. gris 2 åt ett kex, Rödluvan åt ett kex

9. gris 3 åt ett kex, Rödluvan åt ett kex

Alla brottskombinationer kan hända. Därför är det teoretiskt möjligt för Vargen att lista ut svaret, om han nu lyckas hitta på sådana vägningar, så att varje resultat motsvarar entydigt en brottskombination. Men vilka grisar ska han väga, ska han väga Rödluvan och i vilken ordning? Notera att det kanske inte går i alla fall.

Lösning:

Men det går! Tricket är att använda kexen som Vargen har kvar. Min kompis Erik föreslår följande algoritm:

Vargen börjar förstås med att hiva upp två grisar på vågen, vi kan kalla dem gris 1 och gris 2. Om gris 1 och gris 2 inte väger lika mycket har den tyngre ätit ett eller två kex.

Låt oss antaga att gris 1 är den tyngre grisen. Då lägger han gris 1 i ena vågskålen och gris 3 plus ett kex i andra vågskålen. Om gris 1 är tyngre ändå, har han ätit båda kexen. Om gris 3 + kex väger lika mycket som gris 1 så har gris 1 ätit 1 kex, gris 3 ätit 0 kex och således har Rödluvan också inmundigat 1 kex. Om gris 3 + kex väger mer än gris 1, så har gris 1 och gris 3 ätit ett kex vardera.

Om gris 1 och gris 2 väger lika mycket tar man en av dem (säg gris 1) och väger denna tillsammans med ett kex mot den överblivna (gris 3). Om gris 1 + kex då väger mer än gris 3, har gris 1 och gris 2 ätit varsitt kex. Om gris 3 väger lika mycket som gris 1 + kex, så har gris 3 och Rödluvan ätit varsitt kex. Om gris 3 väger mer än gris 1 + kex så har gris 3 ätit båda kexen.

Denna lösning kan sammanfattas i följande diagram:

Redan tre personer har löst förra veckans gåta, men alla andra har en vecka till på sig att skicka in lösningen. Och här är en ny gåta att klura på.

Vargen bjöd hem de tre små grisarna och Rödluvan för att titta på film. Efter att de var klara gick Vargen till köket, räknade alla kex och upptäckte att det saknades två. Men han har en stor balansvåg hemma som han kan använda. Hur kan med hjälp av två vägningar bestämma, vem som åt upp kexen? Alla kex väger lika mycket, alla grisar (i alla fall när de precis hade kommit till Vargen) också. Vargen vet även att Rödluvan bantar, så hon kunde max äta upp ett kex.

En balansvåg har två skålar. Om tyngderna på skålarna är lika visar balansvågen jämvikt. Annars visar den vilken skål som är tyngre. Det finns en stor påse strösocker, en balansvåg samt en vikt på 1g. Hur kan man snabbast väga upp ett hekto strösocker? Observera att om man lägger två sockerhögar i en och samma skål, så blandar sockret ihop sig till en enda hög förstås.

Lösning:

Det finns två saker vi måste göra: dels hitta på ett sätt att få 100 g överhuvudtaget och dels bevisa att det sättet verkligen är det snabbaste. Det är då kanske mer logiskt att göra detta i omvänd ordning: först uppskatta hur många vägningar behövs som minst, och sedan f’örsöka hitta på en algoritm för detta antal vägningar.

I allmänhet, gör alltid först den delen av lösningen som verkar vara enklast. I vårt fall är det ganska lätt att uppskatta en gräns i alla fall. Vi kan mäta hur mycket socker vi maximalt kan väga upp efter ett visst antal vägningar.

Första gången finns det bara en sak att göra: väga upp 1 g socker med hjälp av vikten. (1 g socker uppvägt)

Andra gången kan vi max väga upp 2 g socker till (placera vikten + 1 g socker på ena skålen och uppnå balans genom att hälla socker i den andra skålen). Efter detta har vi engramsvikten, en sockerhög som väger 1 g och en sockerhög som väger 2 g. (3 g socker uppvägt)

Tredje gången kan vi igen ta alltihop på en skål och på så sätt få en sockerhög som väger 4 g. (7 g socker uppvägt)

Fortsätt räkna på samma sätt, det vill säga väg upp så mycket socker som möjligt varje gång. Efter 6 gånger kommer vi ha 63 g socker uppvägt som mest. Det kan vara uppdelat i olika högar, men det är bara 63 g totalt som vi känner till massan för. Alltså räcker det inte med 6 vägningar.

Men går det med 7?

Det går faktiskt, men det är ett lite lurigt sätt. Jag tackar Johan som har berättat lösningen för mig. Djalal hade också en korrekt lösning.

Först observerade vi att man kunde dubbla all vikt man hade. Men genom att strunta i att använda engramsvikten, så kan vi dubblera allt vi hade minus 1 gram. Man kan förstås få dubletter av enskilda småhögar också, eller få en hög som vägde 1 g mer än en annan. Vi kan faktiskt även få en hög som väger 1 mindre än en viss vald, helt enkelt genom att placera den gamla högen på ena vågskålen och engramsvikten på den andra och sedan hälla socker tills det blir balans.

Första vägningen: 1 g vikt = 1 g socker

Andra vägningen: 1 g vikt + 1 g socker = 2 g socker

Tredje vägningen: 3 g socker = 3 g socker

Fjärde vägningen: 6 g socker = 6 g socker

Femte vägningen: 1 g vikt + 12 g socker = 13 g socker

Sjätte vägningen: 25 g socker = 25 g socker

Sjunde vägningen: 50 g socker = 50 g socker

Efter den sista vägningen har vi två högar med 50 g socker i varje, så det är bara att lägga ihop dem. Vi har fått ett hekto strösocker!

Problemet kommer från mattecirkeln med Anna. Både jag och hon fick först fel svar :). Det gäller alltså att ha vettigt bevis för att antalet vägningar är det minsta möjliga.

Gåta:

En balansvåg har två skålar. Om tyngderna på skålarna är lika visar balansvågen jämvikt. Annars visar den vilken skål som är tyngre. Det finns en stor påse strösocker, en balansvåg samt en vikt på 1g. Hur kan man snabbast väga upp ett hekto strösocker? Observera att om man lägger två sockerhögar i en och samma skål, så blandar sockret ihop sig till en enda hög förstås.

Här är ett smakprov av vår andra lektion, som handlar om att väga saker på en balansvåg och avgöra om de är lätta, tunga, falska etc. Här nedan ser ni några av lektionens svåraste problem. 

Nu kan man försöka analysera vad det är egentligen som lärs ut på mattecirkeln. På sätt och vis är lektionerna mycket mer lika spel än någon annan undervisningsform. Mycket görs på egen hand och man ”levlar” när problemernas svårighetsgrad ökar. Samtidigt används det man samlade på sig under tidigare ”levels” (lättare problem).

En bra lektion lär ut idéer. Den här lektionen lärde inte ut någon specifik idé, utan var en härlig blandning av olikheter, informationsteori, falluppdelning och kombinatorik. Som inte i sig är metoder, utan just idéer till lösningar. Jag avslutar med ett citat:

What is the difference between method and device? A method is a device which you used twice.

–George Pólya, ”How to solve it”