Matematické Fórum

Marian · 16. 12. 2008 07:12 — Editoval Marian (16. 12. 2008 12:41)

Nechť
$\{ a_1,a_2,\cdots ,a_n \}\cup\{ b_1,b_2,\cdots ,b_n\} =\{m|\, m\in\mathbb{N},\, 1\le m\le 2n\}$ .
Předpokládejme, že platí $a_1<a_2\cdots <a_n$ a $b_1>b_2>\cdots >b_n$ .
Dokažte, že pro všechna přirozená čísla n je
$\Large{\sum_{j=1}^{n}|a_j-b_j|=n^2.}$

Edit.: Řešení v obecném případě jsem nenašel. Zvládl jsem jen malou část.

Pavel Brožek

Nepřítel mi předhodí nějaké množiny (uspořádané v uvedeném smyslu)

$A=\{ a_1,a_2,\cdots ,a_n \}\nl B=\{ b_1,b_2,\cdots ,b_n \}$ ,

já ale začnu od množin

$A_0=\{ 1,2,\cdots ,n\}\nl B_0=\{ 2n,2n-1,\cdots ,n+1\}$ ,

pro které si každý snadno ověří, že rovnost platí. Teď se pokusím napsat postup, jak a proč můžeme prohazovat prvky mezi těmito množinami tak, že se součet

$\Large{\sum_{j=1}^{n}|a_j-b_j|}$

nezmění.

1. Z množiny $A_0$ si vyberu největší prvek $i\leq n$ takový, že není v množině $A$ (pokud existuje). Z množiny $B_0$ vezmu prvek $2n+1-i$ (který je na stejném místě v množině B, jako i v množině A). Vybrané prvky mezi množinami prohodím, mám tedy nové uspořádané množiny

$A_1=\{ 1,2,\cdots,i-1,i+1,\cdots ,n,2n+1-i\}\nl B_1=\{ 2n,2n-1,\cdots,2n+2-i,2n-i,\cdots ,n+1,i\}$ ,

celkový součet absolutních hodnot rozdílu je stejný, protože si přísluší stejná čísla jako předtím (pouze se změnil jejich index j v sumě).

2. To samé budu dělat dokud budu mít v množině $A_1$ nějaké číslo $i\leq n$ takové, že není v množině $A$ . Snadno se přesvědčete, že prvek, kterého se zbavuji z množiny $A_1$ se vždy zařadí na konec množiny $B_1$ a příslušný prvek z množiny $B_1$ zase na konec množiny $A_1$ , součet absolutních hodnot rozdílů se tedy po celou dobu nemění.

Pavel Brožek

Množinu $A_1$ máme pomyslně rozdělenu na první část $A_1^1$ , kde jsou prvky menší nebo rovny n a na druhou část $A_1^2$ , kde jsou prvky větší než n. Podobně rozdělíme množinu $B_1$ na $B_1^1$ a $B_1^2$ , přičemž první část $B_1^1$ , která má prvky větší než n má stejně prvků jako množina $A_1^1$ . Zbývá dostat do množiny $A_1^2$ prvky z $B_1^1$ , které jsou v $A$ a zbavit se přebytečných prvků. Jestliže vezmeme

$a \in A_1^1,\qquad b \in A_1^2$

kterým přísluší (ve smyslu té sumy - mají tedy stejné j)

$c\in B_1^1,\qquad d \in B_1^2$ ,

pak pokud prohodíme mezi množinami prvky a a c a množiny nepřeuspořádáme podle velikosti, pak aby zústala suma zachována, musí platit

$|a-c|+|b-d|=|a-b|+|c-d|$ .

Vzhledem k tomu, že $a<c,\,b>d,\,a<b,\,c>d$ , to platí. Může ale nastat případ, že množiny $A_1^2$ a $B_1^1$ nyní nejsou uspořádané podle velikosti. To ale snadno napravíme, protože pokud

$x, y\in A_1^2$ , kterým přísluší $t, u\in B_1^2$ ,

můžeme x a y prohodit beze změny sumy, protože platí

$|x-t|+|y-u|=|y-t|+|x-u|$ (protože všechny argumenty absolutních hodnot jsou kladné).

Podobně pro množinu $B_1^1$ . Máme tedy množiny opět uspořádané. Popsal jsem tedy, jak si můžeme prohazovat prvky mezi $A_1^2$ a $B_1^1$ beze změny sumy, myslím, že je zřejmé, že je můžeme prohazovat tak, že nakonec docílíme toho, že upravíme $A_1^1$ přesně do podoby množiny $A$ .

Je to celkem dlouhé, takže bych se nedivil, kdyby tam byla chyba nebo to nebylo srozumitelné :-)

Marian · 18. 12. 2008 01:39

↑ BrozekP:
Zajímavá úvaha. Začal jsem uvažovat podobně, ale nedomyslel jsem to. Budu si muset rozmyslit tvé řešení a popřípadě vymyslet snad i nějaké to své.

Matematické Fórum

#1 16. 12. 2008 07:12 — Editoval Marian (16. 12. 2008 12:41)

Předvánoční součet absolutních hodnot

#2 16. 12. 2008 18:20 — Editoval BrozekP (16. 12. 2008 19:07)

Re: Předvánoční součet absolutních hodnot

#3 16. 12. 2008 19:02 — Editoval BrozekP (16. 12. 2008 19:07)

Re: Předvánoční součet absolutních hodnot

#4 18. 12. 2008 01:39

Re: Předvánoční součet absolutních hodnot