Ancora in piccionaia!

[Piera]

Visto che lo avete già risolto ne propongo un altro ben più difficile.
Dimostrare che in ogni partizione dei primi $ 2N $ numeri naturali in due sequenze, una decrescente e l'altra crescente, ciascuna avente $ N $ numeri, la somma dei valori assoluti delle differenze dei numeri corrispondenti è sempre $ N^2 $.
In simboli:
Se
$ a_1>a_2 > a_3 > ... > a_N $
$ b_1 < b_2 < b_3 < ... < b_N $
è una partizione dei primi $ 2N $ numeri naturali,
allora
$ |a_1 - b_1| + |a_2 - b_2| + ... + |a_N - b_N| = N^2 $.

[Simo_the_wolf]

FiQo viene per induzione... come lo fai coi piccioni?

Ciauz

[Piera]

Una dimostrazione è qui
http://www.cut-the-knot.org/Curriculum/ ... Game.shtml

[Piera]

Per chi fosse interessato :
altri esercizi (con relativa soluzione) sul principio della piccionaia sono qui:
http://www.cut-the-knot.org/do_you_know/pigeon.shtml

[piever]

Non ho visto la soluzione dei piccioni ma banalmente:
individuiamo i numeri che si sottraggono:
$ b_k $ ha $ n-k $ numeri maggiori di se stesso della sua serie, dunque $ a_k>b_k $ se e solo se $ b_k $ ha almeno n numeri maggiori di se, quindi se e solo se $ b_k\leq n $
$ a_k $ ha $ n-k $ numeri minori di se stesso della sua serie, quindi $ b_k>a_k $ se e solo se $ a_k $ ha meno di n numeri minori di se stesso, quindi se e solo se $ a_k\leq n $
Perciò vanno aggiunti i numeri da n+1 a 2n e sottratti i numeri da 1 a n. Quindi il valore che cerchiamo è $ (1+2+...+2n)-2(1+2+...+n) $. Non resta che calcolarlo. Banalmente abbiamo che $ \frac {2n(2n+1)}{2}-\frac {n(n+1)}{2}*2=n^2 $

EDIT: corretta svista

[HiTLeuLeR]

Richiamando a questo punto una riflessione di qualcun altro (qui), mi domando: a chi giova proporre un problema su questo forum e linkare, nel giro d'un paio d'ore appena, una pagina esterna che ne contiene una soluzione? Non è per far polemica, però...