[LX OM] I etap

[danioto]

A jeśli tak mogę zapytać, to jak porównujecie 3 serię z wcześniejszymi? ;>
A u mnie:
9. Symetria środkowa
10. Pokazanie, że M należy do okręgu, później z trójkątów równoramiennych
11. Tysiące pomysłów, dziesiątki zapisanych stron i pusta wysłana pusta kartka (tak! nie lubię nierówności!)
12. Pokazanie tak samo jak wcześniej, że końcową liczbę da się przedstawić w postaci:
\(\displaystyle{ \sum_{i=0}^{p-1} 2^{i} \cdot x_{i}}\)
Gdzie \(\displaystyle{ x_{i}}\) to permutacja zbioru \(\displaystyle{ \{1;2....p-1\}}\) odpowiadająca odwrotności kolejności skreślania. Następnie pokazuję sposób takiego skreślania, że owa suma jets podzielna przez p. Rozpatruję dwa przypadki:
I) 2 - reszta kwadratowa p, wtedy z Twierdzenia Eulera
\(\displaystyle{ \\ 2^{ \frac{p-1}{2}} \equiv 1 (mod \ p)}\) Więc \(\displaystyle{ 2^{{n}} \cdot x + 2^{n+ \frac{p-1}{2}} \cdot (p-x) \equiv 0 (mod \ p) \\}\),
gdzie przy odpowiednich założeniach dla n. Czyli warunki zadania spełniają wszystkie liczby pierwsze, dla których 2 to reszta kwadratowa.
II) 2 - niereszta kwadratowa p, wtedy permutacją zbioru reszt przy dzieleniu ziobru \(\displaystyle{ \{2^{0},2^{1}...2^{p-2}\}}\) jest zbiór \(\displaystyle{ \{1,2...(p-1)\}}\). Mamy teraz dwa zbiory \(\displaystyle{ \{1,2...(p-1)\}}\), które łączymy w ten sposób, że każdemu wyrazowi z jednego zbioru przeporządkowujemy taki sam drugiego zbioru, otrzymujemy \(\displaystyle{ 1^{2} + 2^{2} + ... + (p-1)^2 = \frac{(p-1)(p)(2p+1)}{6}}\) co przystaje do zera modulo p, dla każdego \(\displaystyle{ p \equiv 1 (mod \ p) \vee p \equiv 5 (mod \ p)}\) z czego wynika, że p>3.

[Landru]

Czy udało się komukolwiek z Was dojść do tego, że jeśli dla pewnego p można tak skreślać liczby po lewej strony tablicy, że liczba powstała po prawej jest podzielna przez p, to istnieją również p-2 inne sposoby skreślania, by uzyskać żądaną podzielność?

tak, istnieje nawet więcej sposobów. Jeden z nich to przepisywanie liczb po kolei od najmniejszej do największej aż się dojdzie do połowy i wtedy zaczynamy przepisywać od największej:
1,2,3,...,(p-1)/2,(p-1),(p-2),(p-3),...,((p-1)/2)+1
Okazuje się, że podzielną przez p liczbę uzyskamy także po każdym obrocie tego ciągu. przez obroty mam tu na myśli tego typu zmiany kolejności:
a,b,c,d
d,a,b,c
c,d,a,b
b,c,d,a
ale i tak istnieje znacznie więcej możliwości.

[xiikzodz]

O, czyli nie musze poprawiac. danioto mnie wyreczyl.

[ojciec_kogut]

Apropos 12, to trochę was nie rozumiem.

Przecież dla dowolnego p mamy że końcowe liczby mogą być tylko postac
\(\displaystyle{ \sum_{i=1}^{p-1} i\tau(i)}\) gdzie \(\displaystyle{ \tau(i)}\) to permutacja zbioru \(\displaystyle{ {1 , 2,3,..,p-1}}\). Biorąc permutację tożsamościową mamy \(\displaystyle{ \sum_{i=1}^{p-1} i^2}\) a to dzieli p dla p>3 i \(\displaystyle{ p P}\)

Nie może tak być?

[michaln90]

ja dowodziłem tak jak sylwek, rozważając 3 przypadki

[Sylwek]

Rozpatruję dwa przypadki:

Nie wiem co to Twierdzenie Eulera, ale w żadnym ze swoich przypadków nie rozpatrujesz przypadku, w którym występuje np. p=43, czyli jeśli przyjmiemy za t najmniejszą liczbę naturalną, że \(\displaystyle{ 2^t \equiv 1 \ (mod \ p)}\), to brakuje Ci przypadku, gdzie \(\displaystyle{ \frac{p-1}{t}}\) jest nieparzysta i większa od jedynki (dla p=43 mamy t=14, więc (p-1)/t=3).

O, czyli nie musze poprawiac. danioto mnie wyreczyl.

Jednak Cię nie wyręczył

Przecież dla dowolnego p mamy że końcowe liczby mogą być tylko postac

Nie bardzo, wówczas z tego by wynikało, że zawsze t=p-1 (co to jest t - patrz powyżej), a to nie jest prawda, np. p=7, p=43, itp.

[Swistak]

9 IMHO zdecydowanie najprostsze zadanie (w połowie zadań z grami na tablicach stosuje się symetrię...) - symetria środkowa
Mi 10 zajęło 30 minut i ja je zrobiłem tak:
Udowodniłem, że punkty X,Y,B,C leżą na jednym okręgu o środku M, gdzie X i Y to środki okręgów dopisanych. Zrobiłem to korzystająć z faktu, że kąte między dwusiecznymi kątów przyległych wynosi 90 stopni. Potem łatwo z kątów i sumy kątów w czworokącie udowodniłem, że kątCXY+katBYX=120 stopni, a z trojkąta prostokątnego jeszcze katBXY+katBYX=90 stopni, więć kat CYB=30 stopni i wtedy katCMB=60 z wpisanego i środkowego. Z tego wynika, że punkty C,B,A,M leżą na jednym okręgu. Dalej, że punkt P, punkt O i punkt M leżą na symetralnej odcinka BC, więc PM to średnica, a bardzo prostym wnioskiem jest, że BM to odcinek o długośći promienia, więc mamy tezę.
W 11, najpierw, że \(\displaystyle{ (a+\frac{1}{a}^{a}}\) jest ciągiem rosnącym, potem, że jeżeli ciąg \(\displaystyle{ b_{1}, b_{2}, b_(3}...}\) jest ciągiem rosnącym, to \(\displaystyle{ \sqrt[n-1]{b_{1} b_{2} ... b_{n-1}} ... b_{n}}}\), potem za \(\displaystyle{ b_{n}}\) podstawiam \(\displaystyle{ (\frac{n+1}{n})^{n}}\) i te wartości podstawiam do tych pierwiastków i wychodzi, że \(\displaystyle{ \sqrt[n-1]{\frac{n^{n-1}}{(n-1)!}}}\)

[Zygmunt Freud]

Okazuje się, że podzielną przez p liczbę uzyskamy także po każdym obrocie tego ciągu. przez obroty mam tu na myśli tego typu zmiany kolejności:
a,b,c,d
d,a,b,c
c,d,a,b
b,c,d,a
ale i tak istnieje znacznie więcej możliwości.

dostałem właśnie to samo - w moim przypadku pomocne było małe twierdzenie Fermata. Z niego uzyskałem także informację, że jeżeli liczba po prawej stronie dzieli się przez p, to istnieje również taki sposób skreślenia liczb 1,2,3...,(p-2), że uzyskana po prawej stronie liczba również dzieli się przez p.

[danioto]

Nie wiem co to Twierdzenie Eulera

To tiwerdzenie, że \(\displaystyle{ a^{\frac{p-1}{2}} \equiv 1 \ (mod \ p)}\), wtedy i tylko wtedy kiedy \(\displaystyle{ a}\) to reszta kwadratowa.

A jeśli chodzi o 43, to:
2 to niereszta kwadratowa 43, więc \(\displaystyle{ 2^{\frac{43-1}{2}} \equiv (-1) \ (mod \ 43)}\), więc przyporządkowuję tak, jak to wcześniej opisałem, czyli reszty dzielenia zbioru \(\displaystyle{ \{2^{0},2^{1}...2^{42}\}}\) przez 43 będą permutajcją zbioru \(\displaystyle{ \{1,2...42}\}}\), następnie przyporządkowujemy:
\(\displaystyle{ \{1^{2},2^{2}....42^{2}\}}\)
Co jest podzielne przez 43 według przystawania modulo.

Więc jednak wyręczył

Edit:
A właśnie. Mam pytanie. Co mam zrobić, by nawet jak się nie dostanę to mieć wyniki w ręku? Napisać do swojego okręgu z takową prośbą, czy jak?

[pier2]

A kiedy można spodziewać się list zakwalifikowanych do II etapu?

[Sylwek]

przez 43 będą permutajcją zbioru

Wydaje mi się, że jest zupełnie przeciwnie. Możesz sprawdzić sam, że \(\displaystyle{ 2^{14} \equiv 1 \ (mod \ 43)}\) i to jest najmniejszy wykładnik o tej właściwości, z czego wynika, że każda z reszt z dzielenia tych liczb: \(\displaystyle{ \{2^{0},2^{1}...2^{41}\}}\) przez 43 będzie się zawierały w zbiorze czternastu reszt z dzielenia liczb: \(\displaystyle{ \{2^{0},2^{1}...2^{13}\}}\) przez 43.

[michaln90]

Daniato wcisnąłeś po prostu blefa. Należało rozważyć przecież sytuację taką że 2 do potęgi p-1/t przystaje do 1 mod p i na pewno nie dało się ominąć głupawym stwierdzeniu o resztach niekwadratowych. Z kolei twierdzenie Eulera nie jest tutaj przydatne, gdyż po prostu oddzielnie rozważam przypadek 2 do potęgi p-1/2 przystaje do 1 mod p.

[danioto]

Aj.. masz rację. Luka w dowodzie, a już się cieszyłem na owo rozwiązanie Ale szczerze powiedziawszy to wydaje mi się, że dałoby się ją załatać - dwie linijki komentarza by wystarczyły. Szkoda, że nie przeanalizowałem dokładniej.

Edit:
Głupawym stwierdzniem?

[michaln90]

Założenia zadania spełniają wszystkie liczby pierwsze większe od 3. Tylko ty po prostu nie udowodnilweś 1 z 3 przypadków. Prawdopodobnie dostaniesz 2 punkty.

[danioto]

Tak. Dałoby się to załatwić w maksymalnie 3 linijkach komentarza, lecz... Cóż. Prawdopodobnie tak - 2 punkty, lecz proszę ogranicz się do nieużywania takich stwierdzeń "głupawym stwierdzeniem" - o ile mi wiadomo, to każdy się ma prawo mylić, szczególnie ktoś kto dopiero zaczyna z OM swoją przygodę. Nieprawdaż?