Posts in category afschatten

Birthday Paradox on steroids.

Most of us are familiar with the so-called Birthday Paradox: the probability in a group of 23 people there are (at least) two who share a birthday is larger than 50%. If you are not familiar with this result then you could peek at the calculation on the Wikipedia page or try it for yourself (big hint calculate the probability that no two people in the group share a birthday).

In Act One of Episode 630 of This American Life we see another take on this phenomenon. It occurs in the context of voter fraud, in particular double voting. In this case, a bit simplified, one looks at the probability that in the group of American Voters two of them would have the same name and the same birthday (including the year).

Listen to the episode to see that basically all cases of `double voting’ can be accounted for by chance alone. And then you may want to read the paper on which the item was based, and visit the website of Sharad Goel (who was featured in the broadcast).

Het vermoeden van Duffin en Schaeffer

Recentelijk is het Duffin-Schaeffer-vermoeden bewezen. U kunt de preprint hier lezen. In de krant is er ook aandacht aan besteed. Ik wil hier iets meer over de wiskunde achter dit vermoeden vertellen.

Het vermoeden, nu dus een stelling, zegt iets over het benaderen van irrationale getallen met behulp van rationale getallen. De vraag is in het algemeen hoe efficiëent dergelijke benaderingen kunnen zijn.
Nu zullen de meningen over wat efficiënt is uiteen lopen maar de benaderingen die we in de praktijk gebruiken, namelijk afgekapte decimale ontwikkelingen, zijn het niet echt. Als die afgekapte ontwikkelingen als breuk schrijft is die breuk vrijwel nooit te vereenvoudigen: de benadering 3.14159265358979323846264338327 van π levert een onvereenvoudigbare breuk met een grote teller en een grote noemer.
Een goede benadering is er een waar de nauwkeurigheid groot is, vergeleken met de grootte van teller en noemer. Zo kun je 22/7 een goede benadering van π noemen omdat het verschil 22/7-π kleiner is dan 1/49. Het criterium dat we hier hanteren is: p/q is een goede benadering van α als |α-p/q| kleiner is dan 1/q2. Overigens is 19/6 ook een goede benadering: 19/6-π is kleiner dan 1/36.
Een beetje spelen met een rekenmachientje laat zien dat er geen goede benaderingen van π zijn met noemers 8 of 9.

Het vermoeden van Duffin en Schaeffer, nu dus de stelling van Dimitris Koukoulopoulos en James Maynard, gaat overigens niet over individuele irrationale getallen als π of √2. Het bekijkt de zaak van de andere kant en doet uitspraken over hoeveel irrationale getallen veel goede benaderingen hebben.
Je kunt bijvoorbeeld een vaste noemer n nemen en kijken welke getallen een goede benadering met noemer n hebben. Hierbij beperken we ons tot het interval (0,1); getallen in andere intervallen krijgen we door over een geheel getal op te schuiven.
Nu is meteen duidelijk welke getallen een goede benadering met noemer n hebben: die liggen in de intervalletjes van de vorm (k/n-1/n2,k/n+1/n2), met k=1,…,n-1, en in (0,1/n2) en (1-1/n2,1).
De totale lengte van die intervallen is gelijk aan 2/n (reken maar na).
Hiermee kun je voorspellingen doen: omdat 2/10+2/11+2/12+2/13+2/14+2/15 kleiner is dan  1 zijn er getallen zonder goede benadering met noemers 10 tot en met 15.
Noem de vereniging van de intervalletjes hierboven even An. Met behulp van de Categoriestelling van Baire kun je bewijzen dat er een relatief `dikke’ deelverzameling van het interval (0,1) is waarvan elk element tot oneindig veel van de An behoort en dus oneindig veel goede benaderingen heeft.

Dit nu is de aard van de stelling van Dimitris Koukoulopoulos en James Maynard: deze geeft, bij bepaalde definities van `goede benadering’, voorwaarden onder welke de verzameling getallen met oneindig veel goede benaderingen heel `dik’ is of juist heel `dun’, waarbij `dik’ en `dun’ ondubbelzinnige definities hebben. Daarnaast geeft de stelling ook een dichotomie: `dik’ en `dun’ zijn de enige mogelijkheden. Het is nooit zo dat ongeveer de helft van de getallen oneindig veel goede benaderingen hebben; de kans is altijd gelijk aan nul (wat niet betekent dat er geen getallen zonder oneindig veel goede benaderingen zijn) of gelijk aan één.

In het krantenartikel wordt nog het volgende voorbeeld van `mooie’ benaderingen gegeven: als hierboven moet |α-p/q| kleiner zijn dan 1/q2, maar q moet zelf ook een kwadraat zijn. In dat geval is de kans op oneindig veel mooie benaderingen gelijk aan nul, maar de bovengenoemde stelling van Baire garandeert toch dat er heel veel irrationale getallen met oneindig veel goede benaderingen zijn.

Ten slotte: voor de definitie van `goed’ waar dit stuk mee begon geldt dat <emelk irrationaal getal oneindig veel goede benaderingen heeft. Dat bewijs je niet met de methoden die hier beschreven zijn, daar moet je wat dieper de getaltheorie in duiken. Zie hiervoor de Wikipediapagina’s over Benaderingsstelling van Dirichlet en over Kettingbreuken.

De koningin en de profeet

Via facebook kwam ik bij dit artikel uit The Poke: de Koningin van Engeland zou afstammen van de profeet Mohammed. Het refereert aan een stuk uit de Daily Mail van vorig jaar. Maar goed, is dit bijzonder?

Een nuttig gegeven in het artikel is dat we van de koningin 43 generaties terug moeten om bij de profeet te komen. Daar kunnen we mee rekenen.
Op deze pagina wordt met veel slagen om de arm geschat hoeveel mensen er ooit op aarde geleefd hebben. Dat zouden er zo’n 108 miljard zijn. Op die pagina staat een tabel met bevolkingsaaantallen voor diverse jaartallen. Daaruit kunnen we schatten dat er in de tijd van Mohammed niet veel meer dan 400.000.000 mensen op de hele aarde leefden.
Aan de andere kant: als we vanuit om het even welk persoon 43 generaties terug in de tijd gaan en consequent bij elke voorouder de naam van de vader en moeder op zouden schrijven, dan bevat elke nieuwe generatie twee keer zoveel namen als de voorgaande: twee ouders, vier grootouders, acht overgrootouders, enzovoort. De 43ste generatie bevat dan 243=8.796.093.022.208 namen.

Wat dan overduidelijk is dat er heel wat personen meer dan één keer in die 43ste generatie genoemd zullen worden: gemiddeld ruim 20.000 maal. Als je zo naar die getallen kijkt wordt het hoogst onwaarschijnlijk dat Mohammed niet een voorouder van de koningin is.
Er zijn natuurlijk geografische omstandigheden die personen uit bepaalde gebieden wat onwaarschijnlijker als voorouder maken, maar er is altijd veel verkeer tussen Europa en de Arabische wereld geweest. Ik hou het er op dat het helemaal niet bijzonder is dat er een lijntje loopt van Mohammed naar Elizabeth. Het zou wel knap zijn als ze echt zo’n lijntje zouden hebben gevonden.

En tau rund jorden, II

Dette er andre delen av en oversettelse av en artikkel som ble publisert i November 2004 i Pythagoras (et matematisk tidsskrift for unger). Artikkelen finnes også på Engelsk i Half a Century of Pythagoras, en utvalg av artikler publisert av MAA.

Vi strekker en tau helt tettsittende rund jorden, forlenger det lit og drar de opp til den en helt stram. Hvor høyt må vi dra opp tauen? Kan vi uttrykke høyden i lengden vi spleiset inn?

I går vi så at når vi tar en tau som er en meter langre enn jordens omtrekk og drar tauen strammt ved Nordpolen så skal det høyeste punktet være på 121 meter og lit mer. I dag skal vi lage en enkel formel med radiusen og ekstra lengden i som gir en god approksimasjon av høyden.

En effektiv approksimasjon

Her er tegningen fra i går igjen

Fra Pythagoras sin læresetning lærte vi at



Fra bildet ser vi også at



Dette kan kombineres til denne ligningen



Nå har vi et uttrykk for h som bruker R og α men vi trenger et som bruker ε. Dette må gjøres implisitt fordi α er en løsning av



og der er ingen `pen’ (eller stygg) formel for løsningene.

Som vi så i går er vinkelen α veldi liten (0.006176 radianer). Nå er det slik at α+α3/3 er en veldi bra approksimasjon av tanα. Hvis vi setter dette uttrykket i ligningen så får vi



Også tanα er veldi liten.
Og for x nær 0 har vi √(1+x)≈1+½x; nå kan vi forenkle formelen for h til en approksimasjon



Neste steg er å skrive ut kvadraten



Når vi setter i tallene så får vi Rα2=242.8 m, Rα4=0.009 m og Rα6=3.5×10-7 m. Vi derfor kan trygt kaste fjerde og sjette potensene og så får vi denne approksimasjonen for h:



Lit lengre siden fant vi at



Vi setter det inn i approksimasjonen og får



Nå bruker vi verdien av R og får til slutt



Det flotte med denne formelen er at den gir nesten samme svaret som i går: setter vi inn ε=0.5 så får vi h≈121.4 m igjen.

Oppgav
Sett inn ε=0.005 in formelen vår. Hvor mye forskjeller resultatet fra verdien av h som vi fikk i går?

Exercise
Undersøk hvor bra approksimasjonen √(1+x)≈1+½x er. For eksempel, sammenlign (1+½x)2 med 1+x; for hvilken x er forskjellen liten nok til å bli kastet? Er du enig i hvordan approksimasjonen brukes her?

Bemerkning
Vi kan isolere ε i formelen:



dette gir viktig kvalitativ informasjon: h er omtrent lik en konstant ganger ε2/3.
Hvis du er kjent med Taylorpolynomer kann det være gøy å finne ut hvor stor feilen er (hvilken potens av ε) i denne approksimasjonen.

Tijdrijden in Bergen

Deze week worden in Bergen, Noorwegen, de wereldkampioenschappen wielrennen op de weg gehouden, met vandaag, 20-09-2017, het tijdrijden voor de heren. Het parcours is interessant: een relatief vlakke rit met aan het eind een klim naar de top van Fløyen, een plek met een mooi uitzicht over de stad en de haven.

In de lokale krant Bergens Tidende staat het profiel van de rit getekent, met de laatste drie kilometer nog een keer apart in het onderstaande plaatje.

Dat ziet er dramatisch uit, tot je even naar de eenheden kijkt: horizontaal zijn dat kilometers, verticaal gaat het in stappen van 50 meter omhoog. En dat geeft, op zijn zachtst gezegd, een vertekend beeld. Ik heb, bij benadering, het echte profiel even geschetst.

Dat lijkt niet erg steil en zo van opzij ziet het er niet moeilijk uit; echter, bij wegen met een dergelijke helling staat vaak een waarschuwingsbord voor, juist, een steile helling. Een hellingspercentage van ongeveer 10 % betekent dat er constant met een kracht gelijk aan ongeveer 10 % van het gewicht van jezelf en je fiets tegen je aan geduwd wordt. Naar beneden is dat plezierig al zul je snel zien dat je in je remmen moet knijpen om niet te snel te gaan. Naar boven maak die kracht het fietsen al een stuk moeilijker.

Voor wie wil rekenen: denk maar eens aan de formule F=m×a (kracht is massa maal versnelling). De kracht recht naar beneden is gelijk aan g×m (hier is g de zwaartekrachtsversnelling, daar mochten we op school wel de waarde 10 voor nemen). Hiervan werkt 10 % langs de weg, dus onze F is gelijk aan g×m/10, van school mocht ik daar dus m van maken. Conclusie: de versnelling die we ondervinden als we freewheelend naar beneden gaan is 1 m/s2. Per seconde gaan we dus een meter per seconde sneller. Bereken zelf maar eens hoe snel je dat te link vindt worden.

Snel ordenen

Nog een vraag van de wisfaq:

Ik ben me aan het voorbereiden voor toelatingsexamen aan de Koninklijke Militaire School en kwam volgende vraag tegen:
Sorteer a, b en c volgens stijgende waarden: a=√23; b=1199/250; c=959/200
Nu vroeg ik me af hoe ik dit efficiënt kan doen en zonder rekenmachine weliswaar!

Hoe doe je zoiets snel? Als ik veel haast heb bereken ik misschien 1199×200 en 959×250. Er geldt namelijk dat b>c precies als 1199×200>959×250 (via kruislings vermenigvuldigen) en daarnaast zou ik snel de kwadraten van b en c bepalen en met 23 vergelijken.

Die vermenigvuldigingen kosten wel wat tijd want de getallen zijn een beetje groot. Daarom kan het handig zijn iets beter naar de getallen te kijken. Dan blijkt dat die twee breuken hetzelfde gehele deel hebben, namelijk 4, en dat wat overblijft snel te vergelijken is:
1199/250=4+199/250=4+796/1000 en 959=4+159/200=4+795/1000 en nu zijn b en c in ieder geval heel eenvoudig te vergelijken: b>c.
En hoe zit het met √23? Het kwadrateren van b en  c kan iets sneller als je het indirect doet: schijf b=5-204/1000 en c=5-205/1000, en gebruik de bekende formule (x-y)2=x2-2xy+y2. Dan blijkt dat

  • b2=23-4/100+(204/1000)2, en
  • c2=23-5/100+(205/1000)2.

Nu is (204/1000)2 net iets meer dan (2/10)2=4/100, dus b2 is net iets groter dan 23.
Ook (205/1000)2 is iets meer dan 4/100 maar niet te veel: het is kleiner dan het makkelijkere kwadraat (21/100)2=4,41/100 en dat is weer kleiner dan 5/100, dus c2 is kleiner dan 23.

Conclusie: 959/200<√23<1199/250.

Ik vind dit een aardige opgave omdat met weinig niet al te moeilijke vermenigvuldigingen en delingen drie getallen die heel dicht bij elkaar liggen toch mooi onderscheiden kunnen worden.

Twee machten vergelijken

Op een paar plekken op het web dook de vraag weer eens op wie groter is: 10001001 of 10011000.

Je kunt die vraag op meer dan één manier/niveau beantwoorden. Achtereenvolgens bekijken we

  1. Rekenmachientje: neem links en rechts de duizendstemachtswortel en vergelijk 10001,001 met 1001. Dank aan Frank Boers (via `Leraar Wiskunde’ op Facebook).
  2. Logaritmen en rekenmachientje: de logaritmen (basis 10) kunnen eenvoudig vergeleken worden en we krijgen informatie over het aantal cijfers in beide machten.
  3. Natuurlijke logaritmen en integralen: de natuurlijke logaritmen van de machten kunnen, met een beroep op een eenvoudige eigenschap van de integraal `met de hand’ vergeleken worden.
  4. Binomium van Newton: schrijf (1000+1)1000 uit met behulp van het binomium en laat zien dat de termen in de som steeds groter worden; hiermee is de macht snel af te schatten.
  5. Binomium van Newton (bis): het quotient van (1000+1)1000 en 10001001 is met behulp van het binomium af te schatten met 3/1000.
  6. Het getal e: met behulp van een definierende rij voor e kan de vorige afschatting verbeterd worden tot e/1000.
  7. Functieonderzoek: in het algemeen geldt: als e<x<y dan yx<xy. Dit volgt door de functie x/ln(x) te bekijken. Dank aan René Pannekoek.
  8. Gebruik de e-macht: via ex>1+x vind je 10001,001>1000+ln(1000).

De oplossingen vereisen nogal wat wiskundige notatie; daarom heb ik ze hier in een PDF-file neergezet.

© 2011 TU Delft