KP Hart

KP's ramblings

Het Compactheidsbeginsel

Twee recente artikelen op Kennislink hebben iets gemeen. Dat gemeenschappelijke is een belangrijk stuk gereedschap uit de Wiskunde dat bekend staat als het Compactheidsbeginsel.

In 2016 werd een kleuringsprobleem voor de natuurlijke getallen opgelost: is het mogelijk de natuurlijke getallen in tweeën te delen op zo’n manier dat beide delen geen enkel Pythagoreïsch drietal bevatten? Het antwoord is: “nee”. Zoals op Kennislink te lezen is is er iets meer ontdekt: bij elke verdeling van {1,2,3,…7825} in twee delen moet een van de delen een Pythagoreïsch drietal bevatten en er is een verdeling van {1,2,3,…,7824} waarbij geen van de beide delen een bevat.
Voor de goede orde: een Pythagoreïsch drietal is een drietal natuurlijke getallen (a,b,c) dat voldoet aan a2+b2=c2. Ook wordt het probleem vaak in termen van kleuringen geformuleerd: de verdeling wordt weergegeven door elk natuurlijk getal rood of blauw te kleuren.

Begin van deze maand werd vooruitgang geboekt bij een kleuringsprobleem in het platte vlak: in hoeveel verzamelingen moet je de punten in het vlak minimaal verdelen opdat geen enkel deel twee punten bevat die afstand 1 hebben. Er was lang bekend dat dat minimale aantal ten minste 4 en ten hoogste 7 is; nu is bekend dat het ten minste 5 moet zijn. Okk hier is al aan een eindige verzameling punten te zien dat bij elke verdeling in vier stukken er altijd een stuk is dat twee punten met afstand 1 bevat.

Waarom is dat? Het zou toch bij het eerste probleem zo kunnen zijn dat bij verschillende kleuringen de drietallen één kleur krijgen steeds hoger in de natuurlijke getallen moeten zitten. Maar kennelijk is het zo dat, ongeacht de kleuring er al een éénkleurig drietal is in {1,2,3,…7825}.

Het geheim is een stelling van De Bruijn en Erdös; deze zegt dat bij elk kleurings probleem het volgende geldt: als elke eindige verzameling een `goede’ kleuring heeft dan is er een `goede’ kleuring voor de hele verzameling. Dat kun je ook als volgt contrapositief formuleren: als elke kleuring van de hele verzameling `slecht’ is dan is er een vaste eindige verzameling waarvoor elke kleuring `slecht’ is. In April 2014 is over deze stelling een artikel in Pythagoras verschenen.

Het voordeel van dit Compactheidsbeginsel is dat men voor positieve resultaten alleen naar eindige verzamelingen hoeft te kijken; dat kan de bewijzen aanzienlijk vereenvoudigen. Het nadeel is dat het niet constructief is: het geeft geen enkele informatie over de grootte van de vaste eindige verzameling waarvoor elke kleuring `slecht’ is. Dat laatste is te zien aan de resultaten waarover op Kennislink bericht werd; de zoektochten naar de eindige verzamelingen en de verificaties dat ze werkten kostten veel tijd en moeite.

Eindexamen Wiskunde B (vwo) (2018-05-14)

Ik heb gisteravond snel het examen gemaakt en becommentarieerd. Hier is een link naar mijn PDF. Ik had niet veel tijd dus ik kan fouten gemaakt hebben (laat het mij weten).

Ik vond het examen niet echt uitdagend. Er was niet veel context en die van de Sheffield Winter Garden leek er met de haren bijgesleept. Aan de andere kant waren de formuleringen wel erg uitgebreid en bleef er vaak niet meer over dan een (soms lastige) invuloefening.`

Het vlak kleuren

Vorige maand (april 2018) is er een stap gezet op weg naar de oplossing van het volgende probleem: “hoeveel kleuren heb je nodig om de punten van het vlak te kleuren en wel zo dat punten op afstand 1 verschillende kleuren krijgen. De titel van het artikel in de Volkskrant is misleidend want het probleem is nog niet opgelost; de titel van het stuk in NRC is correct.

Beide stukken waren niet zo duidelijk als men wellicht hoopte, getuige bijvoorbeeld de commentaren in de facebookgroep ‘Leraar Wiskunde’. De opmerkingen over de voorbeelden in de Volkskrant werden niet altijd begrepen en de pixelmetafoor in NRC leidde tot misverstanden over de aard van het probleem.

Wat bekend was over het probleem tot vorige maand was het volgende. Door middel van een betegeling van het vlak met behulp van regelmatige zeshoeken met diameter 1 kun je een kleuring met zeven kleuren maken. Hierbij moet je wel precies zijn: bij elke zeshoek neem je de randpunten van zes uur tot twaalf uur mee (inclusief zes uur exclusief twaalf uur) en laat je de andere randpunten weg. Elke tegel krijg namelijk een kleur en op deze manier vermijdt je dat randpunten op afstand 1 dezelfde kleur krijgen.

De voorbeelden in het NRC-artikel zijn duidelijk: als je de punten van het vlak met twee kleuren kleurt dan zijn er in een gelijkzijdige driehoek met zijden 1 al twee punten met dezelfde kleur. Daarnaast is er een configuratie van zeven punten te zien waarvoor bij elke kleuring met drie kleuren twee punten met afstand 1 zijn die dezelfde kleur krijgen.

Het nieuwe is een configuratie van 1581 punten, gevonden door Aubrey de Grey waarin hetzelfde geldt, maar nu voor vier kleuren; dus, hoe je die punten ook kleurt met vier kleuren er zullen er altijd twee zijn met afstand 1 en dezelfde kleur. Inmiddels is 1581 teruggebracht tot 633.

De pixelmetafoor uit NRC leidde tot een onderschatting van het probleem; dat kwam door een subtiel verschil tussen pixels en de punten van het vlak: in tegenstelling tot pixels hebben punten in het vlak geen directe buren en geen oppervlakte, ook zijn ze niet vierkant. De echte formulering van het probleem vraagt naar het kleinste natuurlijke getal n met de eigenschap dat er een functie van het vlak naar {1,2,…,n} is met de eigenschap dat als d(x,y)=1 dan f(x)≠f(y). Daar komt geen verf of kwast aan te pas en de vorm of oppervlakte van een punt is ook niet van belang.

Achter de voorbeelden die laten zien dat een bepaald aantal kleuren niet volstaat zit een stelling van De Bruijn en Erdös: als elke eindige deelverzameling van het vlak een goede kleuring met k kleuren toelaat dan laat het vlak ook een goede kleuring toe. Met andere woorden: om te laten zien dat er geen goede kleuring is moet je een eindige verzameling zonder goede kleuring vinden.

Overigens zou dit nog tot twee verschillende oplossingen van het probleem kunnen leiden: de stelling van De Bruijn en Erdös geldt onder aanname van het keuzeaxioma. In dit artikel van Shelah en Soifer is te lezen dat de aard van de gevraagde functie het antwoord kan beïnvloeden. Lang voor het werk van De Grey was bekend dat een Lebesgue-meetbare kleuring ten minste vijf kleuren zou vergen. NB de laatste stelling in het artikel van Shelah en Soifer is nu achterhaald.

Ten slotte: houd de Wikipediapagina over dit probleem in de gaten.

Toevoeging (2018-05-14): het hieronder in een reactie genoemde artikel op Kennislink is ook zeer informatief.

Did Thanos kill me?

Some of you may have seen Avengers: Infinity War already, some may have not. Via Geek Girl Authority I found this website: www.didthanoskill.me/. There you can check whether you will survive the carnage at the end of the movie.

As is to be expected the decision process is not very sophisticated:

if (randomNumber < 0.5) {
   displayElement.textContent = "You were slain by Thanos, 
                            for the good of the Universe.";
 } else {
   displayElement.textContent = "You were spared by Thanos.";
 }

But, can you escape your fate by reloading the page? Actally, no.
The script first retrieves a cookie:

var randomNumber = getCookie("thanosNumber");

If that number exists it will be used in the decison process, so the random number is generated on your first visit and re-used on each next reload. My `thanosnumber’ is 0.3461087295578963, so I’m a goner.

I also checked whether the process is fair; it is on this page you can read that the random number is in the interval [0,1) (including 0, excluding 1). That means that, even accounting for the finite precision, half the numbers can be expected to be less than ½.

To see why excluding 1 mighyt matter think of a machine with a very low precision, say two binary digits. This means that the random numbers would be chosen from these four: .00, .01, .10, .11 (that is: 0, ¼, ½, ¾,). Clearly your probability of survival would be 2/4, i.e., one half. On the other hand, if 1 were als a possible outcome then your survival probability would be 3/5.

For the population of the Earth and with the precision suggested by my thanosnumber including 1 or not would not make much difference.
Since there are no more that 1010 people and the thanosnumbers have a precisioon of 16 digits the difference in the order of 10-6 person.

Wat is een verzameling? II

We zetten de zoektocht naar het begrip `verzameling’ voort.

In de vorige blogpost hebben we de definities die Bolzano en Cantor van `verzameling’ gaven geciteerd. Die kwamen eigenlijk neer op “een verzameling is een verzameling”. Nu is het nogal lastig om een definitie van verzameling in woorden op te schrijven zonder te vervallen in synomiemen maar het kan wel.

Rond de eeuwisseling (die van 1900) begon men ernstig over de aard van definities na te denken. De eerste stap was het vastleggen van de taal waarin die definities vastgelegd zouden worden. En met `taal’ bedoelde men niet zoiets als Grieks, Latijn, of Swahili maar een meer formele constructie. Deze gaat uit van een beperkt aantal symbolen. Sommige zijn algemeen, zoals ∧ (en), ∨ (of), ¬ (niet), ∀ (voor alle) ∃ (er is) enzovoort; en sommige zijn specifiek voor het onderhavige onderdeel van de wiskunde, in de verzamelingenleer kunnen we toe met ∈ (is element van) en = (is gelijk aan).

In deze taal kunnen we vrijwel alles beschrijven wat we willen. De taal is sterk genoeg om dingen als

  • “x is een priemgetal”
  • “x is een reëel getal”
  • “x is een rechte lijn in het vlak”

en nog veel meer uit te drukken. Op deze manier kunnen we afspreken dat we iets alleen een verzameling noemen als het bestaat uit x-en met een eigenschap die in onze taal is uit te drukken. Dus
{x : x is een priemgetal}
is een verzameling (waarbij “x is een priemgetal” in de taal is geformuleerd). Dit komt vrij dicht in de buurt van Cantor’s definitie van verzameling: de accolades {} representeren de `Zusammenfassung zu einen Ganzen’, en we hebben `Annschauung’ en `Denken’ vervangen door `beschrijfbaar in de taal’.

De lege verzameling ∅ is uit te drukken door {x : x≠x} en telt dus mee als verzameling. Andere dingen leken iets dubieuzer, zoals {x : x=x}, de verzameling, V, van alle verzamelingen(?). Die gaf aanleiding tot een paradoxale toetand: Cantor had bewezen dat elke verzameling strikt minder elementen dan deelverzamelingen heeft (zie deze en de daarop volgende post voor de betekenis van meer en minder), maar voor deze V geldt dat niet, want elke deelverzameling is automatisch ook een element.
De oplossing, van Cantor, was onderscheid te maken tussen gewone en `oneigenlijke’ verzamelingen. En V was dus oneigenlijk; te groot om als gewone verzameling mee te tellen. Dat dit niet de schoonheidsprijs verdient lijkt me duidelijk want wie bepaald wat gewoon en oneigenlijk is?

Het kon nog erger: Bertrand Russell schreef de volgende verzameling, R, op: {x : x∉x}. Deze R leidt tot een wel heel eenvoudige paradox/tegenspraak, namelijk “$R∈R dan en slechts dan als R∉R”. Hier zijn geen diepe stellingen voor nodig; de afspraak hierboven was vanaf het begin al dubieus.

De uiteindelijke oplossing kwam van Ernst Zermelo. Deze formuleerde een een lijst axioma’s (spelregels) die we in acht moeten nemen als we met verzamelingen omgaan. Deze geven vooral aan hoe nieuwe verzamelingen uit oude gevormd kunnen/mogen worden. Die regels zijn redelijk natuurlijk; zo mogen we, gegeven twee verzamelingen x en y de verzameling {x,y} vormen.
Een van de belangrijkste regels is het Afscheidingsaxioma; dit zwakt onze eerste beschrijving wat af. Als x een gegeven verzameling is en φ is een formule in onze taal dat is {y:y∈x ∧ φ} weer een verzameling. Het verschil is dus dat we al een verzameling moeten hebben en daarbinnen elementen met een bepaalde eigenschap bijeen nemen.
Wat voor veel mensen in begin nog even wennen is is dat elk individu waar uitspraken over worden gedaan een verzameling is. Dus de elementen van verzamelingen zijn zelf ook weer verzamelingen enzovoort. Dat impliceert ook dat dingen als natuurlijke en reële getallen beschrijvingen krijgen die niet lijken op wat we gewend zijn maar dat went uiteindelijk wel.

Maar goed, dit leidt dan tot de volgnde definitie van verzameling: iets waarvan het bestaan uitgaande van de axioma’s te bewijzen is.
En wat dan allemaal uitgaande van die axioma’s mogelijk is kunt u in elk boek over Verzamelingenleer lezen en ook in het dictaat van de cursus Verzamelingenleer die ik zelf gegeven heb.

Wat is een verzameling? I

De Wiskunde is doordrenkt van verzamelingen. Nagenoeg elke definitie van een te bestuderen structuur — groep, graaf, interval, … — begint met “een verzameling die …”. De taal en de methoden van de Verzamelingenleer helpen dan ook vaak bij het efficiënt formuleren en noteren van resultaten.

Hierbij gaat men voor het gemak voorbij aan het feit dat de vraag “Wat is een verzameling?” nog niet beantwoord is. Dat klinkt merkwaardig want we herkennen een verzameling wel als we er een zien: postzegels, boeken, vingerhoedjes, …, je kunt het zo gek niet bedenken of iemand heeft er wel een verzameling van.

Echter, in de Wiskunde houden we van precieze definities, zodat op elk moment duidelijk is waar we het over hebben. Hier is een waarschuwing op zijn plaats, mooi geïllustreerd door het volgende citaat

1005. Die Mathematiker sind eine Art Franzosen; redet man mit ihnen, so übersetzen sie es in ihre Sprache, und dann ist es alsobald ganz etwas anderes.
Johann Wolfgang von Goethe,
Maximen und Reflexionen, Nachlass, Über Natur und Naturwissenschaft

Ik heb niet de illusie te weten wat Goethe hier zelf mee bedoelde en door nadere bestudering van zijn is dat wellicht te achterhalen maar ik vind de uitspraak op zichzelf al treffend genoeg. Veel definities van wiskundige begrippen beantwoorden niet aan het idee dat de niet-wiskundige er van heeft.

Hoe zit dat met het begrip `verzameling’? Hoe kijken we daar wiskundig tegenaan. Een van de eersten die een definitie van `verzameling’ formuleerde was Bernard Bolzano.

Einen Inbegriff, den wir einem solchen Begriff unterstellen, bei dem die Anordnung seiner Theile gleichgültig ist (an dem sich also nichts für uns Wesentliches ändert, wenn sich bloss diese ändert) nenne ich eine Menge.
Bernard Bolzano,
Paradoxien des Unendlichen (1851)

Een andere definitie vinden we bij Georg Cantor.

Unter einer ,Menge` verstehen wir jede Zusammenfassung M von bestimmten wohlunterschiedenen Objecten m unserer Anschauung oder unseres Denkens (welche die ,Elemente` von M genannt werden) zu einem Ganzen.
In Zeichen drücken wir dies so aus:

M = {m}

Georg Cantor,
Beiträge zur Begründung der transfiniten Mengenlehre (Erster Artikel) (1895)

Het is, denk ik, geen toeval dat het begrip `Menge’ gedefinieerd werd bij onderzoek naar het begrip `oneindig’. Op dat moment zijn eventueel gegeven relaties tussen de individuen in het geheel van ondergeschikt belang. Op een gegeven moment kies je uit een hele rij synoniemen — collectie, veelheid, Mannigfaltigkeit, aggregate, set, verzameling, … — er eentje en dat wordt dan de naam van het basisbegrip.

Wie de definities nauwkeurig leest ziet dat ze, eigenlijk, niets zeggen: beide gebruiken een synoniem, Inbegriff en Zusammenfassung, als definitie. Daarbij zegt de definitie van Bolzano expliciet en die van Cantor impliciet wat hierboven al is gezegd: bij een verzameling is de onderlinge relatie van de elementen niet van belang. Vlak voor de definitie gaf Bolzano het voorbeeld van een gebroken glas; dat vinden wij iets heel anders dan hetzelfde glas voor het gebroken was omdat de onderlinge relatie tussen de delen verstoord is, als verzameling — atomen, moleculen — is het niet veranderd.

De definities van Bolzano en Cantor hadden ongetwijfeld het doel zo scherp mogelijk af te bakenen over welke zaken er uitspraken gedaan werden. Bolzano nam daarbij een lange aanloop waarvan de definitie een samenvatting was.

Op een naïef niveau kun je met deze afspraken redelijk uit de voeten omdat er niet meer gebeurd is dan dat bekende gehelen nu het predicaat `verzameling’ opgeplakt hebben gekregen. Iets als {1,2,3,4,5} wordt door iedereen herkend als “de verzameling natuurlijke getallen van 1 tot en met 5”. En ook verzamelingen met een beschrijving als {n ∈ N : n ≤ 10100} herkennen we wel, mits we eerst hebben afgesproken dat N de verzameling der natuurlijke getallen voorstelt.

Waar de wiskunde en de dagelijkse praktijk uit elkaar lopen is bij de kleinste verzamelingen: de lege verzameling en de verzamelingen met één element. Als ik zeg dat ik een postzegelverzameling heb en ik laat een album zonder zegels zien dan gelooft niemand mij, ook niet als ik er één laat zien (vlak voor ik hem op een brief plak).

Wiskundig gesproken zouden dat volstrekt legitieme verzamelingen zijn ook al piept de buitenwacht nog zo hard. Bij het werken met en gebruik van verzamelingen komen die kleine verzamelingen zo vaak voor dat het heel vervelend wordt ze iedere keer uit te sluiten van het verzamelingschap. Denk aan vergelijkingen. Heel vaak wordt daar over de oplossingsverzameling gesproken en dat zou ineens niet mogen als er geen of maar één oplossing is? Kom nou!

Maar goed, dit alles gaat nog uit van de opvatting dat we verzamelingen herkennen als we ze zien. Het vertelt ons nog niet wat een verzameling is. Wat de moderne opvatting van verzameling is zien we volgende keer.

Å Bygge Broer

I Abels Tårn på 23. mars hørte jeg et forsøk å forklare hvorfor Robert Langlands fikk tildelt Abelprisen 2018. “Hans program danner broer mellom tallteorien og andre deler av matematikken.” Det ble ikke mye mer diskusjon; det var snakk om `automorfe former’, men bare snakk.

Hvis en ønsker å vite hva Langlands Program handler om så kan enfinne noen innledende artikler på Abelprisens nettsted. I Abels Tårn hører vi også om prisvinneren fra 2016: Andrew Wiles. Wiles sin bevis av Fermats siste theorem er et eksempel på bruk av en bro mellom Tallteorie og Algebraisk Geometri.

Jeg lurte på om det ikke var een liten bro mellom tallteori og geometri (algebraisk eller annerledes) som kunne illustrere hvordan geometri kan hjepe tallteori (eller omvendt).

Her har vi kanskje en, et enkelt spørsmål i talltheorie: fins det to kvadrattall der et er doppelt så stor enn det andre? Det vil si: fins det to naturlige tall, m og n, slik at n2=2×m2?
For dette spørsmålet kan vi bygge en bro til geometrien: vi tegner to kvadrater, et med sidelengde m og et med sidelengde n. og spørsmålet er om vi kan få det til at arealet av det andre kvadratet er to ganger arealet av det første.
Vi kan tegne kvadratene sånn:.

Det er en elementær læresetning at en kan doble arealet av en kvadrat ved å tegne et kvadrat hvilket sidelengde er lik diagonalen in det første kvadratet.
Nå tar vi en rettvinklet trekant med sidelengder m, m og n (halvparten av kvadratet med sidelengder m). Vi danner et punkt z på som deler hypotenusen i to stykker, av lengde m og n-m, og så tegner vi linien gjennom z vinkelrett på hypotenusen og mot siden av trekantet.

Hypotenusen i det nye trekantet er diagonalen in et kvadrat med sidelengde n-m og derfor vet vi at kvadratet av hypotenusen er lik 2(n-m)2. Når vi bruker at n2=2m2: så får vi

2(n-m)2=2n2-4nm+2m2=4m2-4nm+n2=(2m-n)2

Den nye hypotenusen er altså 2m-n lang.

Dette beviser at det er ikke mulig å finne to naturlige tall m og n som i spørsmålet: hvis det fins to slike tall kan vi finne andå to slike tall som er mindre. Men for de naturlige tall vet vi: hvis det fins et tall som har en (ønsket) egenskap fins det et minste tall med denne egenskapen. Så vi kunne ha begynt med det minste tall n slik at det fins et tall m for hvilet vi har n2=2m2 men da er 2m-n et mindre tall med samme egenskapen. Dette motbeviser at en sånn n fins.

Her ser vi, som i beviset til Wiles, at geometrien hjelper å løse et tallteoretisk problem.

Nå er det slik at vårt tallteoretisk problem har en (nogså enkel) tallteoretisk løsning: i kvadraten n2 finner vi et likt antall primfaktorer 2, dobbelt så mange som i n selv. Og i 2 ganger et kvadrat, 2m2, finner vi et odde antall primfaktorer 2, dobbelt så mange som i m selv plus en til. Det betyr at 2m2 er aldri lik n2.

Og mange folk håper at Fermats Siste Teorem har en slik enkel bevis også.

Bruggen bouwen

In het Noorse radioprogramma Abels Tårn werd op 23 maart een poging gedaan uit te leggen waarom Robert Langlands de Abelprijs 2018 had gekregen. “Hij bouwde bruggen tussen diverse gebieden in de Wiskunde.” Veel verder ging de discussie niet; al viel de kreet `Automorfe Vormen’ nog even.

Voor wie wil weten wat het Langlands Program inhoudt kan op op de website van de Abelprijs wat inleidende artikelen vinden. In het radioprogramma werd nog even verwezen naar een eerdere winnaar Andrew Wiles. Diens bewijs van de Grote Stelling van Fermat is een voorbeeld van het gebruik van zo’n brug tussen Getaltheorie aan de ene oever en Algebraïsche Meetkunde aan de andere.

Ik vroeg me af of er niet een klein bruggetje tussen getaltheorie en meetkunde (algebraïsch of anderszins) bestaat dat als illustratie kan dienen.

Misschien helpt dit, een eenvoudige getaltheoretische vraag: bestaan er twee kwadraten (van natuurlijke getallen) waarvan de ene het dubbele van de andere is? Dat wil zeggen: zijn er twee natuurlijke getallen, m en n, zo dat n2=2×m2?
Je kunt voor dit probleem een brug naar de meetkunde slaan: teken twee vierkanten, een van n bij n en een van m bij m. De vraag is of je m en n zo kunt kiezen dat de oppervlakte van het eerste vierkant twee keer zo groot is als het tweede.
In de meetkundige versie kun je de vierkanten als hieronder tekenen.

Om een gegeven vierkant in oppervlakte te verdubbelen moet je een vierkant tekenen waarvan de zijden gelijk zijn aan de diagonaal van het eerste vierkant.
Neem nu de rechthoekige driehoek met zijden m, m en n. Pas m af op de schuine zijde en teken de lijn vanuit z loodrecht op de schuine zijde naar de basis.

De schuine zijde van de nieuwe driehoek is de diagonaal van een vierkant met zijden n-m en dus geldt dat het kwadraat van die zijde gelijk is aan 2(n-m)2. Schrijf dat uit en gebruik dat n2=2m2:

2(n-m)2=2n2-4nm+2m2=4m2-4nm+n2=(2m-n)2

Dus die schuine zijde is inderdaad 2m-n lang.

Dit laat zien dat het niet mogelijk is natuurlijke getallen m en n te vinden als gewenst: als er twee van die getallen zijn dan kun je twee andere vinden die kleiner zijn. Maar in de natuurlijke getallen geldt: als er een getal met een bepaalde eigenschap bestaat dan is er ook een kleinste getal met die eigenschap. We hadden dus onze m en n zó kunnen kiezen dat n het kleinste getal is waarvoor een m bestaat met n2=2m2 en dan is 2m-n een echt kleiner getal met dezelfde eigenschap. Die tegenspraak laat zien dat zo’n n er in het geheel niet is.

Dus, als in het bewijs van Wiles, heeft de meetkunde geholpen bij het oplossen van een getaltheoretisch probleem.

Overigens heeft het getaltheoretische probleem een eenvoudige getaltheoretische oplossing: in een kwadraat n2 komt de priemfactor 2 een even aantal malen voor, namelijk twee keer zo vaak als in n zelf. En in het dubbele van een kwadraat, 2m2 komt 2 een oneven aantal malen voor: een even aantal maal in m2 plus de ene extra factor 2. Dus 2m2
is nooit gelijk aan n2.

En vele mensen hopen dat de grote stelling van Fermat ook zo’n eenvoudig bewijs heeft.

KP checkt: 200 liter inkt

Op twitter toonde Dap Hartmann zich een aanhanger van regel 17 uit The Elements of Style: Omit needless words (er zijn twee regels 17, dit is de eerste). Dat zou hem bij het nakijken wel 200 liter (rode?) inkt per jaar besparen.

Navraag leerde dat Dap met een vulpen nakijkt. Een snelle zoektocht leerde dat vulpeninkt in potjes van, onder meer, 60 en 80 ml wordt verkocht. Nu rekent 80 ml iets makkelijker: er gaan 12.5 van die potjes in een liter, en dus 2500 potjes in 200 liter.
Als Dap 50 weken per jaar van maandag tot en met vrijdag zit na te kijken (welk een plichtsbetrachting) dan komen die 200 liter neer op 10 potjes inkt per dag.
Ik denk dat Dap van de stijlfiguur `overdrijving’ gebruik heeft gemaakt.

Fruitmanden samenstellen

Op Facebook stond in de groep Wiskundelessen de volgende vraag (verkort weergegeven): “Hoeveel fruitmanden met zes stuks fruit kun je samenstellen uit vier kiwis, vijf bananen, zes peren, en zeven appels?” De vraagsteller wist dat het antwoord 79 moest zijn maar zag geen manier om daar aan te komen.

Een reageerder vond 79 wel erg weinig want het aantal manieren om 6 dingen uit 22 te kiezen, zonder op de volgorde te letten, is gelijk aan de binomiaalcoëfficiënt 22 boven 6 en die is gelijk aan 74613.
Dat antwoord zou kloppen als de vruchten er wel erg verschillend uit zouden zien. De vraagstelling vermeldt dat niet en het antwoord 79 suggereert dat de vruchten van dezelfde soort ononderscheidbaar zijn.

Hoe pak je zoiets aan? Elke fruitmand is eigenlijk een woord van zes letters, gekozen uit {k,b,p,a}, en gesorteerd: eerst de k’s, dan de b’s, de p’s, en aan het eind de a’s . Bijvoorbeeld kkbbpa, aaaaaa, ppppp, … Die woorden kun je lezen als producten: k2b2pa, a6, p6, … Het komt er dus op neer al dat soort producten te tellen. Hoe doe je dat systematisch, zonder een product te missen?

Dat gaat het best met wat eenvoudige algebra, werk het volgende product uit:

(1+k+k2+k3+k4)(1+b+b2+b3+b4+b5)(1+p+p2+p3+p4+p5+p6)(1+a+a2+a3+a4+a5+a6+a7)

Je krijgt dan alle mogelijke gesorteerde woorden met ten hoogste vier k’s, vijf b’s, zes p’s en zeven a’s.
Nu nog even de woorden van zes letters opzij zetten en tellen: klaar.

Dat kan nog iets sneller: maak van elke letter een x. Elk woord van zes letters wordt dan x6 en dat maakt het uitwerken van het product wat makkelijker.

(1+x+x2+x3+x4)(1+x+x2+x3+x4+x5)(1+x+x2+x3+x4+x5+x6)(1+x+x2+x3+x4+x5+x6+x7)

Met (be)hulp van Maple is het resultaat snel gevonden:

Inderdaad: 79 fruitmanden met zes vruchten. We kunnen nu ook aflezen hoeveel fruitmanden met andere aantallen vruchten gemaakt kunnen worden.

In het februarinummer uit 2016 van Pythagoras staat nog meer over deze manier van combinaties tellen.

© 2011 TU Delft