[MIX][Teoria liczb] Rozgrzewka przed drugim etapem OM

[hannahannah]

2.

Ukryta treść:    

\(\displaystyle{ I=\{1,\ldots,2p-1\}}\) oraz \(\displaystyle{ a_1,\ldots,a_{2p-1}}\) to dane liczby.

\(\displaystyle{ w(x_1,\ldots,x_{2p-1})=\sum_{P\subseteq I,\.|P|=p}\left(\sum_{i\in P}x_i\right)^{p-1}}\).

\(\displaystyle{ w=_p0}\), bo \(\displaystyle{ p}\) dzieli wszystkie współczynniki. Gdyby każda suma \(\displaystyle{ S_P=\sum_{i\in P}a_i}\) była niepodzielna przez p, to na mocy \(\displaystyle{ S_P^{p-1}=_p1}\), \(\displaystyle{ w(a_1,\ldots,a_{2p-1})=\binom{2p-1}{p}\neq 0\;\mbox{mod}\;p}\).

[Ponewor]

4 cd

Istotnie masz rację. Pozwolę sobie jeszcze zauważyć, że teza jest trywialnym wnioskiem z Wniosku z

Kod: Zaznacz cały

http://www.deltami.edu.pl/temat/matematyka/teoria_liczb/2011/03/07/O_potegach_dwojki/

11

Ukryta treść:    

ZsD dla : \(\displaystyle{ 2n+1}\) liczb \(\displaystyle{ a_j^2 - a_1^2}\) dla \(\displaystyle{ j=2, ..., 2n+2}\)

Ale wskazanych liczb jest \(\displaystyle{ n+1}\). Poza tym czym w ogóle jest \(\displaystyle{ a_{2n+2}}\)?

10

Ukryta treść:    

Jeśli \(\displaystyle{ n}\) jest nieparzyste to jest ich tyle samo
\(\displaystyle{ X =\{1, … 2n \}}\) bijekcja : \(\displaystyle{ A \mapsto X \backslash A}\)
Jesli : \(\displaystyle{ n}\) parzyste, nie jest ich tyle samo np : \(\displaystyle{ n=2}\)
\(\displaystyle{ \{ 1, 3 \}, \{ 2, 4 \}}\) dwa zbiory o sumie parzystej
\(\displaystyle{ \{ 1, 2 \}, \{ 1, 4 \}, \{ 2, 3\}, \{ 3, 4 \}}\) cztery zbiory o sumie nieparzystej

Dla pełnego rozwiązania przydałoby się wskazać tę bijekcję. Poza tym trzeba też przeprowadzić pełny dowód, że dla parzystych te liczby się różnią i jeszcze odpowiedzieć o ile.
Ogólnie, to byłoby znacznie łatwiej jakbyś bardziej szczegółowo opisywał swoje rozwiązania.

\(\displaystyle{ (a_1-a_2)^2+(b_1-b_2)^2+(a_2-a_3)^2+(b_2-b_3)^2+...+(a_{n-1}+a_n)^2+(b_{n-1}+b_n)^2+(a_n+a_1)^2+(b_n+b_1)^2}\)

Bardzo mocno byś sobie ułatwił życie, gdybyś teraz znów skorzystał z obserwacji \(\displaystyle{ a\equiv a^{2} \pmod{2}}\).
Rozwiązanie jest poprawne (poza drobnymi literówkami które widać w przytoczonym wyżej fragmencie).

[AndrzejK]

Poprawiłem literówki i faktycznie, ponowne wykorzystanie tej własności bardzo skraca rozwiązanie! Mogłem o tym pomyśleć.

[Ponewor]

13.

Ukryta treść:    

Podstawiając \(\displaystyle{ x=\frac{a}{b}}\),\(\displaystyle{ y= \frac{b}{c}}\),\(\displaystyle{ z= \frac{c}{a}}\) otrzymujemy \(\displaystyle{ x+y+z= \frac{a}{b} + \frac{b}{c} + \frac{c}{a}}\), \(\displaystyle{ xy+yz+zx= \frac{b}{a} + \frac{c}{b} + \frac{a}{c}}\) oraz \(\displaystyle{ xyz=1}\), a ponadto liczby \(\displaystyle{ x,y,z}\) są wymierne. Na mocy wzorów Viete'a istnieje zatem wielomian trzeciego stopnia o pierwszym i ostatnim współczynniku będącym liczbą \(\displaystyle{ 1}\) i wszystkich współczynnikach całkowitych, którego pierwiastkami są liczby wymierne \(\displaystyle{ x,y,z}\). Na mocy twierdzenia o wymiernych pierwiastkach wielomianu dostajemy, że liczby \(\displaystyle{ x,y,z}\) muszą mieć liczniki i mianowniki będące dzielnikami jedynki, a zatem są co do znaku równe \(\displaystyle{ 1}\) c.k.d.

No to już jest raczej blisko poprawnego rozwiązania, ale na pewno nim nie jest - przecież oczywiście może być \(\displaystyle{ a=b=c=5}\) i założenia zadania zachodzą.

A nie, przepraszam, to jest poprawne rozwiązanie.

[mol_ksiazkowy]

11 cd

Ukryta treść:    

Niech \(\displaystyle{ a_i}\) przy dzieleniu przez \(\displaystyle{ 2n}\) daje resztę \(\displaystyle{ r_i}\).
Jeśli istnieja \(\displaystyle{ i \neq j}\) że \(\displaystyle{ r_i= r_j}\) to \(\displaystyle{ a_i -a_j}\) dzieli się przez \(\displaystyle{ 2n}\)
Jeśli \(\displaystyle{ r_i \neq r_j}\) dla \(\displaystyle{ i \neq j}\) to zbiór reszt
\(\displaystyle{ \{ 0, …., 2n-1 \} = \{ 0 \} \ \cup \ \{1, 2n-1 \} \ \cup \ \{2, 2n-2 \} \ \cup .... \ \cup \{n-1, n+1 \} \ \cup \{ n \}}\) tj. suma \(\displaystyle{ n+1}\) rozłącznych podzbiorów.
Z ZsD w jednym z nich są jakieś \(\displaystyle{ r_i}\) i \(\displaystyle{ r_j}\)
tj. \(\displaystyle{ r_i+r_j=2n}\)

Uwagi: przy \(\displaystyle{ n+1}\) liczbach teza się wysypie; \(\displaystyle{ n=3}\)
liczby \(\displaystyle{ a_i}\): 0, 1, 2, 3.

można wybrać takie dwie a, b

można wybrać takie dwie różne a, b

[Ananasiatko]

Zadanie 17.

Ukryta treść:    

Podzielmy \(\displaystyle{ \{1,2,...,2p\} = X \cup Y}\), gdzie \(\displaystyle{ X=\{1,2,...,p\}}\) oraz \(\displaystyle{ Y=\{p+1,...2p\}}\) Zbiory \(\displaystyle{ X}\) i \(\displaystyle{ Y}\) modulo \(\displaystyle{ p}\) to ten sam zbiór wszystkich reszt mod \(\displaystyle{ p}\), od teraz rozpatrujmy też wszystkie działania
modulo \(\displaystyle{ p}\). Dla \(\displaystyle{ i \in \{0,1,...,p\}}\) oznaczmy przez \(\displaystyle{ a_i}\)
liczbę \(\displaystyle{ p}\)-elementowych podzbiorów zbioru \(\displaystyle{ \{1,...,2p\}}\),
które mają dokładnie \(\displaystyle{ i}\) elementów w zbiorze \(\displaystyle{ X}\)
a których suma elementów jest podzielna przez \(\displaystyle{ p}\)
Szukaną liczbą w zadaniu jest wówczas suma \(\displaystyle{ S=a_0+a_1+...a_p}\)

W dalszym ciągu wyznaczamy \(\displaystyle{ a_i}\). Jeśli \(\displaystyle{ i=0}\) lub \(\displaystyle{ i=p}\),
to \(\displaystyle{ a_i=1}\) (tutaj przydaje się nieparzystość \(\displaystyle{ p}\), aby stwierdzić, że faktycznie
cały zbiór \(\displaystyle{ X}\) (bądź \(\displaystyle{ Y}\)) ma sumę podzielną przez \(\displaystyle{ p}\)).

Załóżmy teraz, że \(\displaystyle{ 0<i<p}\), a więc \(\displaystyle{ i}\) jest względnie pierwsze z \(\displaystyle{ p}\). Rozważmy dowolny zbiór \(\displaystyle{ A\subset X}\) taki, że \(\displaystyle{ A}\) ma \(\displaystyle{ i}\) elementów.
Przez \(\displaystyle{ A+x}\) oznaczmy zbiór \(\displaystyle{ A+x=\{a+x : a\in A\}}\) (dodawanie mod \(\displaystyle{ p}\)), będący cyklicznym przesunięciem \(\displaystyle{ A}\).
Zbiory \(\displaystyle{ A}\), \(\displaystyle{ A+1}\), ... \(\displaystyle{ A+(p-1)}\) są parami różne i ich sumy elementów są parami różne modulo \(\displaystyle{ p}\) (sumy każdych dwóch kolejnych różnią się o \(\displaystyle{ i}\) modulo \(\displaystyle{ p}\)) a w dodatku są wszystkimi przesunięciami zbioru \(\displaystyle{ A}\). Zbiór
przesunięć \(\displaystyle{ A}\) nazwijmy orbitą \(\displaystyle{ A}\). Pozostaje zauważyć, że wszystkie podzbiory \(\displaystyle{ i}\)-elementowe zbioru \(\displaystyle{ X}\) możemy rozbić na rozłączne orbity pewnych
podzbiorów \(\displaystyle{ X}\) (bierzemy orbity wszystkich \(\displaystyle{ i}\)-elementowych podzbiorów i każde dwie są rozłączne lub takie same).

Wniosek stąd w szczególności taki, że dla dowolnego \(\displaystyle{ r}\) sumę dającą resztę \(\displaystyle{ r}\) przy dzieleniu przez \(\displaystyle{ p}\) ma dokładnie \(\displaystyle{ \frac{1}{p}{p \choose i}}\)
\(\displaystyle{ i}\)-elementowych podzbiorów \(\displaystyle{ X}\) (też \(\displaystyle{ Y}\)) (bo po jednym w każdej orbicie, więc \(\displaystyle{ \frac{1}{p}}\) całości). Wyznaczmy \(\displaystyle{ a_i}\). Interesuje nas liczba par
podzbiorów \(\displaystyle{ A\subset X}\), \(\displaystyle{ B\subset Y}\) takich, że \(\displaystyle{ A}\) ma \(\displaystyle{ i}\)
elementów, zaś \(\displaystyle{ B}\) ma ich \(\displaystyle{ p-i}\), oraz \(\displaystyle{ A}\) i \(\displaystyle{ B}\)
dają przeciwne reszty przy dzieleniu przez \(\displaystyle{ p}\). Zgodnie z powyższymi rozważaniami, dla dowolnego \(\displaystyle{ B\subset Y}\) mającego \(\displaystyle{ p-i}\) elementów, odpowiedni
\(\displaystyle{ A\subset X}\) możemy dobrać na dokładnie \(\displaystyle{ \frac{1}{p}{p \choose i}}\) sposobów.
Przeto \(\displaystyle{ a_i={p \choose p-i}\frac{1}{p}{p \choose i} = \frac{1}{p}{p\choose i}{p\choose p-i}}\)

Obliczamy w końcu, że

\(\displaystyle{ S=\sum_{i=0}^p a_i = \frac{1}{p}(\sum_{i=0}^p{p\choose i}{p\choose p-i})
-\frac{1}{p}{p\choose 0}{p\choose p} - \frac{1}{p}{p\choose p}{p\choose 0} +a_0+a_p
=\frac{1}{p}{2p\choose p} - \frac{2}{p} + 2 = \frac{1}{p}({2p\choose p}+2p-2)}\)

[Pinionrzek]

\(\displaystyle{ w=_p0}\) co oznacza ten zapis?

[Ponewor]

\(\displaystyle{ w \equiv 0 \pmod{p}}\)

[Pinionrzek]

Ok, dzięki

[mol_ksiazkowy]

10 cd

Ukryta treść:    

Jeśli \(\displaystyle{ n}\) jest parzyste należy rozróżnic przypadki: podzielne przez 4 lub niepodzielne.
por.

[Ponewor]

^zgrabne. Można nawet policzyć ile jest takich podzbiorów np. gdy \(\displaystyle{ n}\) jest nieparzyste, wychodziło ich \(\displaystyle{ \frac{1}{2}\binom{2n}{n}}\).

[marcin7Cd]

3.

Ukryta treść:    

Oznaczmy przez \(\displaystyle{ R_{k}}\) zbiór różnych reszt \(\displaystyle{ \pmod{n}}\) wszystkich możliwych sum elementów \(\displaystyle{ a_{1},a_{2}, ... ,a_{k}}\). Udowodnię, że \(\displaystyle{ |R_{k}|<|R_{k+1}|}\) jeśli \(\displaystyle{ |R_{k}|<n}\). Na pewno \(\displaystyle{ |R_{k}| \le |R_{k+1}|}\) (bo \(\displaystyle{ R_{k} \subseteq R_{k+1}}\)), więc trzeba wykazać niemożliwość \(\displaystyle{ |R_{k}|=|R_{k+1}|}\). Zauważmy, że zbiór \(\displaystyle{ R_{k+1}}\) otrzymamy przyłączając do zbioru \(\displaystyle{ R_{k}}\) reszty zbioru \(\displaystyle{ R_{k}}\) zwiększone o \(\displaystyle{ a_{k+1} \ \pmod{n}}\) . Gdyby po takiej operacji otrzymali byśmy taką samą liczbę reszt to znaczyło by, że każda reszta zbioru \(\displaystyle{ R_{k}}\) zwiększona o \(\displaystyle{ a_{k+1}}\) również należy do \(\displaystyle{ R_{k}}\). Rozważając zbiór takich reszt(powiększonych o \(\displaystyle{ a_{k+1}}\)) to on musi zawierać tyle samo różnych reszt co \(\displaystyle{ R_{k}}\). Co oznacza, że ten zbiór i \(\displaystyle{ R_{k}}\) muszą być takie same, więc sumy ich elementów muszą być równe. Oznaczmy przez \(\displaystyle{ S_{k}}\) sumę wszystkich reszt \(\displaystyle{ R_{k}}\). Gdyby powyższy warunek byłby spełniony to \(\displaystyle{ S_{k}\equiv S_{k}+|R_{k}|a_{k+1}\pmod{n} \Rightarrow |R_{n}|a_{k+1}\equiv 0 \pmod{n}}\) sprzeczność \(\displaystyle{ NWD(a_{k},n)=1 \ \hbox{i} \ |R_{n}|<n}\). Więc \(\displaystyle{ |R_{k'}|<|R_{k'+1}| \Rightarrow |R_{k'}|+1 \le |R_{k'+1}|}\) (jeśli \(\displaystyle{ |R_{k'}| \neq n}\)). Jeśli w któryś momencie \(\displaystyle{ |R_{k'}|=n}\) to z tego wynika \(\displaystyle{ |R_{k'+1}|=n}\) , a z tego indukcyjnie \(\displaystyle{ |R{k}|=n}\) (jeśli \(\displaystyle{ k'<k}\)). Korzystając z tych dwóch faktów można indukcyjnie udowodnić, że \(\displaystyle{ k \le |R_{k}|}\) Co kończy dowód.

[Ponewor]

\(\displaystyle{ S_{k}\equiv S_{k}+ka_{k}\pmod{n}}\)

Czy w tym momencie nie założyłeś, że tych reszt jest dokładnie \(\displaystyle{ k}\)? I tak właściwie, to nie chodziło Ci o \(\displaystyle{ a_{k+1}}\)?

[marcin7Cd]

Teraz powinno być dobrze.

[Ponewor]

i istotnie jest