Opgave 3

Bepaal het aantal oneven binomiaalgetallen in (a+b)^n.

Antwoord

  1. Een binomiaalgetal is van de vorm: \binom{n}{r}=\dfrac{n!}{r!s!} met s=n-r.
  2. We noteren de getallen n,r en s in het binair talstelsel:

        \[n=\sum_{i=0}^hn_i.2^{h-i}\]

     

        \[r=\sum_ir_i.2^{k-i}\]

     

        \[s=\sum_i^ps_i.2^{p-i}\]

    met n_i,r_i,s_i \in \{0,1\} en n_0=1

  3. De exponent van 2 in n! is gelijk aan n-\sum n_i. De exponent van 2 in r! is gelijk aan r-\sum r_i. De exponent van 2 in s! is gelijk aan s-\sum s_i.
    Voor meer uitleg lees volgend artikel
  4. Als het binomiaalgetal oneven moet zijn, dan mag \dfrac{n!}{r!s!} geen factor 2 meer bevatten en moet dus n-\sum n_i=r-\sum r_i+s-\sum s_i.
  5. Bijgevolg is \binom{n}{r} oneven als \sum n_i=\sum r_i+\sum s_i.
  6. Het aantal oneven binomiaalgetallen komt dus overeen met het aantal keuzes van r, tussen  0 to n , waarvoor \sum n_i=\sum r_i+\sum s_i.
  7. Als n_i=0 moet  r_i=s_i=0. Er is dus 2^0=1 mogelijkheid
  8. Als n_i=1, dan heb je 2^1=2 mogelijkheden: r_i=1,s_i=0 of r_i=0,s_i=1.
  9. Noteer k=\sum_i n_i, dan zijn er dus 2^k oneven binomiaalgetallen.
  10. Er zijn dus 2^k oneven binomiaalgetallen in (a+b)^n, waarbij k gelijk is aan de som van de cijfers in de binaire schrijfwijze van n.
  11. Controleer met een voorbeeld : voor n=4 heb je als binomiaalgetallen: 1,4,6,4,1. Er zijn dus 2 oneven binomiaalgetallen. Nu is 4 = 100 in het binair talstelsel en dus is k = 1+0+0=1. Er zijn dus 2^1=2 oneven binomiaalgetallen.

Ontbinding in priemfactoren van n!

We weten dat n! = n.(n-1)…1. We willen nu onderzoeken wat de exponent is van een priemgetal p in de ontbinding in factoren van n!
  • Schrijf  n in het p-tallig stelsel: n=n_lp^l+n_{n-1}p^{l-1}+\cdots+n_1p+n_0.
  • Elk veelvoud van p tussen 1 en n levert 1 factor p in de ontbinding van n!. Zo zijn er \lfloor \dfrac{n}{p} \rfloor= n_lp^{n-1}+n_{l-1}p^{l-2}+\cdots+n_1, want \dfrac{n_0}{p}<1.
  • Elk veelvoud van p^2 tussen 1 en n levert  een extra factor p in de ontbinding van n!. Zo zijn er \lfloor \dfrac{n}{p^2} \rfloor= n_lp^{n-2}+n_{l-1}p^{l-3}+\cdots+n_2, want \dfrac{n_1}{p}+\dfrac{n_0}{p^2}<1
  • Noteer met v_p(n!) de exponent van p in de ontbinding van n!.
  • Dan is:  v_p(n!)=( n_lp^{n-1}+n_{l-1}p^{l-2}+\cdots+n_1)+(n_lp^{n-2}+n_{l-1}p^{l-3}+\cdots+n_2)+\cdots +(n_lp+n_{l-1})+n_l
  • Herschikking geeft: v_p(n!)=n_l(p^{n-1}+p^{n-2}+\cdots+p+1)+n_{l-1}(p^{l-2}+\cdots+1)+\cdots+n_2(p+1)+n_1
  • Dus v_p(n!)=n_l\dfrac{p^n-1}{p-1}+n_{l-1}\dfrac{p^{n-1}-1}{p-1}+\cdots+n_2\dfrac{p^2-1}{p-1}+n_1.
  • Noteer n_l+n_{l-1}+\cdots+n_1+n_0=s_p(n).
  • Bijgevolg is v_p(n!)=\dfrac{1}{p-1}(n-s_p(n)).

Voorbeeld : 12!=479001600=2^{10}.3^5.5^2.7.11

  • 12 = 1100 in het binair talstelsel, dus is v_2(12!)=12-(1+1+0+0)=10.
  • 12 = 110 in het drietallig stelsel, dus is v_3(12!)=\dfrac{1}{2}(12-(1+1))=5.
  • 12 = 22 in het vijftallig stelsel , dus is v_5(12!)=\dfrac{1}{4}(12-(2+2))=2.
  • 12 = 15 in het zeventallig stelsel , dus is v_7(12!)=\dfrac{1}{6}(12-(1+5))=1.
  • 12 = 11 in het elftallig stelsel , dus is v_{11}(12!)=\dfrac{1}{10}(12-(1+1))=1.

Baltic Way

Op 23 augustus 1989 vond in Estland,Letland en Litouwen een vreedzaam protest plaats tegen de Sovjet-Unie aan wie de drie Baltische staten precies 50 jaar daarvoor hun onafhankelijkheid verloren. Over een afstand van ruim 600 kilometer werd een menselijke ketting gevormd langs de hoofdsteden Riga, Tallinn en Vilnius. De demonstratie leverde de landen veel internationale publiciteit en dat zorgde uiteindelijk binnen een jaar voor de onafhankelijkheid van de drie landen.

baltic

Ter nagedachtenis aan dit protest dat tot de onafhankelijkheid leidde, werd in 1990 voor het eerst de ‘Baltic Way’ georganiseerd tussen Estland, Letland en Litouwen. In de afgelopen 25 jaar is de lijst met deelnemende landen stapsgewijs uitgebreid tot het huidige aantal van 11: naast de 3 Baltische staten zijn dat Finland, Zweden, Noorwegen, Denemarken, Ijsland, Polen, Duitsland en Rusland. België was in 2005 als twaalfde land te gast bij de Baltic Way.

Het concept is al die jaren nagenoeg ongewijzigd gebleven. Ieder land stuurt 5 middelbare scholieren die als team gedurende vierenhalf uur aan twintig opgaven moeten werken. De charme van de wedstrijd is dus dat je als team voor ieder lid de juiste opgave moet uitzoeken. Opgaven op oplossingen kan je hier vinden.