Rekommenderad från: 12 år
[kkratings]
På ett bord ligger en boksamling av barnböcker i 10 delar, uppdelade i två högar. Du får ta tag i en stapel (några av de översta böckerna i en hög, som minst en, som mest hela högen) och placera den överst på den andra högen.
Hur kan man på 19 sådana operationer eller färre se till att alla böckerna ligger i en hög och delarna är ordnare (det vill säga, del 1 ligger underst, del 2 ligger näst underst och så vidare)?
Problem vecka 17
Nötter (1 poäng).
I tre högar finns 22, 14 respektive 12 nötter. Du får göra tre förflyttningar, så att högarna får lika många nötter. Under en förflyttning får du flytta ett antal nötter från en hög till en annan, men antalet nötter man flyttar måste vara lika med antalet nötter i högen man flyttar till. Vilka förflyttningar ska du göra?
Äpplen (3 poäng). Några lådor innehåller sammanlagt 2000 äpplen. Du får antingen ta bort lådor eller ta bort äpplen från lådor. Visa att du kan med hjälp av sådana operationer få kvar lådor med samma antal äpplen i varje, så att det sammanlagt finns minst 100 äpplen kvar.
Visa lösningar
Lösningen till problemet för de äldre vecka 47
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.
