Przypuśćmy, że \(\displaystyle{ a _{1}, a _{2},...,a _{n}}\) są liczbami całkowitymi takimi że \(\displaystyle{ n| a _{1}+a _{2}+...+a _{n}}\). Pokaż, że istnieją dwie permutacje \(\displaystyle{ \left( b _{1}, b _{2},..., b _{n} \right)}\) i \(\displaystyle{ \left( c _{1}, c _{2},..., c _{n} \right)}\) zbioru \(\displaystyle{ \left( 1,2,...,n\right)}\) takie, że dla każdego \(\displaystyle{ 1\le i \le n}\)
\(\displaystyle{ n| a _{i}-b _{i}-c _{i}}\).
[Kombinatoryka][Teoria liczb] Dwie permutacje i podzielność.
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
- arek1357
- Użytkownik
- Posty: 5446
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 141 razy
- Pomógł: 553 razy
Re: [Kombinatoryka][Teoria liczb] Dwie permutacje i podzielność.
Stare jak świat zadanie, ale można go sprowadzić do poziomu pierścienia modulo:
\(\displaystyle{ \ZZ_{n}}\)
w tym pierścieniu treść tego zadania mogłaby brzmieć tak:
\(\displaystyle{ a_{i}}\)
takie elementy pierścienia \(\displaystyle{ \ZZ_{n}}\) , że:
(*) \(\displaystyle{ a_{1}+a_{2}+...+a_{n}= 0 \mod n}\)
należy wykazać, że istnieją takie permutacje elementów \(\displaystyle{ (x) , (y)}\) pierścienia \(\displaystyle{ \ZZ_{n}}\),
że:
\(\displaystyle{ x_{1}+y_{1}=a_{1} \mod n}\)
\(\displaystyle{ x_{2}+y_{2}=a_{2} \mod n}\)
..............................................................................................
\(\displaystyle{ x_{n}+y_{n}=a_{n} \mod n}\)
żeby wskazać taką permutację utwórzmy macierz:
\(\displaystyle{ \begin{bmatrix} (0,0) &(0,1)&(0,2)&...&(0,n-1)\\ (1,n-1) &(1,0)&(1,1)&...&(1,n-2)\\ (2,n-2) &(2,n-1)&(2,0)&...&(2,n-3)\\..................&..............&......&..........\\ (n-1,1) &(n-1,2)&(n-1,3)&...&(n-1,0)\end{bmatrix}}\)
i teraz napiszę co to za macierz a mianowicie pierwsza kolumna to taka , w której suma elementów wynosi \(\displaystyle{ 0}\) , w drugiej suma elementów wynosi \(\displaystyle{ 1}\) , itd...
czyli każdą parę można zinterpretować jako sumę: \(\displaystyle{ x_{i}+y_{i} , i=1,2,3,...,n ; x_{i} , y_{i} \in \ZZ_{n}}\)
czyli nasze a_{i} to tylko jakaś dowolna para z kolumny gdzie: \(\displaystyle{ x_{i}+y_{i}=a_{i}}\)
teraz pokażemy ,że istnieje taki wybór par od: \(\displaystyle{ i=1 }\)do: \(\displaystyle{ n-1}\) , że ostatnia para zostanie taka , że suma ich da:
\(\displaystyle{ a_{n}=-\left( a_{1}+a_{2}+...+a_{n-1}\right) }\)
pokaże na czym to polega na przykładzie wyobraźmy sobie, że zabieramy parę: \(\displaystyle{ (2,3)}\) z tej macierzy , wtedy
ilość możliwości się nam redukuje, a mianowicie musimy wykreślić cały wiersz w którym znajduje się element: \(\displaystyle{ (2,3)}\)
oraz wszystkie elementy z całej macierzy te w których trójka znajduje się na drugim miejscu...
żeby sobie ułatwić sprawę czyli będziemy po kolei wybierać elementy czyli pary i wykreślać tylko wiersze, będziemy wybierać od: \(\displaystyle{ 1}\) do \(\displaystyle{ n-1}\) bo ten ostatni wyznaczy się sam... a dlatego , że suma elementów \(\displaystyle{ a_{i}}\) wynosi zero modulo \(\displaystyle{ n}\) ...
teraz pokażę według jakiego klucza będziemy wybierać te pary...
załóżmy zgodnie z warunkami zadania , że sumy te wynoszą:
\(\displaystyle{ a_{1} , a_{2} , a_{3} ,..., a_{n-1}}\)
czyli wybieramy od: \(\displaystyle{ 1}\) do: \(\displaystyle{ n-1}\)
\(\displaystyle{ (x_{1} , y_{1}) , (x_{2}, y_{2}) , (x_{3} , y_{3}),..., (x_{n-1} , y_{n-1} )}\)
gdzie: \(\displaystyle{ x_{1}+y_{1}=a_{1} , x_{2}+y_{2}=a_{2} ,..., x_{n-1}+y_{n-1}=a_{n-1}}\)
tak możemy robić ponieważ w każdej kolumnie mamy różne \(\displaystyle{ x_{i}}\) i w każdym wierszu mamy różne \(\displaystyle{ y_{i} }\) co nam gwarantuje, że żadne dwie pary z tego wyboru nie będą leżeć ani w jednym wierszu ani w jednej kolumnie...
czyli wykreślimy wszystkie wiersze , zostanie tylko jeden wiersz , ale dzięki temu, że w tej macierzy w każdej kolumnie , wszystkie \(\displaystyle{ x_{i}}\) są między sobą różne , i w każdym wierszu wszystkie \(\displaystyle{ y_{i}}\) różne
zostanie nam w tym wierszu , w którym ,żeśmy nic nie wykreślili wszystkie elementy \(\displaystyle{ x_{i}}\) - równe ,
a wszystkie elementy: \(\displaystyle{ y_{i}}\) różne, ponieważ zostaje nam do wykreślenia z tego ostatniego wiersza wszystkie elementy (pary), których współrzędne: \(\displaystyle{ y_{i}=0 , 1 , 2 , 3,...,n-2}\) , więc zostanie ostatni element:
\(\displaystyle{ (n-1 , y_{n})}\) gdzie:
\(\displaystyle{ y_{n}+n-1=a_{n}}\)
cnd...
zrobię przykład: dla pierścienia:
\(\displaystyle{ \ZZ_{4} }\)
najpierw macierz:
\(\displaystyle{ \begin{bmatrix} (0,0) &(0,1)&(0,2)&(0,3)\\ (1,3) &(1,0)&(1,1)&(1,2)\\ (2,2) &(2,3)&(2,0)&(2,1)\\ (3,1) &(3,2)&(3,3)&(3,0)\end{bmatrix}}\)
niech np.:
\(\displaystyle{ a_{1}=1 , a_{2}=2 , a_{3}=2 , a_{4}=3 }\)
według tego klucza co pisałem wybieramy takie pary np.:
\(\displaystyle{ (0,1) ; (2,0) ; (3,3)}\)
skreślamy więc: pierwszy, trzeci i czwarty wiersz...
zostają elementy drugiego wiersza:
\(\displaystyle{ (1,3) ; (1,0) ; (1,1) ; (1,2)}\)
teraz wykreślamy z drugiego wiersza te elementy dla których:
\(\displaystyle{ y_{i}=1,0,3}\)
zostanie para: \(\displaystyle{ (1,2)}\)
ale w tej parze rzeczywiście:
\(\displaystyle{ 1+2=3 \mod 4}\)
co zgodne jest z tym, że:
\(\displaystyle{ a_{4}=3}\)
cnd...
\(\displaystyle{ \ZZ_{n}}\)
w tym pierścieniu treść tego zadania mogłaby brzmieć tak:
\(\displaystyle{ a_{i}}\)
takie elementy pierścienia \(\displaystyle{ \ZZ_{n}}\) , że:
(*) \(\displaystyle{ a_{1}+a_{2}+...+a_{n}= 0 \mod n}\)
należy wykazać, że istnieją takie permutacje elementów \(\displaystyle{ (x) , (y)}\) pierścienia \(\displaystyle{ \ZZ_{n}}\),
że:
\(\displaystyle{ x_{1}+y_{1}=a_{1} \mod n}\)
\(\displaystyle{ x_{2}+y_{2}=a_{2} \mod n}\)
..............................................................................................
\(\displaystyle{ x_{n}+y_{n}=a_{n} \mod n}\)
żeby wskazać taką permutację utwórzmy macierz:
\(\displaystyle{ \begin{bmatrix} (0,0) &(0,1)&(0,2)&...&(0,n-1)\\ (1,n-1) &(1,0)&(1,1)&...&(1,n-2)\\ (2,n-2) &(2,n-1)&(2,0)&...&(2,n-3)\\..................&..............&......&..........\\ (n-1,1) &(n-1,2)&(n-1,3)&...&(n-1,0)\end{bmatrix}}\)
i teraz napiszę co to za macierz a mianowicie pierwsza kolumna to taka , w której suma elementów wynosi \(\displaystyle{ 0}\) , w drugiej suma elementów wynosi \(\displaystyle{ 1}\) , itd...
czyli każdą parę można zinterpretować jako sumę: \(\displaystyle{ x_{i}+y_{i} , i=1,2,3,...,n ; x_{i} , y_{i} \in \ZZ_{n}}\)
czyli nasze a_{i} to tylko jakaś dowolna para z kolumny gdzie: \(\displaystyle{ x_{i}+y_{i}=a_{i}}\)
teraz pokażemy ,że istnieje taki wybór par od: \(\displaystyle{ i=1 }\)do: \(\displaystyle{ n-1}\) , że ostatnia para zostanie taka , że suma ich da:
\(\displaystyle{ a_{n}=-\left( a_{1}+a_{2}+...+a_{n-1}\right) }\)
pokaże na czym to polega na przykładzie wyobraźmy sobie, że zabieramy parę: \(\displaystyle{ (2,3)}\) z tej macierzy , wtedy
ilość możliwości się nam redukuje, a mianowicie musimy wykreślić cały wiersz w którym znajduje się element: \(\displaystyle{ (2,3)}\)
oraz wszystkie elementy z całej macierzy te w których trójka znajduje się na drugim miejscu...
żeby sobie ułatwić sprawę czyli będziemy po kolei wybierać elementy czyli pary i wykreślać tylko wiersze, będziemy wybierać od: \(\displaystyle{ 1}\) do \(\displaystyle{ n-1}\) bo ten ostatni wyznaczy się sam... a dlatego , że suma elementów \(\displaystyle{ a_{i}}\) wynosi zero modulo \(\displaystyle{ n}\) ...
teraz pokażę według jakiego klucza będziemy wybierać te pary...
załóżmy zgodnie z warunkami zadania , że sumy te wynoszą:
\(\displaystyle{ a_{1} , a_{2} , a_{3} ,..., a_{n-1}}\)
czyli wybieramy od: \(\displaystyle{ 1}\) do: \(\displaystyle{ n-1}\)
\(\displaystyle{ (x_{1} , y_{1}) , (x_{2}, y_{2}) , (x_{3} , y_{3}),..., (x_{n-1} , y_{n-1} )}\)
gdzie: \(\displaystyle{ x_{1}+y_{1}=a_{1} , x_{2}+y_{2}=a_{2} ,..., x_{n-1}+y_{n-1}=a_{n-1}}\)
tak możemy robić ponieważ w każdej kolumnie mamy różne \(\displaystyle{ x_{i}}\) i w każdym wierszu mamy różne \(\displaystyle{ y_{i} }\) co nam gwarantuje, że żadne dwie pary z tego wyboru nie będą leżeć ani w jednym wierszu ani w jednej kolumnie...
czyli wykreślimy wszystkie wiersze , zostanie tylko jeden wiersz , ale dzięki temu, że w tej macierzy w każdej kolumnie , wszystkie \(\displaystyle{ x_{i}}\) są między sobą różne , i w każdym wierszu wszystkie \(\displaystyle{ y_{i}}\) różne
zostanie nam w tym wierszu , w którym ,żeśmy nic nie wykreślili wszystkie elementy \(\displaystyle{ x_{i}}\) - równe ,
a wszystkie elementy: \(\displaystyle{ y_{i}}\) różne, ponieważ zostaje nam do wykreślenia z tego ostatniego wiersza wszystkie elementy (pary), których współrzędne: \(\displaystyle{ y_{i}=0 , 1 , 2 , 3,...,n-2}\) , więc zostanie ostatni element:
\(\displaystyle{ (n-1 , y_{n})}\) gdzie:
\(\displaystyle{ y_{n}+n-1=a_{n}}\)
cnd...
zrobię przykład: dla pierścienia:
\(\displaystyle{ \ZZ_{4} }\)
najpierw macierz:
\(\displaystyle{ \begin{bmatrix} (0,0) &(0,1)&(0,2)&(0,3)\\ (1,3) &(1,0)&(1,1)&(1,2)\\ (2,2) &(2,3)&(2,0)&(2,1)\\ (3,1) &(3,2)&(3,3)&(3,0)\end{bmatrix}}\)
niech np.:
\(\displaystyle{ a_{1}=1 , a_{2}=2 , a_{3}=2 , a_{4}=3 }\)
według tego klucza co pisałem wybieramy takie pary np.:
\(\displaystyle{ (0,1) ; (2,0) ; (3,3)}\)
skreślamy więc: pierwszy, trzeci i czwarty wiersz...
zostają elementy drugiego wiersza:
\(\displaystyle{ (1,3) ; (1,0) ; (1,1) ; (1,2)}\)
teraz wykreślamy z drugiego wiersza te elementy dla których:
\(\displaystyle{ y_{i}=1,0,3}\)
zostanie para: \(\displaystyle{ (1,2)}\)
ale w tej parze rzeczywiście:
\(\displaystyle{ 1+2=3 \mod 4}\)
co zgodne jest z tym, że:
\(\displaystyle{ a_{4}=3}\)
cnd...