Två bokhögar

Rekommenderad från: 12 år


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

bokhog

Visa lösningen

2 reaktioner till “Två bokhögar”

  1. 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

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

Kommentera