Tożsamość Proizvolova

W matematyce tożsamość Proizwolowa jest tożsamością dotyczącą sum różnic dodatnich liczb całkowitych . Tożsamość została postawiona jako problem przez Wiaczesława Proizwolowa podczas Ogólnounijnych Radzieckich Olimpiad Studenckich w 1985 roku ( Savchev i Andreescu 2002 , s. 66).

Aby określić tożsamość, weź pierwsze 2 N dodatnich liczb całkowitych,

1, 2, 3, ..., 2 N - 1, 2 N ,

i podziel je na dwa podzbiory po N liczb każdy. Uporządkuj jeden podzbiór w kolejności rosnącej:

${\ Displaystyle A_ {1}A_ {2} <\ cdots <A_ {N}.}$

Uporządkuj drugi podzbiór w kolejności malejącej:

${\ Displaystyle B_ {1}> B_ {2}> \ cdots > B_ {N}.}$

Potem suma

${\ Displaystyle | A_ {1} -B_ {1} | + | A_ {2} -B_ {2} | + \ cdots + | A_ {N} -B_ {N} |}$

jest zawsze równe N ² .

Przykład

Weźmy na przykład N = 3. Zbiór liczb to zatem {1, 2, 3, 4, 5, 6}. Wybierz trzy liczby z tego zestawu, powiedzmy 2, 3 i 5. Następnie sekwencje A i B to:

ZA ₁ = 2, ZA ₂ = 3 i ZA ₃ = 5;

B ₁ = 6, B ₂ = 4 i B ₃ = 1.

Suma jest

${\ Displaystyle |A_{1}-B_{1}|+|A_{2}-B_{2}|+|A_{3}-B_{3}|=|2-6|+|3-4| +|5-1|=4+1+4=9,}$

co rzeczywiście równa się 3 ² .

Dowód

Sprytny dowód tożsamości jest następujący. Zauważ, że dla dowolnego $\ displaystyle a, b}$ to: za ${\ Displaystyle | ab | = \ max \ {a, b \} - \ min \ {a, b \}}$ . Z tego powodu wystarczy ustalić, że zbiory ${\ Displaystyle \ {\ max \ {a_ {i}, b_ {i} \}: 1 \ równoważnik i \ równoważnik n \}} i$ : ${\ Displaystyle \ {n + 1, n + 2, \ kropki, 2n \}}$ pokrywają się. liczby $,$ wystarczy pokazać, ${\ Displaystyle 1 \ równoważnik k \ równoważnik n}$ , ${\ Displaystyle \ max \ {a_ {k}, b_ {k} \}> n}$ . Załóżmy przeciwnie, że dla niektórych $…$$2$ rozważmy liczby ${\ Displaystyle a_ {1}, a_ {2}, \ kropki, a_ {k}, b_ {k}, b_ {k + 1}, \ kropki, b_ {n}}$ . Oczywiście wszystkie te liczby są różne (ze względu na konstrukcję), ale są co najwyżej $osiągnięto$ sprzeczność.

•   Sawczew, Światosław; Andreescu, Titu (2002), Miniatury matematyczne , Anneli Lax New Mathematical Library, tom. 43, Amerykańskie Stowarzyszenie Matematyczne, ISBN 0-88385-645-X .

Linki zewnętrzne

• Tożsamość Proizvolova na Cut-the-knot.org
• Ilustracja wideo (i zarys dowodu) tożsamości Proizvolova autorstwa dr Jamesa Grime'a