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)?
Böcker kan ligga hur som helst i början, men vi vet att de ligger i två högar på något sätt, och del 1 måste vara i en utav högarna. Låt oss först se till att just del 1 hamnar underst i en hög.
Ta då tag i högen som inte innehåller del 1 och lägg det överst på den andra högen. Allt ligger nu i en hög. Ta sedan tag i stapeln som har del 1 som understa bok och lyft över allting till den tomma platsen. Nu har vi en hög med del 1 underst och en annan hög, vilket ha tagit oss 2 operationer. Högst 2 egentligen, om del 1 redan låg på rätt plats från början.
Oavsett var del 2 ligger nu gör vi följande process. Lyfta bort alla eventuella böcker som ligger på del 1 och placera den stapeln på andra högen. Eftersom del 2 nu finns i den högen, lyft stapeln som har den delen underst och placera alltihop på del 1. Detta tog oss (högst) 2 operationer.
Gör samma sak med del 3: lämna först del 1 & del 2 ensamma och sedan lyft över stapeln med del 3 underst dit. Igen (högst) 2 operationer.
Fortsätter man på samma sätt kommer del 4, del 5, del 6, del 7, del 8 ta högst 2 operationer var. Vi har nu förbrukat 16 operationer, så det är 3 kvar.
Hur kan högarna se ut nu? I en hög ligger del 1 till del 8 i rätt ordning och på dem ligger eventuellt några böcker.
Om del 9 och del 10 råkar ligga ovanpå dem i rätt ordning, så är vi klara. Om de råkar ligga i fel ordning, lyft bort de båda och sedan lägg dem tillbaka en i taget (del 9 kommer vara först med att läggas på den stora stapeln, sist kommer del 10), det kommer ta (högst) 3 operationer.
Om både del 9 och del 10 ligger i den andra högen, lägg dem över antingen båda på en gång (om del 9 är underst), eller en i taget (om del 10 är underst), detta kommer ta (högst) 3 operationer.
Om den lilla högen bara innehåller del 10, så tar det 1 operation att lägga över den och få sorterad stapel. Om den lilla högen bara innehåller del 9, är det lite svårare. Då lägger vi över del 10 till den lilla högen, och sedan lägger tillbaka del 9 & del 10 tillsammans, och får en sorterad stapel. Detta tog alltså (högst) 2 operationer.
Oavsett hur det ser ut på slutet, tar det alltså högst 3 operationer. Vi klarade således att sortera bokhögen på högst 19 operationer!
Kul problem! Om man sätter sig med tio spelkort 1–10 och plockar lite märker man att det är ganska lätt att oftast klara det på elva tolv drag sådär ifall man helt enkelt alltid lägger ihop två kort som ska ligga efter varann när det går. Oftast kan man göra sådana drag, men några få gånger måste man hitta på nåt annat. Ibland blir det lite mer; jag fick fjorton någon gång.
Med metoden i lösningen här vet man att man alltid klarar det på max 19. Jag gick utöver rekommenderad-från-12-år-kategorin och undrade hur många drag som *kan* krävas som mest med en perfekt metod. Det går helt klart att komma under den gränsen. (Resonemanget där visar t.ex. max fem drag för tre kort, men det går att alltid klara det på max fyra. Målet är 3,2,1. Värsta läget är högarna 1,2 + 3.)
Istället för att försöka tänka smart så skrev jag ett program som provade alla möjligheter. Det finns nästan 20 miljoner sätt att lägga de tio korten i två högar. (Då räknar jag det som samma sätt om man byter plats på de två högarna.)
När det är färdigt ska man ha 10,9,8,7,6,5,4,3,2,1. Det vanligaste är att det går att klara det på 10 drag (6,6 miljoner fall). I snitt går det att klara på 9,9 drag, och medianen är 10. I värsta fall går det att klara på 14 drag, faktiskt! Ett exempel på en sådan position med svårhittad lösning på fjorton drag är 6,7,5,9,3 + 10,4,8,1,2.
Här är hela tabellen över hur många positioner som kräver olika många drag.
0 1
1 9
2 81
3 648
4 4740
5 27846
6 138474
7 557946
8 1787772
9 4178254
10 6609797
11 5442439
12 1164136
13 45848
14 409
Summa 19958400
Häftigt Per!
Jag misstänkte att det gick att förbättra algoritmen genom att vara lite smartare på slutet (precis som att man inte räknar med 4 operationer för 9:an och 10:an), men frågan var hur långt man kunde gå utan att fastna i väldigt många fall.
Tack programmering, för att du finns. Nu har du dessutom skapat ett nytt pussel: hur klarar man sig på 14 drag i fallet 6,7,5,9,3 + 10,4,8,1,2 :)