WW: Cijferreeksen

De woensdagmiddag is op GeenCommentaar Wondere Woensdagmiddag. Met extra aandacht voor de nieuwste ontwikkelingen in Wetenschap- en Techniekland.

getallenkussentjes (foto flickr/EraPhernalia Vintage . . . (playin' hooky ;o))We beginnen vandaag met het volgende puzzeltje: maak de volgende reeks af: 1,2,4,8, ??.

Bent u aan het nadenken? Neem de tijd, we hebben geen haast. Ja? U bent eruit? Als uw antwoord “16” is mag ik u feliciteren: inderdaad is dat het goede antwoord. Wat we hier zien zijn de machten van 2 (20, 21,22, 23,…). Maar u bent niet de enige winnaar, ook mensen met als antwoord “15” winnen vandaag. De getoonde reeks kan namelijk ook gezien worden als begin van de Cake Number reeks (het aantal manieren waarop een 3-dimensionale kubus in n plakken gesneden kan worden). En ook de mensen met die  “17” antwoordden winnen vandaag. Zij hielden blijkbaar de Generalized Catalan Number reeks [pdf] aan.En laten we eigenlijk maar iedereen die mee heeft gedaan feliciteren. Elk antwoord op deze vraag is namelijk correct. En nog erger, dit geldt voor alle cijferreeksen.

De wiskundige vertaling van de bovenstaande vraag is de volgende: gegeven deze cijferreeks, a) geef een reeks-formule die deze sequentie oplevert en b) geef de volgende waarde die je krijgt als je deze reeks-formule gebruikt. En nu is bekend dat voor elke eindige reeks van gehele getallen er een polynoom is die deze reeks beschrijft. Dat wil dus zeggen dat de reeks 1,2,4,8,16 een polynoom heeft (namelijk onder andere a(n) = 2^n) maar ook 1,2,4,8,15 (C(n+1,3)+n+1.) en ook 1,2,4,8,0 of 1,2,4,8,100. Van die laaste twee weet ik de polynomen niet, maar de het wiskundig bewijs geeft aan dat ze er wel degelijk zijn.

Hoewel de cijferreeks-vraag vanuit wiskundig opzicht dus betekenisloos is, zal iedereen die wel eens meegedaan heeft aan een intelligentie-test zal dit type vraag namelijk zeer bekend voorkomen. Bij cijferreeks-vragen is het ‘juiste’ -lees het gezochte- antwoord dat getal dat de volgende waarde is van de meest “of “prettig aanvoelende” polynoom-beschrijving. Zo’n simpele beschrijving voor een uiterlijk complexe reeks getallen geeft een prettig gevoel van abstractie en begrip. Mensen zoeken voortdurend simpele patronen in de chaos die ze omringt en de een kan dit beter dan de ander.

Psychologisch allemaal zeer begrijpelijk dus, maar wiskundig is het dus een volstrekt betekenisloze vraag. Wie allerlei mogelijke (benoemde) reeksen wil bekijken kan terecht op de OEIS On-Line Encyclopedia of Integer Sequences, waar je het begin van een sequentie kan invoeren en de bijbehorende benoemde reeksen als antwoord krijgt. Op fibonicci.com kan je een aantal van de reeksen zelf uitproberen.

Ten slotte nog een link naar een werkelijk schitterend filmpje over de beroemdste aller reeksen: de Fibonaccireeks.

  1. 2

    @1: Maar goed dat er niet meer gekeurd wordt voor militaire dienst. Van intelligentietesten was toch ook al eens aangetoond dat ze cultureel vertekend zijn (anders misschien ook nog wel een aardig topic voor een WW)?

  2. 3

    @2: maar de IQ-test voor militaire dienst was toch juist om de slimmerikken er uit te zeven, zodat die konden worden afgekeurd?

  3. 4

    Misschien mis ik iets, maar het artikel gaat over een nogal simpel resultaat dat genoemd wordt in een mailinglijst uit 2002. En er zit meer in dan hier vermeld:

    Het bewijs is via constructie, wat betekent dat niet alleen aangetoond is dat voor iedere reeks zo’n polynoom bestaat, maar dat ook meteen het recept voor het maken van die polynoom wordt voorzien. Het is heel eenvoudig, en kan zo aan middelbare-schoolleerlingen uitgelegd worden (althans, dat hoop ik met alle onderwijs[strike]verslechteringen[/strike]vernieuwingen).

    Bijvoorbeeld voor de reeks 1,2,4,8,100 is het:
    f(x) = 85/24 (x-4)(x-3)(x-2)(x-1) + 1/6 (x-3)(x-2)(x-1) + 1/2 (x-2)(x-1) + (x-1) + 1.

    Wat hiermee is laten zien is dat eindige reeksen niet zo interessant zijn. Oneindige reeksen daarentegen des te meer. Natuurlijk kun je bovenstaande eindige reeksen uitbreiden tot oneindige door te zeggen: vanaf nu alles 1, of vanaf nu de Fibonnacireeks, maar dat is nogal flauw.

    Op Wikipedia staat nog een aardig resultaat, het bewijs wordt niet genoemd. Een reeks heet “definieerbaar” als je een algoritme kunt geven waardoor ieder willekeurig element uit de reeks bepaald kan worden. Onder meer alle eindige reeksen voldoen hier dus aan, daar gaat dit artikel over.

    Nu is de verzameling van alle mogelijke reeksen onaftelbaar, zoals dat heet. Denk erover als een maat voor hoeveel oneindig veel reeksen er zijn. De verzameling defineerbare reeksen is echter wél aftelbaar. Dat betekent dat “bijna alle” (wat een wiskundig precieze uitspraak is) reeksen niet definieerbaar zijn!

  4. 5

    Hoezo is de reeks 1,2,4,8,16, , ,etc eindig?
    Zijn priemgetallen op dezelfde wijze eindig? En wat is als dat zo zou zijn het polynoom voor de priemgetallen?

  5. 6

    @Paul
    De reeks 1,2,4,8,16,… als machten van 2 is oneindig.

    Als je daarentegen zegt: ik ben op zoek naar een eindige reeks die begint met 1,2,4,8,16, dan laat de genoemde constructie zien dat alle reeksen die zo beginnen mogelijk zijn.