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 :)
