h.hofstede (h.hofstede@hogeland.nl)

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.

Het bewijs.

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

 

       

h.hofstede (h.hofstede@hogeland.nl)