Vorige week was de familie Van der Torus in de bibliotheek en leenden ze samen zestien nieuwe boeken. Bij de uitgang liepen ze door het beveiligingspoortje en, ja hoor, PIEP PIEP! Blijkbaar was een van de boeken niet goed vrijgegeven. De baliemedewerker wilde alle boeken één voor één controleren, maar Mu merkte meteen op dat het sneller kon met binair zoeken (zie vorige aflevering; hint: halveren). Met slechts vier pogingen bij het poortje was het boek zo gevonden. Dat maakte indruk.

Milli en Mu zijn intussen aan de slag gegaan met het nieuwe probleem van vorige keer. Je legt een aantal, zeg 15, willekeurige speelkaarten open naast elkaar op tafel. De vraag is: kun je die rij zodanig in tweeën delen dat er evenveel zwarte kaarten in het linker deel zitten als rode kaarten in het rechter deel? En zo ja, hoe vind je zo'n gebalanceerde splitsing efficiënt? Had je er zelf al over nagedacht?

Oplossing

Aanvankelijk hadden Phi en Pi ze wat laten aanmodderen. Mu probeerde meteen een slim maar ingewikkeld programma te maken om de hoe-vraag te beantwoorden, terwijl Milli vond dat ze eerst maar eens moesten uitzoeken of het wel altijd kon. Pi legde uit dat aantonen dat iets mogelijk is, kan door er een algoritme voor te bedenken. De vraag is dan: wat is een algoritme dat altijd zo'n gebalanceerde splitsing vindt? Phi voegde daar aan toe dat het algoritme niet efficiënt hoefde te zijn. Als het maar duidelijk is dat het goed werkt.

Milli merkte op dat je natuurlijk voor elke splitsing kan controleren of deze gebalanceerd is, d.w.z. of het aantal zwarte kaarten links gelijk is aan het aantal rode kaarten rechts. Die aantallen zijn eenvoudig te bepalen. Mu vond dat het zo wel veel werk zou zijn met dat telkens opnieuw tellen. Voor een rij van $N$ kaarten zijn er $N + 1$  splitsingen mogelijk en voor elke splitsing worden alle $N$ kaarten een keer bekeken (dat zien we als één handeling). In totaal dus $N^2 + N$ handelingen. Bovendien is dan nog steeds niet duidelijk dat er altijd een gebalanceerde splitsing bestaat.

Ze kregen nog een aanwijzing van Phi. Wat als je links begint, met een splitsing waarbij het linkerdeel leeg is en het rechterdeel de hele rij omvat. Dan is de telling voor het linkerdeel nul en voor het rechterdeel het totaal aantal rode kaarten in de rij. Hoeveel kunnen die tellingen veranderen als je de splitsing één plaats naar rechts verschuift?

Milli dacht even na en zei toen aarzelend: "Dan komt er links een zwarte of een rode kaart bij en gaat er rechts een zwarte of rode kaart af." "Inderdaad", reageerde Phi, "en wat gebeurt er dan met de tellingen?" Toen liet Mu weer van zich horen: "Als er links een zwarte kaart bij komt, dan gaat de zwarte telling links met één omhoog en rechts blijft de rode telling gelijk, want het aantal rode kaarten verandert daar niet. Als er links een rode kaart bij komt, dan blijft de telling links gelijk terwijl de telling rechts met één omlaag gaat." "En wat betekent dat dan voor het verschil?" wilde Phi weten. Nu was Milli Mu te vlug af: "In beide gevallen neemt het verschil in de tellingen (zeg, rechts minus links) met precies één af. Maar dat helpt toch niet?" "Nou, kijk dan eens naar dat verschil bij het begin en bij het einde," stelde Phi voor, "Dat verschil begint positief (zwart nul, rood alles) en eindigt negatief, als het linkerdeel alle zwarte kaarten bevat en het rechterdeel leeg is." Toen zeiden Milli en Mu in koor: "Onderweg moet het verschil dus een keer precies gelijk aan nul zijn!"

De wiskundige is nu blij, want dit bewijst dat er altijd een gebalanceerde splitsing bestaat en geeft bovendien een manier om die te vinden. Maar de informaticus wil meer. Of liever, minder. Het nieuwe algoritme was niet veel beter, want het controleert de splitsingen van links naar rechts en telt nog evenveel. Daarop had Mu een ingeving: "Waarom kunnen we niet binair zoeken?" Dat vond Pi best een goed idee. Je probeert de splitsing in (de buurt van) het midden en als er meer zwarte kaarten links liggen dan rode kaarten rechts, dan weet je dat de balancerende splitsing niet rechts maar verder naar links ligt en ga je daar verder met zoeken. Net zo als er meer rode kaarten rechts liggen dan zwarte links. Het aantal handelingen gaat nu omlaag naar ongeveer $N\cdot {}^2\!\log(N)$. Voor grote waarden van $N$ maakt dat best veel uit.

Milli had intussen ook even nagedacht en had een beter idee: "Waarom houden we de tellingen niet gewoon bij terwijl we de splitsingen van links naar rechts controleren? Vooraf kun je de rode kaarten tellen, zeg $R$. Aan het begin is het aantal zwarte kaarten, zeg $Z$, gelijk aan nul. Voor de volgende splitsing wordt of $R$ één kleiner (als we een rode kaart passeren), of $Z$ één groter (als we een zwarte kaart passeren). Zodra de tellingen gelijk zijn, kunnen we stoppen." Waarop Phi suggereert om alleen $R - Z$ bij te houden en te zoeken naar een verschil van $0$. De hoeveelheid werk is dan in het slechtste geval $2N$. Pi heeft een nog beter idee: begin met een leeg linkerdeel (zwarte telling is nul) en een leeg rechterdeel (rode telling is nul) en een middendeel dat alle kaarten bevat. Maak nu telkens het middendeel kleiner, totdat het leeg is. Vergelijk de kaarten op de uiteinden van het middendeel. Als de linker rood is dan voeg je die bij het linkerdeel. Als de rechter zwart is dan voeg je die bij het rechterdeel. En als de linker zwart is en de rechter rood, dan voeg je beide kaarten toe aan hun deel. De tellingen blijven telkens gelijk. Dus zodra het middendeel leeg is, heb je de splitsing gevonden. De hoeveelheid werk is nu $N$. Beter kan niet. Of toch?

Het was Phi die ze kon overtroeven: "Nummer de splitsingen vanaf links, beginnend met nul. Dan is het nummer van de gezochte splitsing gelijk aan het aantal rode kaarten." Daar hadden de anderen niet van terug. En waarom is dat dan zo, wilden ze weten? "Kijk", zegt Phi, "Het verschil $R - Z$ begint met het aantal rode kaarten en neemt telkens met precies één af. Bij nul is de splitsing gevonden. Je gaat dus het aantal rode kaarten naar rechts."

		Volgende keer Beschouw een functie $f$ van de natuurlijke getallen naar de natuurlijke getallen. Een beroemde functie is de Collatz functie: $f(n) = n/2$ als $n$ even is en anders $3n + 1$. Kies nu een startwaarde $s$, zeg $s = 19$, en pas $f$ herhaaldelijk toe op $s$. Dan ontstaat een rij $g$ van getallen: $g_0 = s, g_1 = f(s), g_2 = f(f(s)), \ldots$. Als gegeven is dat $f$ bij herhaald toepassen periodiek wordt, d.w.z. voor voldoend grote $n$ geldt $g_{n + k} = g_n$, bedenk dan een efficiënt algoritme dat, gegeven de startwaarde voor $n$, de kleinste periode $k$ vindt.