[Kombinatoryka][Teoria liczb] Dwie permutacje i podzielność.

Zadania z kółek matematycznych lub obozów przygotowujących do OM. Problemy z minionych olimpiad i konkursów matematycznych.
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.
Awatar użytkownika
Burii
Użytkownik
Użytkownik
Posty: 133
Rejestracja: 5 maja 2011, o 23:06
Płeć: Kobieta
Pomógł: 3 razy

[Kombinatoryka][Teoria liczb] Dwie permutacje i podzielność.

Post autor: Burii »

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}}\).
Awatar użytkownika
arek1357
Użytkownik
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ść.

Post autor: arek1357 »

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...
ODPOWIEDZ