[LVIII OM] I etap

[giermek]

co do 5, hmmmmm nie wiem ale wydaje mi sie ze nigdzie nie jest uzasadnione ze H',K,L,H'' leza na jednej prostej. ja to zrobilem z przenoszenia odcinkow i twierdzenia ze odcinek laczacy wierzcholek w trojkacie z ortocentrum jest rownolegly i dwa razy dluzszy od odcinka laczacego punkt przeciecia symetralnych ze srodkiem odcinka naprzeciw tego punktu. Co do mojego rozwiazania nie jestem w stu procentach pewien ze jest wystarczajace.

jest. udowadniam na poczatku, ze KL leza na srednicy. prostopadlej do OC. potem, ze trojkat CH*H** jest trojkatem opisanym na polokregu, a ze kat 90 stopni jest przy C, to sprawa zalatwiona.

co do 8.mego moglbys rozwinac do pelnego rozwiazania? ogolnie robilo sie to tak albo przez tw. o generatorze.

swoja droga 8. i 9.te sa pod tym wzgledem podobne, ze w wiekszosci rozwiazan przegadane.

pozostalo mi 12te ktore nie rokuje nadzei.

[TheButcher]

8 to mozn bylo zrobic tak jak sie udowadnia twierdzenie eulera, i powedziec, ze wtedy oczywiscie istnieje taka permutacja.

6 z ciagow jednomonotonicznych

[Aramil]

...przez tw. o generatorze.

o czym mowi to twierdzenie?

[giermek]

...przez tw. o generatorze.

o czym mowi to twierdzenie?

Dla kazdego \(\displaystyle{ p}\) bedacego liczba pierwsza istnieje takie \(\displaystyle{ g A= \{1,2,...,p-1\}}\), ze \(\displaystyle{ A = \{g^0, g^1, ... , g^{p-2}\}}\)

[Iron]

Lol, ze trzy razy w necie natknąłem się na to twierdzenie o generatorze, ale nadal nie rozumiem jakie ma zastosowanie w rozwiązaniu?

Do qsiarza: zrobiłem prawie tak samo jak Ty , ustawiłem reszty w ciąg arytmetyczny o pierwszym wyrazie 1, różnicy 1 i ostatnim p-1, wyprowadziłem ogólny wzór na (wybaczcie, jeszcze się nie zagłębiałem w TeXa ) Xk = ((lp+1)/(p-1))+1, gdzie l jest całkowitą, a k jest całkowitą >1 obrałem funkcję Xk(k), gdzie k jest indeksem i zarazem wartością reszty, napisałem dziedzinę i zbiór wartości {2,3,...,p-1}, wykazałem, że tylko x1=1 (bo wzór dotyczy całej reszty) a później udowodniłem, że funkcja w całej dziedzinie jest różnowartościowa... hmm... trzeba było udowadniać, że jest całkowite? przecież zawsze znajdzie się takie k, żeby było całkowite , w każdym razie różnowartościowość udowodniłem metodą szkolną xD

[DEXiu]

Iron a tak z ciekawości - jaka Ci wyszła dziedzina? (oczywiście zmienną jest k a nie p, tak?). Bo jak jakaś ciasnawa to niekoniecznie musi być to oczywiste, że "znajdzie się takie k, żeby było całkowite"
Co do mnie to w 8. mam podstawienie \(\displaystyle{ x_{1}=1,x_{k}=\frac{k}{k-1}\,(\mod{p})}\), w 7. odbicie całego czworościanu symetrycznie i udowodnienie, że B'CD jest szukanym trójkątem, w 6. oczywiste - AM-GM, odwracanie, sumowanie, ciągi jednom., w 5. przedłużenie KL do przecięcia z okręgiem i dowód, że obie sumy są równe promieniom.

[giermek]

Lol, ze trzy razy w necie natknąłem się na to twierdzenie o generatorze, ale nadal nie rozumiem jakie ma zastosowanie w rozwiązaniu?

rozpatrujesz cale zadanie dla dodawania mod p-1 zbioru \(\displaystyle{ \{0,1,...,p-2\}}\), a z pewnej wlasnosci tego generowania ktora ciezko mi tutaj wyjasnic (sam nie wiem dlaczego tak jest) ustawienie tych sum tak, zeby bylo dobrze jest bardzo proste.

jesli chodzi o ostatnia serie to nie mam pojecia ocb w 12, w 11. zgadlem wzor ktory dziala i mniej wiecej potrafie wytlumaczyc dlaczego taki on jest , a 9 proste, 10 srednie.

i nie mowcie, ze podpowiadam, litosci ;d

ps. ma ktos jakiegos pdfa z jakiejs ksiazki dotyczacej doglebnie teorii grafow? tak teoretycznie bardziej niz algorytmicznie. ps. cormena mam, tam nie ma tego czego szukam

[DEXiu]

giermek nie chciałbym nadużywać uprawnień, tudzież czyjejś cierpliwości, ale jeszcze jedno "litości", "przecież nie podpowiadam", "już po drugiej serii" itp. i będzie co najmniej ostrzeżenie.

[Iron]

Dexiu, wiesz, zmienną jest k, a dzidziena {2,3,...,p-1}, zbiór wartości taki sam (z tymże strzeliłem byka przy przepisywaniu, bo ogólny wzór jest zły , ale zaraz poprawię )
Tak, wiem, że wąska, ale skoro ogólny wzór wyprowadziłem z zależności pisanej jeden pod drugą, to wydawało mi się, że nie muszę już go udowadniać (bo znajdzie się takie całkowite l, że x(k) też jest całkowite , ehh... mam nadzieję, że mi zaliczą to rozwiązanie...

// ło... teraz przanalizowałem i zapomniałem napisać, że l jest najmniejszą liczbą całkowitą, dla której x jest naturalne... ale się zamotałem w tym zadaniu... pozostaje tylko mieć nadzieję, że to także nie jest błąd dyskwalifikujący rozwiązanie...

[DEXiu]

Hehe. Też próbowałem dokładnie taką drogą, ale zwątpiłem bo nie wiedziałem właśnie, jak ograniczyć to l żeby wartość ułamka zmieściła się w {1,2...,p-1} a poza tym - żeby była całkowita i parami różna dla parami różnych l. Obszedłem kongruencjami i dowodem, że dla \(\displaystyle{ k\in\{2,3,...,p-1\}}\) wartości \(\displaystyle{ \frac{k}{k-1}}\) są parami różne w \(\displaystyle{ Z_{p}-\{1\}}\)

[Rzeszut]

Iron a tak z ciekawości - jaka Ci wyszła dziedzina? (oczywiście zmienną jest k a nie p, tak?). Bo jak jakaś ciasnawa to niekoniecznie musi być to oczywiste, że "znajdzie się takie k, żeby było całkowite"
Co do mnie to w 8. mam podstawienie \(\displaystyle{ x_{1}=1,x_{k}=\frac{k}{k-1}\,(\mod{p})}\), w 7. odbicie całego czworościanu symetrycznie i udowodnienie, że B'CD jest szukanym trójkątem, w 6. oczywiste - AM-GM, odwracanie, sumowanie, ciągi jednom., w 5. przedłużenie KL do przecięcia z okręgiem i dowód, że obie sumy są równe promieniom.

Zrobiłem dokładnie tak samo.

[Iron]

Hehe. Też próbowałem dokładnie taką drogą, ale zwątpiłem bo nie wiedziałem właśnie, jak ograniczyć to l żeby wartość ułamka zmieściła się w {1,2...,p-1} a poza tym - żeby była całkowita i parami różna dla parami różnych l. Obszedłem kongruencjami i dowodem, że dla \(\displaystyle{ k\in\{2,3,...,p-1\}}\) wartości \(\displaystyle{ \frac{k}{k-1}}\) są parami różne w \(\displaystyle{ Z_{p}-\{1\}}\)

Ale l wcale nie musi, a nawet nie jest parami różne, w zasadzie to nie ma jakiejś konkretnej zależności na l , a dla najmniejszej wartość l dla której Xk jest całkowite, Xk należy do {2,3,...,p-1} bo tak jest i koniec , jedyny problem, że tego nie napisałem xD

[MarcinT]

DeXiu - Identycznie zrobiłem ósme.

siódme łatwo wektorami szło

piąte przedluzasz KO do przeciecia z okregiem (powiedzmy K') i udowadniasz ze K'K=KH

szóste rozwaliłem samym A.G.

[qsiarz]

w 8 zamiast pisac ze jest najmniejsza, wystarczylo napisac ze jest mniejsza od p. wczesniej udowodnilem ze istnieje dokladnie 1 taka liczba


jak zastosowac tw. o generatorze do rozwiazania 8? moze ktos cale to zadanie napisac?

[Marcin88]

Gdy już jest wybrany któryś spośród tych \(\displaystyle{ \phi(p-1)}\) generatorów, to ustawiając te liczby tak, by: \(\displaystyle{ x_{2k-1}\equiv g^{p-2k+1}(mod\, p)\: \: x_{2k}\equiv g^{2k-1}(mod\, p)}\) dla każdego \(\displaystyle{ k=1,2,3,...,\frac{p-1}{2}}\) łatwo zauważyć że taka permutacja spełnia warunki zadania.