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!
