De fraaiste wiskundige bewijzen #1

quote:

Op vrijdag 30 oktober 2009 20:37 schreef Agno het volgende:

De oneindige som 1/1 + 1/2 + 1/3 +... 1/n is gelijk aan het oneindige product (1/(1-1/p) (p = priemgetal). Het bewijs hiervoor is een goed te volgen.

Je bedoelt met P de verzameling der primegetallen.

quote:

Nog even over die zin in bold. Moet dat niet zijn "of kun je elk even getal groter dan 3 als de som van precies twee priemgetallen schrijven"? De Goldbach conjecture dus?

Uiteraard, dat is mijn fout. Afgezien van twee zijn er natuurlijk geen even priemgetallen en verder geldt dat een oneven + oneven getal een even getal is.

quote:

Op zaterdag 31 oktober 2009 00:09 schreef Kees22 het volgende:
Ik probeer me even die middelste term voor te stellen.
Je neemt voor elk priemgetal p dus de som van de reciproce van de opeenvolgende gehele machten (dus bijv. voor p=5 1/5^0 + 1/5^1 + 1/5^2 + 1/5^3 + 1/5^4 + ......... 1/5^k) en al die sommen ga je met elkaar vermenigvuldigen.

Interpreteer ik het zo goed?

Ja. En de grap is dus dat je elk getal n (uniek) kunt ontbinden en priemfactoren, dus die middelste term bevat een product van oneindige sommen met termen als 1 + 1/2 + 1/2² + 1/2³ + ···, en als andere factor 1 + 1/3 + 1/3² + 1/3³ ···, en als je dit vermenigvuldigt dan krijg je dus 1/(1·1·1·1···) = 1/1, en 1/(2·1·1·1···) = 1/2 en 1/(1·3·1·1···) = 1/3 maar ook 1/(2·3·1·1···) = 1/6, enz. Kortom, uiteindelijk 1/n voor alle n.

De naald van Buffon

De naald van Buffon is een bekend probleem dat kansrekening en geometrie combineert. Het probleem stamt uit de achttiende eeuw en luidt in zijn oorspronkelijke formulering ongeveer zo:

quote:

Stel dat we een vloer hebben die bestaat uit parallelle houten planken, elk van dezelfde breedte. Als we een naald laten vallen op die vloer, wat is dan de kans dat deze naald op twee planken ligt?

Het is duidelijk dat één en ander in ieder geval afhangt van de lengte van de naald, hoe langer de naald hoe groter de kans. We zullen de breedte van de planken b noemen. Tussen de planken zitten oneindig dunne naden, en als de naald dus op twee planken ligt, kruist deze één naad. De lengte van de naald zullen we met l aanduiden. Als nu geldt l ≤ d (wat we een korte naald zullen noemen), dan blijkt dat de kans p dat de naald op twee planken ligt gegeven wordt door:



Hiervoor zijn twee afleidingen te geven, een geometrische, en eentje die wat gebruik maakt van elementaire kansrekening en calculus. Die laatste zullen we aan het eind geven, maar eerst zullen we de geometrische behandelen. Deze geeft ook een experimentele methode om π te berekenen.


^{Een voorbeeld van een aantal willekeurig geworpen naalden van lengte l op een vloer met planken van breedte b.}

Geometrische methode

Het idee voor deze oplossing is voor het eerst door E. Barbier in 1860 aangedragen. We zijn op zoek naar de kans dat een naald op twee planken ligt, maar de truc is dat dit samenvalt met de verwachting van het aantal naden waarop de naald ligt. Dit lijkt een subtiel onderscheid, maar is het zeker niet. Als we toch even kijken naar de verwachting van het aantal naden dat een naald van willekeurige lengte kruist, dan is dit:



waarbij p₁ de kans is dat de naald één naad kruist, p₂ dat ze er twee kruist, enzovoort. De kans dat deze op (minstens) twee planken ligt wordt gegeven door:



Maar, wij bekijken een korte naald met lengte l ≤ b, dus p₂ = p₃ = ··· = 0. En daarom geldt in het geval van een korte naald E(N₁) = p. Dus als we de verwachting kunnen berekenen, dan hebben we ook de kans.<sup>1

Aan elkaar bevestigde naalden.</sup>
We zullen verder gaan met de verwachting, de verwachtingswaarde heeft namelijk een aantal interessante eigenschappen, die goed van pas komen. Stel namelijk, we gooien nog een naald, en laat het aantal naden deze naald kruist aangeduid worden door N₂. Natuurlijk geldt E(N₁) = E(N₂), en ook de kans dat deze naald op een naad ligt blijft is hetzelfde als voor de eerste naald.

Nu doen we echter wat anders. we maken de punten van de naalden aan elkaar, m.a.w. twee punten van de naald vallen samen, maar op zich kunnen ze verder los bewegen, dus de naald kan in een rechte lijn vallen, of meer in een V-vorm. Als dat gebeurt zijn N₁ en N₂ natuurlijk niet onderling onafhankelijk, maar voor de verwachtingswaarde maakt dat niet uit, immers, er geldt:



ook als N₁ en N₂ niet onderling onafhankelijk zijn. Dezelfde logica gaat ook op als we aan een van de uiteinden nog een naald vastmaken, en nog één, enzovoort. Merk op dat de naalden niet eens allemaal dezelfde lengte hoeven te hebben (zo’n constructie wordt ook wel Buffon’s noodle genoemd).

Verder merken we op dat korte naalden natuurlijk naar verwachting minder naden zullen kruisen dan lange naalden. We kunnen daarom veilig stellen dat het aantal naden dat een naald kruist afhangt van de lengte. Met andere woorden E(N) = f(l), waarbij f een functie is die we nog zullen bepalen. We kunnen echter sowieso al het nodige zeggen over f. Stel je voor dat we twee naalden N₁ en N₂ (met lengtes l₁ en l₂ nemen en zo aan elkaar maken dat ze altijd in elkaars verlengde vallen. Dan geldt natuurlijk:



Maar omdat de verwachtingswaarde lineair is, geldt ook nog:



M.a.w., f(l₁ + l₂) = f(l₁) + f(l₂). Dat is alvast één eigenschap die we binnen hebben. Verder kunnen we b.v. N₁ ook weer zien als m kleine naaldjes van allemaal gelijke lengte die aan elkaar gemaakt zijn, en dan krijgen we b.v.:



En zo vinden we dat f lineair is voor l ∈ ℚ. Als laatste merken we nu op dat f(l) monotoon stijgend moet zijn, en daarom ook dat f(l) = c·l voor l ∈ ℝ. Het aantal naden waar een naald N van lengte l naar verwachting op ligt wordt dus gegeven door:



Waarbij we c moeten bepalen. Merk op dat we het hier dus over een naald hebben met mogelijk veel hoeken erin, en niet per se een rechte naald.

_{Cirkels met straal b hebben altijd twee punten waar ze op een naad liggen.}

Voordat ik duidelijk maak waarom dit precies handig is, laten we eerst eens naar een cirkel² lijken met diameter b. Hoe je een cirkel ook gooit op de vloer, de cirkel ligt altijd precies op twee naden. Verder weten we dat de omtrek van de cirkel bπ is. Een cirkel kunnen we echter benaderen met een ingeschreven veelhoek, of met een omgeschreven veelhoek.

_{Een omgeschreven veelhoek (links) en ingeschreven veelhoek (rechts)}


Noem de omgeschreven veelhoek met n zijden O_n en noem de ingeschreven I_n, dan kunnen we elk van die veelhoeken zien als een aan elkaar gemaakte naald bestaande uit n stukken, waarvan we weten dat E(O_n) = c·l(O_n) en E(I_n) = c·l(I_n).

Er moet dus gelden:



En, omdat:


voor n → ∞:



Kortom:



en dus geldt voor een korte naald van lengte l dat deze naar verwachting:


naden raakt, en dit is dus ook juist de kans dat deze één naad raakt.


_{Cirkels met omgeschreven en ingeschreven veelhoeken willekeurig geworpen, merk op dat er op een bovenste grijze baan b.v. een cirkel ligt waarvan de omgeschreven veel hoek drie snijpunten heeft met de naden. Voor n → ∞ verdwijnt dit verschil.}

Nawoord

Dit geeft in feite een experimentele mogelijkheid om π te bepalen, teken een aantal lijnen op een stuk papier dat de naden tussen de planken voorstelt, gooi er een naald op die even groot is als de ruimte tussen de lijnen, en tel het aantal keren dat de naald een lijn kruist, omdat l = b, geldt dat π = (2n)/a, waarbij n het aantal keer is dat je gooit en a het aantal dat raak is. Dit is tevens vrij gemakkelijk te programmeren – echter, bedenk wel dat je heel snel al gebruik maakt van het getal π in je programma, wat eigenlijk de hele exercitie wat nutteloos maakt. Je moet vrij omzichtig programmeren om dat niet te doen.

Verder is deze methode verbonden aan een berucht experiment waarbij ene Lazzarini, een Italiaans wiskundige, 3408 keer een naald gooide, die 1808 keer een lijn raakte. Als benadering vond hij toen een getal dat tot op zes plaatsen nauwkeurig is – het heeft er echter alle schijn van dat hij zijn experiment zo inrichtte om een zo goed mogelijk resultaat te krijgen door op precies het juiste moment te stoppen.

Methode met integraal
Zij l de lengte van de naald, b de afstand tussen de planken, en p de kans dat de naald op twee planken ligt. Gegeven de hoek α die de naald met de horizontaal maakt, is de hoogte h van de naald l sin α, en daarmee de kans dat een naald die onder een hoek α ligt op twee planken ligt:




Met een integraal kunnen we nu de totale kans krijgen door te middelen over alle hoeken α die de naald kan aannemen ([0...π]):



_{1) Er is een kleine kanttekening te maken m.b.t. de mogelijkheid dat een naald met lengte gelijk aan de breedte van de planken precies zo valt dat ze alleen met de twee uiterste punten op een naad ligt, of het geval waarin de naald precies, over de gehele lengte, op een naad ligt. Aangezien dit wiskundige naalden en planken zijn, hebben beide gebeurtenissen kans 0 en kunnen ze verder genegeerd worden. Dit kan wiskundig gezien hard gemaakt worden.
2) Op zich hoef je geen cirkel te gebruiken, elke figuur met een vaste breedte zou ook werken, zoals een Reuleaux-driehoek. Hieruit volgt indirect ook dat voor deze figuren geldt dat o = π·d.}


Bronnen en meer lezen:
Introduction to geometric probability, Daniel A. Klain, Gian-Carlo Rota.
Buffon’s needle (Wikipedia)
Buffon’s noodle (Wikipedia)
Buffon’s needle op cut-the-knot
Buffon's Noodle Problem, J. F. Ramaley.

quote:

Op dinsdag 3 november 2009 23:59 schreef Agno het volgende:
Leuk. Had ik nog nooit van gehoord, maar de beide bewijzen zijn goed te volgen.

Roept wel de vraag op hoe de formule er uit ziet voor drie dimensionale objecten. Stel dat ik een knikker met doorsnede d laat vallen en de kans wil berekenen dat die knikker een naad kruist. Komt daar niet gewoon precies dezelfde formule uit (met l=d) ? En wat als ik kubusjes laat vallen?

Als je een goede uitdrukking kunt vinden voor de ‘hoogte’ van zo’n voorwerp, dan is het vrij goed te doen. Want dan valt in feite die integraaltruc toe te passen.

quote:

Op woensdag 4 november 2009 00:19 schreef Agno het volgende:

[..]

Inderdaad. Maar wat als ik nu spelden laat vallen en aanneem dat ze met hun punt in het hout blijven steken (dus een halve bol kunnen beschrijven tov van het 'inslagpunt'). Waarschijnlijk lukt dat ook met de integraaltruc want de richtingshoek van de speld tov van de vloer en zijn lengte bepalen de hoogte aan de andere zijde van de speld. Of maak ik een denkfout?

Klopt volgens mij. Maar als het om experimenteren gaat om π uit te rekenen, heb je niet zoveel aan die integratiemethode.