eigensachp van Proizvolov

© 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 N² 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 5².

Het bewijs.

Noem de beide rijen a₁ < a₂ < a₃ < .... en b₁ > b₂ > b₃ > ....
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 (a_i, b_i) nooit in dezelfde helft kan zitten.

Het bewijs daarvan:
Stel dat beiden in de eerste helft zitten, dus dat a_i < N + 1 en b_i < N + 1
Omdat de a's van klein naar groot staan zijn er nog N + 1 - i getallen onder a_i
Omdat de b's van groot naar klein staan zijn er nog i getallen onder b_i.
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}
= ¹/₂ • 2N • (2N + 1) - 2 • ¹/₂ • N • (N + 1)
= 2N² + N - N² - N
= N²