| De
verbazingwekkende eigenschap van Proizvolov |
|
|
Verdeel de eerste 2N natuurlijke getallen in twee
willekeurige maar even grote groepen.
Zet groep 1 in volgorde van klein naar groot en groep 2 in
volgorde van groot naar klein.
Tel alle verschillen (absolute waarde) van overeenkomstige
getallen uit beide rijen bij elkaar op.
Daar komt altijd N2 uit!!! |
|
|
|
|
Voorbeeldje: neem 1, 2, 3, 4,
5, 6, 7, 8, 9, 10
Twee willekeurige groepen: 1, 3, 5, 6, 7
en 2, 4, 8, 9, 10
Dalend en stijgend: 1, 3, 5, 6, 7 en 10, 9, 8,
4, 2
Verschillen optellen: 9 + 6 + 3 + 2 + 5 =
25 JAWEL HOOR! precies 52. |
|
|
Noem de beide rijen a1
< a2 < a3 <
.... en b1 > b2
> b3 > ....
Verdeel de oorspronkelijke verzameling in de eerste helft EH =
{1, 2, 3, ..., N} en de tweede helft TH = {N + 1, N + 2, ...,
2N}
Dan blijkt dat een koppel (ai, bi)
nooit in dezelfde helft kan zitten.
Het bewijs daarvan:
Stel dat beiden in de eerste helft zitten, dus dat ai
< N + 1 en bi < N + 1
Omdat de a's van klein naar groot staan zijn
er nog N + 1 - i getallen onder ai
Omdat de b's van groot naar klein staan zijn
er nog i getallen onder bi.
Samen geeft dat N + 1 - i + i = N + 1
verschillende getallen kleiner dan N + 1
En dat kan niet.
Als beiden in de tweede helft zitten gaat het bewijs precies zo.
Conclusie: beiden zitten in verschillende helften.
Dat betekent dat bij het optellen van alle verschillen
steeds eentje uit de eerste helft wordt afgetrokken van eentje
uit de tweede helft.
Samen geeft dat de hele tweede helft min de eerste helft:
{(N + 1) + (N + 2) + (N +3) + ... + 2N } - {1 + 2 + 3 + ... + N}
= {1 + 2 + 3 + ... + 2N} - 2 • {1 + 2 + 3 + ... + N}
= 1/2 • 2N • (2N
+ 1) - 2 • 1/2 •
N • (N + 1)
= 2N2 + N - N2 - N
= N2 |
|
|
|
|
|