Suma z f
-
mol_ksiazkowy
- Użytkownik
- Posty: 13372
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3425 razy
- Pomógł: 809 razy
Suma z f
Jaki jest zbiór wartości wyrażenia \(\displaystyle{ \sum_{x \in X } |f(x)- x|}\) , jeśli \(\displaystyle{ f: X \to X }\) jest bijekcją zbioru \(\displaystyle{ \{ 1,..., n \} }\)
Ostatnio zmieniony 13 lip 2024, o 19:20 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
arek1357
Re: Suma z f
Bijekcja zbioru:
\(\displaystyle{ X=\left\{ 1,2,3,...,n\right\} }\)
to permutacja tegoż zbioru, każda permutacja składa się z cykli czyli:
\(\displaystyle{ \sum_{x \in X}^{} \left| f(x)-x\right| = \sum_{C_{i}}^{} \left| f(x)-x\right| }\)
Cała tajemnica tkwi w tym, że sumę tę rozbijamy na sumę cykli danej funkcji , a w cyklu mamy:
\(\displaystyle{ C: a_{1}<a_{2}<a_{3}<...<a_{k}}\)
czyli wygląda to tak:
\(\displaystyle{ a_{1} \rightarrow a_{2} \rightarrow a_{3} \rightarrow ... \rightarrow a_{n} \rightarrow a_{1}}\)
i teraz suma na takim cyklu wygląda tak:
\(\displaystyle{ \sum_{C}^{} \left| f(x)-x\right| =a_{2}-a_{1} +a_{3}-a_{2} +...+a_{n-1}-a_{n-2} +a_{n}-a_{n-1} +a_{n}-a_{1} =2a_{n}-2a_{1}}\)
Jak widać suma ta zawsze będzie parzysta , maksymalna wartość wyniesie:
\(\displaystyle{ 2n-2}\) , minimalna: \(\displaystyle{ 0}\)
więc jak zsumujemy po wszystkich cyklach, których w danej permutacji będzie wynosić \(\displaystyle{ r}\) , otrzymamy:
\(\displaystyle{ \sum_{C_{r}}^{} \left| f(x)-x\right| =2k_{1}-2+2k_{2}-2\left( k_{1}+1\right) +...+2n-2\left( k_{r}+1\right)=2n-2r}\)
gdzie:
\(\displaystyle{ C_{1}: 1,...,k_{1}}\)
\(\displaystyle{ C_{2}: k_{1}+1,...,k_{2}}\)
.......................................................................................
\(\displaystyle{ C_{r}: k_{r}+1,..., n}\)
\(\displaystyle{ r=1,...n}\)
jak widać, zbiór wartości \(\displaystyle{ W}\) tej sumy wyniesie:
\(\displaystyle{ W=\left\{ 0,2,4,6,...,2n-2\right\} }\)
Wszystkie parzyste...
np:
\(\displaystyle{ X=\left\{ 1 , 2\right\} }\)
wszystkie sumy to:
\(\displaystyle{ 2-1+2-1=2 , 1-1+2-2=0}\)
\(\displaystyle{ W=\left\{ 0,2\right\} }\)
\(\displaystyle{ X=\left\{ 1,2,3,...,n\right\} }\)
to permutacja tegoż zbioru, każda permutacja składa się z cykli czyli:
\(\displaystyle{ \sum_{x \in X}^{} \left| f(x)-x\right| = \sum_{C_{i}}^{} \left| f(x)-x\right| }\)
Cała tajemnica tkwi w tym, że sumę tę rozbijamy na sumę cykli danej funkcji , a w cyklu mamy:
\(\displaystyle{ C: a_{1}<a_{2}<a_{3}<...<a_{k}}\)
czyli wygląda to tak:
\(\displaystyle{ a_{1} \rightarrow a_{2} \rightarrow a_{3} \rightarrow ... \rightarrow a_{n} \rightarrow a_{1}}\)
i teraz suma na takim cyklu wygląda tak:
\(\displaystyle{ \sum_{C}^{} \left| f(x)-x\right| =a_{2}-a_{1} +a_{3}-a_{2} +...+a_{n-1}-a_{n-2} +a_{n}-a_{n-1} +a_{n}-a_{1} =2a_{n}-2a_{1}}\)
Jak widać suma ta zawsze będzie parzysta , maksymalna wartość wyniesie:
\(\displaystyle{ 2n-2}\) , minimalna: \(\displaystyle{ 0}\)
więc jak zsumujemy po wszystkich cyklach, których w danej permutacji będzie wynosić \(\displaystyle{ r}\) , otrzymamy:
\(\displaystyle{ \sum_{C_{r}}^{} \left| f(x)-x\right| =2k_{1}-2+2k_{2}-2\left( k_{1}+1\right) +...+2n-2\left( k_{r}+1\right)=2n-2r}\)
gdzie:
\(\displaystyle{ C_{1}: 1,...,k_{1}}\)
\(\displaystyle{ C_{2}: k_{1}+1,...,k_{2}}\)
.......................................................................................
\(\displaystyle{ C_{r}: k_{r}+1,..., n}\)
\(\displaystyle{ r=1,...n}\)
jak widać, zbiór wartości \(\displaystyle{ W}\) tej sumy wyniesie:
\(\displaystyle{ W=\left\{ 0,2,4,6,...,2n-2\right\} }\)
Wszystkie parzyste...
np:
\(\displaystyle{ X=\left\{ 1 , 2\right\} }\)
wszystkie sumy to:
\(\displaystyle{ 2-1+2-1=2 , 1-1+2-2=0}\)
\(\displaystyle{ W=\left\{ 0,2\right\} }\)
-
arek1357
Re: Suma z f
Drobna uwaga co do zadania a mianowicie w cyklach liczby nie muszą być w kolejności rosnącej, ale suma jednocyklowa
zawsze będzie wynosić:
\(\displaystyle{ 2 k_{j}-2k_{i}}\)
gdzie:
\(\displaystyle{ C: k_{j}=\max\left\{ k_{1},k_{2},...,k_{s}\right\} }\)
\(\displaystyle{ C: k_{i}=\min\left\{ k_{1},k_{2},...,k_{s}\right\} }\)
gdzie: \(\displaystyle{ s}\) - długość cyklu: \(\displaystyle{ C}\)
więc tak czy siak mój zawężający sposób zapisywania elementów cyklu w kolejności rosnącej w sumie nie wpływa na zadanie...
zawsze będzie wynosić:
\(\displaystyle{ 2 k_{j}-2k_{i}}\)
gdzie:
\(\displaystyle{ C: k_{j}=\max\left\{ k_{1},k_{2},...,k_{s}\right\} }\)
\(\displaystyle{ C: k_{i}=\min\left\{ k_{1},k_{2},...,k_{s}\right\} }\)
gdzie: \(\displaystyle{ s}\) - długość cyklu: \(\displaystyle{ C}\)
więc tak czy siak mój zawężający sposób zapisywania elementów cyklu w kolejności rosnącej w sumie nie wpływa na zadanie...
-
arek1357
-
arek1357
Re: Suma z f
Ale zauważyłem już kiedy suma cyklowa osiągnie maksimum bo ten przykład co dałeś jest przykładem permutacji ząbkowej,
piły ząbkowej bo w tym przypadku suma cyklowa będzie osiągać maksimum...
skupmy się na Twoim przykładzie:
\(\displaystyle{ (1,3,2,4)}\)
zauważyłem , że wierzchołki czyli maksima będą występować dwa razy:
\(\displaystyle{ 3-1+3-2+4-2+4-1=2 \cdot \left( 3+4\right) -2 \cdot (1+2)}\)
więc weźmy cykl o następujących elementach:
\(\displaystyle{ C: \left\{ 1,2,3,...,n,n+1,n+2,...,2n\right\} }\)
Można zauważyć, że suma cyklowa będzie maksymalna, jeżeli wierzchołkami "piły" będą największe elementy zbioru, a minima to te najmniejsze więc suma maksymalna powinna wyglądać tak:
\(\displaystyle{ 2 \cdot \left( n+1+n+2+...+2n\right) -2 \cdot \left( 1+2+...+n\right)=2n^2 }\)
jeżeli natomiast cykl składa się z nieparzystej ilości elementów... to maksimum:
\(\displaystyle{ C: \left\{ 1,2,...n, n+1, n+2,...,2n,2n+1\right\} }\)
wtedy pełnych ząbków gdzie wierzchołków będzie \(\displaystyle{ n}\) , jeden będzie tylko jednostronny, a dolinek pełnych będzie też \(\displaystyle{ n}\)
więc takie maksimum powinno wynieść:
\(\displaystyle{ 2 \cdot \left( n+2+n+3+...+2n+1\right) -2\left( 1+2+...+n\right) +n+1-(n+1)=2n^2+2n}\)
np.:
\(\displaystyle{ (1 ,4,2,5,3)}\)
\(\displaystyle{ 4-1+4-2+5-2+5-3+3-1=12=2 \cdot 2^2+2 \cdot 2=12}\)
widać, że mamy tu: \(\displaystyle{ 4,5}\) - to wierzchołki...
\(\displaystyle{ 1,2}\) - dolinki
\(\displaystyle{ 3}\) - wierzchołko-dolinka
i tylko w każdym cyklu wierzchołko-dolinki kasują się do zera...
w przykładzie parzystym:
\(\displaystyle{ (1,3,2,4)}\)
mamy w sytuacji ekstremalnej dwa wierzchołki: \(\displaystyle{ 3,4}\)
i dwie dolinki: \(\displaystyle{ 1,2}\) więc sytuacja bardziej symetryczna...,
a suma będzie maksymalna, jeżeli pełnych wierzchołków będzie jak najwięcej i będą zbudowane z największych liczb a dolinek siłą rzeczy muszą być złożone z jak najmniejszych liczb...
Oczywiście najmniejsza suma będzie zero , i każda wartość będzie parzysta...
Wiadomo, też, że nie w każdym cyklu elementy idą po kolei więc przydałoby się jeszcze uogólnić...
Ale i tak wierzchołkami będą największe elementy a dolinkami najmniejsze...i tak zawsze trzeba przeprowadzać maksymalne sumowanie...
A parzystość bierze się stąd, że każdy element w takiej sumie cyklowej zawsze występuje dwa razy...
piły ząbkowej bo w tym przypadku suma cyklowa będzie osiągać maksimum...
skupmy się na Twoim przykładzie:
\(\displaystyle{ (1,3,2,4)}\)
zauważyłem , że wierzchołki czyli maksima będą występować dwa razy:
\(\displaystyle{ 3-1+3-2+4-2+4-1=2 \cdot \left( 3+4\right) -2 \cdot (1+2)}\)
więc weźmy cykl o następujących elementach:
\(\displaystyle{ C: \left\{ 1,2,3,...,n,n+1,n+2,...,2n\right\} }\)
Można zauważyć, że suma cyklowa będzie maksymalna, jeżeli wierzchołkami "piły" będą największe elementy zbioru, a minima to te najmniejsze więc suma maksymalna powinna wyglądać tak:
\(\displaystyle{ 2 \cdot \left( n+1+n+2+...+2n\right) -2 \cdot \left( 1+2+...+n\right)=2n^2 }\)
jeżeli natomiast cykl składa się z nieparzystej ilości elementów... to maksimum:
\(\displaystyle{ C: \left\{ 1,2,...n, n+1, n+2,...,2n,2n+1\right\} }\)
wtedy pełnych ząbków gdzie wierzchołków będzie \(\displaystyle{ n}\) , jeden będzie tylko jednostronny, a dolinek pełnych będzie też \(\displaystyle{ n}\)
więc takie maksimum powinno wynieść:
\(\displaystyle{ 2 \cdot \left( n+2+n+3+...+2n+1\right) -2\left( 1+2+...+n\right) +n+1-(n+1)=2n^2+2n}\)
np.:
\(\displaystyle{ (1 ,4,2,5,3)}\)
\(\displaystyle{ 4-1+4-2+5-2+5-3+3-1=12=2 \cdot 2^2+2 \cdot 2=12}\)
widać, że mamy tu: \(\displaystyle{ 4,5}\) - to wierzchołki...
\(\displaystyle{ 1,2}\) - dolinki
\(\displaystyle{ 3}\) - wierzchołko-dolinka
i tylko w każdym cyklu wierzchołko-dolinki kasują się do zera...
w przykładzie parzystym:
\(\displaystyle{ (1,3,2,4)}\)
mamy w sytuacji ekstremalnej dwa wierzchołki: \(\displaystyle{ 3,4}\)
i dwie dolinki: \(\displaystyle{ 1,2}\) więc sytuacja bardziej symetryczna...,
a suma będzie maksymalna, jeżeli pełnych wierzchołków będzie jak najwięcej i będą zbudowane z największych liczb a dolinek siłą rzeczy muszą być złożone z jak najmniejszych liczb...
Oczywiście najmniejsza suma będzie zero , i każda wartość będzie parzysta...
Wiadomo, też, że nie w każdym cyklu elementy idą po kolei więc przydałoby się jeszcze uogólnić...
Ale i tak wierzchołkami będą największe elementy a dolinkami najmniejsze...i tak zawsze trzeba przeprowadzać maksymalne sumowanie...
A parzystość bierze się stąd, że każdy element w takiej sumie cyklowej zawsze występuje dwa razy...
Ostatnio zmieniony 16 lut 2025, o 00:06 przez arek1357, łącznie zmieniany 1 raz.
-
Dasio11
- Moderator
- Posty: 10305
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 41 razy
- Pomógł: 2429 razy
Re: Suma z f
Zamiast męczyć się z cyklami radziłbym wykazać, że permutacja "odwróć porządek" (tj. \(\displaystyle{ 1 \mapsto n, \ 2 \mapsto n-1\ldots}\)) realizuje maksimum tej sumy. A skoro każde dwie permutacje da się połączyć ciągiem transpozycji elementów sąsiednich, to stąd już wynika że wszystkimi możliwymi wartościami są liczby parzyste od zera do tegoż maksimum.
-
arek1357
Re: Suma z f
Fakt ale ząbkowanie zauważyłem pierwsze, lecz jak najbardziej z tą odwróconą permutacją ładny przykład...
tak czy siak wyjdzie:
\(\displaystyle{ 2n^2 \vee 2n^2+2n}\)
dla parzystych lub nie...
Ale bez męki można również powiedzieć, że permutacja jednocyklowa typ jak już pisałem: "maksymalna piła" również realizuje tę maksymalną sumę....
\(\displaystyle{ (1,n+1,2,n+2,3,n+3,...}\)
tak czy siak wyjdzie:
\(\displaystyle{ 2n^2 \vee 2n^2+2n}\)
dla parzystych lub nie...
Ale bez męki można również powiedzieć, że permutacja jednocyklowa typ jak już pisałem: "maksymalna piła" również realizuje tę maksymalną sumę....
\(\displaystyle{ (1,n+1,2,n+2,3,n+3,...}\)