Mattegåta
I tio likadana kannor finns lite mjölk: varje kanna är full till max 10%. En tillåten operation är att ta en valfri kanna och hälla av en del av mjölken till de andra kannorna (lika mycket till varje övrig kanna).
Visa att 10 operationer räcker för att få kannorna att innehålla exakt lika mycket mjölk.
Diskussion
För det första kan kannorna innehålla väldigt ojämna mängder av mjölk, så det, att kannorna är fulla till max 10%, säger är att vi alltid kan hälla över mjölk, det blir alltså aldrig för fullt i någon kanna.
Vi ska få till lika mycket mjölk i varje kanna. Det känns inte som om vi kan hoppas på den sista överhällningen. Om det är ojämnt i många kannor, kan inte en enda överhällning (som ju häller lika mycket i varje icke-vald kanna) få alla kannorna att innehålla lika mycket. Alltså måste vi börja fixa kannor med lika mycket mjölk redan i början.
Börjar man på ett smart sätt får man att 9 operationer räcker.
Lösning (av Erik Svensson)
För att fördela mjölken jämnt mellan kannorna, låt oss använda följande algoritm:
Om alla kannorna har lika mycket mjölk i sig, då är vi klara. Annars kommer någon kanna ha mest mjölk och någon annan ha minst mjölk (om flera har mest eller minst väljer vi godtyckligt bland dessa), och mellan dem finns en viss skillnad i hur mycket mjölk de innehåller. Från den med mest mjölk häller vi till varje annan kanna en tiondel av denna skillnad. På det viset kommer den mest mest mjölk förlora nio tiondelar av skillnaden, och den med minst mjölk ökar med en tiondel av skillnaden, och således kommer de efteråt att innehålla lika mycket mjölk. Alla kannor, utom den vi häller ifrån, ökar sitt mjölkinnehåll lika mycket, vilket innebär att den kanna som hade minst mjölk innan operationen fortfarande kommer ha minst mjölk, tillsammans med den som nyss hade mest mjölk.
Sedan upprepar vi detta. För varje iterering tar vi den kanna som har mest mjölk och ser till att den jämnställs med alla kannor som har minst mjölk. Dessa kannor ändras inte i förhållande till varandra, och alltså kommer vår algoritm på detta vis att öka antalet såna jämnställda kannor med ett vid varje iterering. Efter högst tio itereringar kommer således alla kannor innehålla minst mjölk, det vill säga, de innehåller alla lika mycket mjölk.
