De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  prikbord |  gastenboek |  wie is wie? |  contact

HOME

samengevat
vragen bekijken
een vraag stellen
hulpjes
zoeken
FAQ's
links
twitter
boeken
help

inloggen

colofon

  \require{AMSmath} Printen

Formule voor punten op een cirkel!

Stel we nemen n punten op de omtrek van een cirkel, en als we allemaal met elkaar verbinden, krijgen we allemaal snijpunten binnen de cirkel. Ook allemaal deellijnstukken en gebieden. Kent U een formule voor:
1 het aantal snijpunten 2 het aantal gebieden 3 het aantal deellijnstukken.
Ik heb al voor het aantal gebieden voor n= 1 t/m 5 getekend en gezien dat het een macht van 2 zou kunnen zijn voor de formule. Alleen bij n=6 klopt dit niet meer. Lastig.
Bij voorbaat dank.

Jack
Student hbo - zaterdag 24 april 2004

Antwoord

Hallo Jack,

Op het eerste gezicht lijkt jouw vraag op Circle Division by Lines, maar jouw probleem is net iets anders, omdat je ervan uitgaat dat je alle lijnen tussen de n punten tekent. Bij Circle Division by Lines moest je nog goed opletten hoe de lijnen precies georienteerd waren, maar nu is dat minder ingewikkeld. Wel ga ik er vanuit dat je de punten niet toevallig net zo gekozen hebt dat meerdere lijnen door n punt gaan (en eigenlijk is het daarmee toch weer hetzelfde als bij Circle Division by Lines, waar de uitzonderings-situatie evenwijdigheid van lijnen is).

q23145img1.gif
Je vraagstuk leent zich heel goed voor een aanpak met volledige inductie. Stel we hebben al een n-tal punten op een cirkel (in de tekening n=6). We noemen
  • s(n) = het aantal snijpunten tussen de lijnen,
  • g(n) = het aantal gebieden waarin de cirkel door de lijnen wordt verdeeld,
  • l(n) = het aantal deellijnstukken van snijpunt tot snijpunt.
Nu zetten we er nog (n+1)e punt bij. Wat gebeurt er dan met s,g en l? Zonder beperking van algemeenheid noemen we het nieuwe punt 0 en de rest {1,2,...,n} en we veronderstellen dat punt 0 tussen de punten 1 en n ligt en de overige punten op volgorde over de cirkel zijn verdeeld. De lijnen die er nu bij komen zijn 0-1, 0-2, ..., 0-i, ..., 0-n. Laten we per lijn die er bij komt kijken wat er verandert aan s,g en l:

Voor de eerste lijn 0-1 (en analoog voor 0-n):
Deze doorsnijdt geen enkele andere lijn dus D1s = 0. Hij creert wel n nieuw gebied, dus D1g = +1. Bovendien is het natuurlijk n nieuw lijnstuk, dus D1l = +1 (niet meer omdat hij geen andere lijnen snijdt).

Voor de tweede lijn 0-2 (en analoog voor 0-(n-1)):
Deze doorsnijdt alle lijnen komend uit punt 1, behalve die naar 2 (en die naar 0). Dat zijn er n-2, dus D2s = +(n-2). Deze n-2 snijpunten op 0-2 verdelen de lijn 0-2 in n-1 lijnstukken die evenzoveel gebieden verdelen in twee gebieden, waarvan er dus n nieuw is. Dus D2g = +(n-1). Het aantal lijnstukken dat er is bijgekomen is niet alleen de n-1 lijnstukken op 0-2, maar ook n-2 op de doorsneden lijnen, dus D2l = (n-1)+(n-2).

Heb je het systeem al door? Dan gaan we het nu voor een willekeurige lijn 0-i met i tussen 1 en n doen (ga anders nog even verder met 0-3 en eventueel 0-4).

Voor de lijn 0-i (en analoog voor 0-(n-i+1)):
Deze doorsnijdt alle lijnen tussen de punten uit {1,..., i-1} en de punten uit {i+1,..., n}. Dat zijn er (i-1)(n-i), dus Dis = (i-1)(n-i). Deze (i-1)(n-i) snijpunten verdelen de lijn 0-i in (i-1)(n-i)+1 lijnstukken evenzoveel gebieden in tween delen, dus Dig = (i-1)(n-i)+1 = Dis + 1. Het aantal lijnstukken dat er is bijgekomen zijn de (i-1)(n-i)+1 op 0-i en (i-1)(n-i) op de doorsneden lijnen, dus Dil = (i-1)(n-i) + 1 + (i-1)(n-i) = 2 Dis + 1.

Als we nu willen weten hoeveel snijpunten, gebieden en lijnstukken erbij komen door het toevoegen van het (n+1)e punt, dan hoeven we dit alleen nog maar te sommeren over i van 1 t/m n:
Ds = i=1nDis = i=1n(i-1)(n-i) = i=1n(-n+(n+1)i-i2) = -n2 + (n+1)1/2n(n+1) - 1/6 n(n+1)(2n+1) = 1/6n3 - 1/2n2 + 1/3n = 1/6n(n-1)(n-2).
In de inductie-stap krijg je dus s(n+1) = s(n) + 1/6n(n-1)(n-2), dus s(n) = s(0) + m=1n-1 (1/6m(m-1)(m-2)). Nu is het handig om te weten dat het sommeren over m van een polynoom in m met graad k, een polynoom van graad k+1 oplevert. Dus s(n) = a n4 + b n3 + c n2 + d n + e. Je kunt nu a,b,c,d en e vinden door enkele waarden voor n in te vullen (handig trucje is overigens om ook n=-1 en n=-2 te gebruiken door gewoon s(n) = s(n+1)-Ds toe te passen). Het antwoord luidt:

s(n) = 1/24n4-1/4n3+11/24n2-1/4n = 1/24n(n-1)(n-2)(n-3).

Voor g en l kun je natuurlijk deze zelfde berekeningen opnieuw uitvoeren, maar het kan ook slimmer:
  • Dg = i=1nDig = i=1n(Dis + 1) = Ds + n,
  • Dl = i=1nDil = i=1n(2 Dis + 1) = 2 Ds + n.
Hieruit volgt dat g(n) = s(n) + 1/2n(n-1) + g(0) en l(n) = 2 s(n) + 1/2n(n-1) + l(0), zodat:
  • s(n) = 1/24n(n-1)(n-2)(n-3),
  • g(n) = s(n) + 1/2n(n-1) + 1,
  • l(n) = 2 s(n) + 1/2n(n-1).

Ik hoop je hiermee geholpen te hebben,

Guido Terra

Zie Wat te bewijzen is - Martin Kindt

gt
Vragen naar aanleiding van dit antwoord? Klik rechts..!
woensdag 28 april 2004
 Re: Formule voor punten op een cirkel! 


klein |  normaal |  groot

home |  vandaag |  bijzonder |  twitter |  gastenboek |  wie is wie? |  colofon

©2001-2018 WisFaq - versie IIb