Matematyka.pl

Weźmy sobie jedną z takich sum, która przystaje do \(\displaystyle{ 1}\) modulo \(\displaystyle{ p}\). Niech ta suma wynosi \(\displaystyle{ a_1+a_2+\dots+a_{\frac{p-1}2}}\), gdzie \(\displaystyle{ a_i=\pm i}\). Zauważmy, że dla każdego \(\displaystyle{ s}\) wśród liczb \(\displaystyle{ a_1,a_2,\dots,a_{\frac{p-1}2}}\) dokładnie jedna przystaje do \(\displaystyle{ s}\) lub \(\displaystyle{ -s}\) modulo \(\displaystyle{ p}\). Rozważmy teraz liczby \(\displaystyle{ ra_1,ra_2,\dots,ra_{\frac{p-1}2}}\) dla pewnego \(\displaystyle{ r\not\equiv 0\mod{p}}\). Łatwo zauważyć, że wśród tych liczb również dla każdego \(\displaystyle{ s}\) dokładnie jedna przystaje do \(\displaystyle{ s}\) lub \(\displaystyle{ -s}\) modulo \(\displaystyle{ p}\). Możemy zatem jednoznacznie wyznaczyć takie liczby \(\displaystyle{ b_1,b_2,\dots,b_{\frac{p-1}2}}\), że \(\displaystyle{ b_i\equiv\pm i\mod{p}}\) i \(\displaystyle{ \{b_1,b_2,\dots,b_{\frac{p-1}2}\}=\{ra_1,ra_2,\dots,ra_{\frac{p-1}2}\}}\). Zatem dla każdego \(\displaystyle{ r}\) znaleźliśmy przyporządkowanie, które sumie przystającej do \(\displaystyle{ 1}\) modulo \(\displaystyle{ p}\) przyporządkowuje sumę przystającą do \(\displaystyle{ r}\) modulo \(\displaystyle{ p}\). Można zauważyć, że ta funkcja jest odwracalna (mnożymy przez odwrotność \(\displaystyle{ r}\) modulo \(\displaystyle{ p}\)), zatem jest bijekcją, c.k.d.

Niech \(\displaystyle{ T=PC' \cap AC, S=QC' \cap BC}\) oznaczmy okrąg opisany na \(\displaystyle{ TQPS}\) przez \(\displaystyle{ \omega}\) pokażemy, że \(\displaystyle{ \omega}\) jest okręgiem o którym mowa w zadaniu, w tym celu wystarczy wykazać, że R też należy do \(\displaystyle{ \omega}\). Ponieważ czworokąty \(\displaystyle{ RC'PB,CQC'R}\) są cykliczne, więc \(\displaystyle{ \angle C'BR=\angle C'PR=\angle TPR}\) z drugiej strony \(\displaystyle{ \angle C'BR=\angle CC'R=\angle CQR}\), więc \(\displaystyle{ \angle CQR=TQR=\angle TPR}\), więc istotnie \(\displaystyle{ R\in \omega}\), do udowodnienia tezy wystarczy teraz pokazać, że \(\displaystyle{ T=M}\). Zauważmy, że \(\displaystyle{ \angle HBA=90^{\circ}-\angle A=\angle C'BP}\), więc \(\displaystyle{ \angle TC'A=\angle A}\) co daje nam \(\displaystyle{ TA=TC'}\) oraz \(\displaystyle{ \angle TC'C=90^{\circ}-\angle A=\angle TCC'}\), wiec \(\displaystyle{ TA=TC'=TC}\) qed.
co ciekawe można zauważyć, że okrąg \(\displaystyle{ \omega}\) zawiera wszystkie środki boków czworokąta \(\displaystyle{ BCAH'}\)

Niech \(\displaystyle{ M_1}\) będzie środkiem \(\displaystyle{ H'B}\), \(\displaystyle{ N}\) środkiem \(\displaystyle{ BC}\), \(\displaystyle{ N_1}\) środkiem \(\displaystyle{ AH'}\), \(\displaystyle{ S}\) rzutem \(\displaystyle{ C'}\) na \(\displaystyle{ H'B}\). Udowadniamy, że \(\displaystyle{ PQRS}\) jest wpisany w okrąg, potem, że \(\displaystyle{ MR=MP}\) i \(\displaystyle{ M_1R=M_1P}\) oraz \(\displaystyle{ NQ=NS}\) i \(\displaystyle{ N'Q=N'S}\), zatem proste \(\displaystyle{ MM_1}\) i \(\displaystyle{ NN_1}\) zawierają \(\displaystyle{ O}\), więc \(\displaystyle{ O}\) jest środkiem obu tych prostych (przecięcie przekątnych w równoległoboku), zatem \(\displaystyle{ M=M_1}\), c.k.d.

+Fakt, że środki przeciwległych boków tworzą średnicę okręgu 8 punktów.

Niech \(\displaystyle{ f(x) = ax^2+bx+c}\). Równanie \(\displaystyle{ af(x)^2+bf(x)+c=0}\) ma 4 różne pierwiastki ujemne \(\displaystyle{ p_1,p_2,p_3,p_4}\), więc \(\displaystyle{ f(p_1)=f(p_2) = x_1}\), \(\displaystyle{ f(p_3)=f(p_4) = x_2}\), gdzie \(\displaystyle{ x_1,x_2}\) są pierwiastkami \(\displaystyle{ f(x)}\) (wynika to z tego, że równanie \(\displaystyle{ f(x) = y}\) ma co najwyżej 2 rozwiązania). Z równości \(\displaystyle{ f(p_1)=f(p_2)}\) i \(\displaystyle{ f(p_3)=f(p_4)}\) otrzymujemy \(\displaystyle{ p_1+p_2 = p_3+p_4 = -\frac{b}{a}}\). Te sumy są ujemne, więc \(\displaystyle{ b>0}\), stąd z wzorów Viete'a \(\displaystyle{ x_1+x_2 = -\frac{b}{a} < 0}\). Niech \(\displaystyle{ x_1<x_2}\), mamy \(\displaystyle{ x_1<0}\). Załóżmy, że \(\displaystyle{ x_2 \geq 0}\), wtedy z równości \(\displaystyle{ f(p_3)=f(p_4) = x_2 \geq 0}\) (załóżmy \(\displaystyle{ p_3<p_4}\)) wnioskujemy, że \(\displaystyle{ p_3 \in (-\infty,x_1]}\), \(\displaystyle{ p_4 in [x_2,infty)}\), co przeczy ujemności liczby \(\displaystyle{ p_4}\).

Zatem \(\displaystyle{ x_1,x_2 < 0}\). Stąd dla \(\displaystyle{ i=1,2,3,4}\) zachodzi \(\displaystyle{ f(p_i) < 0}\), czyli \(\displaystyle{ p_i \in (x_1,x_2)}\). Zauważmy jeszcze, że jeżeli każde z równań \(\displaystyle{ f(x) = x_1}\) i \(\displaystyle{ f(x) = x_2}\) ma 2 różne rozwiązania, to dla dowolnego \(\displaystyle{ p}\) z przedziału \(\displaystyle{ (x_1,x_2)}\) równanie \(\displaystyle{ f(x) = p}\) ma 2 różne rozwiązania należące do przedziału \(\displaystyle{ (x_1,x_2)}\)

Załóżmy, że równanie \(\displaystyle{ f_n(x) = 0}\) ma \(\displaystyle{ 2^n}\) różnych pierwiastków takich , że \(\displaystyle{ x_1<p_1<p_2<...<p_{2^n}<x_2<0}\). Wtedy \(\displaystyle{ f_{n+1}(x) = 0 \Leftrightarrow f_n(f(x)) = 0}\), zatem pierwiastkami wielomianu \(\displaystyle{ f_{n+1}}\) są pierwiastki równań \(\displaystyle{ f(x) = p_i}\) dla \(\displaystyle{ i=1,2,...,2^n}\). Każde takie równanie daje 2 pierwiastki z przedziału \(\displaystyle{ (x_1,x_2)}\), zatem wielomian \(\displaystyle{ f_{n+1}}\) ma \(\displaystyle{ 2^{n+1}}\) pierwiastków z przedziału \(\displaystyle{ (x_1,x_2)}\), co kończy dowód indukcyjny.

Wystarczają 2 pajaki. Oznaczmy przez \(\displaystyle{ (x_m,y_m)}\) współrzędne muchy. Niech pierwszy pająk porusza się na początku tak, by też miał współrzędną iksową równą \(\displaystyle{ x_m}\), a drugi tak, by osiagnął współrzędną \(\displaystyle{ y_m}\) (jest to mozliwe, bo nasza plansza jest skończona). Będziemy się teraz starali, by nasze pajaki pozostały przez następne ruchy na "krzyżu" utworzonym przez rząd i kolumnę muchy, przybliżając się do niej w miarę możliwości. Pokażemy, że ta strategia prowadzi do złapania muchy w skończonej ilości kroków. W tym celu zauważmy, że mucha zmienia w jednym ruchu tylko jedną ze swoich współrzędnych, wiec pająk który pozostał w kolumnie/wierszu z muchą może się do niej zblizyć łącznie o dwa pola lub jeśli mucha od niego uciekła o pole to znowu wrócić do poprzedniej odległości, natomiast drugi przesuwa się znowu do wiersza/kolumny muchy. Łatwo zauważyć, że w ten sposób mucha może albo zbliżyć się do naszych dwóch pająków albo pozostać w takiej samej odległości, ale plansza jest skończona, więc w końcu mucha natrafi na ktoryś z boków, a w końcu jeśli niezostanie wcześniej zjedzona zostanie zagnana do narożnika. Łatwo także zauważyć, ze jeden pająk może zdechnąć z głodu przed złapaniem muchy, więc k=2. Przenosząc rozwiazanie w większą liczbę wymiarów można zauważyć, że k=d (gdzie d to wymiar) wystarcza, ale nie wiem czy jest to najmniejsza liczba potrzebnych pająków.

Odp.: k=2
Z dowolnego ustawienia początkowego możemy w skończenie wielu ruchach doprowadzić do sytuacji, w której dwa pająki będą stały w tym samym wierszu i w sąsiadujących kolumnach. Gdy znajdą się w takim stanie, niech oba pająki zmieniają kolumnę tak, aby znaleźć się bliżej kolumny, w której znajduje się mucha. Ta kolumna może się od nich oddalić po następnym ruchu muchy, jednak plansza jest ograniczona ze wszystkich stron, a pająki mogą w skończenie wielu ruchach dojść do granicy planszy, więc muszą też w pewnym momencie dogonić muchę. Jeżeli po swoim ruchu pająki dogoniły muchę (jeśli chodzi o kolumny), mucha może im uciec o jedną kolumnę, widać jednak, że nie może uciekać w nieskończoność. Może też stać w miejscu lub ruszyć się w przeciwną stronę, niż pająki w poprzednim ruchu - w obu tych przypadkach będzie znajdowała się w tej samej kolumnie, co któryś z pająków. Jeżeli po ruchu muchy któryś z pająków jest w tej samej kolumnie, co ona, niech oba pająki poruszają się w kierunku wiersza, w którym ona się znajduje. I znowu - mucha może uciekać od wiersza, w którym znajdują się pająki, ale nie w nieskończoność - plansza jest ograniczona ze wszystkich stron. Może też ponownie uciec z kolumn, w których znajdują się pająki, jednak tak jak poprzednio - dogonią ją, a w dodatku zdążyły się już (przynajmniej w poprzednim ruchu) zbliżyć do wiersza, w którym jest mucha, czyli uciekanie w kolumnach musze nic nie da - w końcu mucha znajdzie się w którejś z kolumn razem z pająkiem, oddalona od niego tylko o jeden wiersz.

Pełne rozwiązanie dla 3D napiszę jutro, bo teraz mi się nie chce, k=2 i mechanizm jest podobny jak w 2D (ganianie po współrzędnych osobno), ale pająki ustawiamy tak, by były dwoma przeciwległymi narożnikami sześcianu 2x2x2 i może zajść sytuacja, w której będziemy ganiać po ostatniej warstwie sześcianu muchę. Ale i to zakończy się powodzeniem związanym z ograniczonością planszy i odpowiednim ustawieniem pająków.

Mógłby ktoś pokazać, czemu nie \(\displaystyle{ k=1}\)?

załóż, że się da i sprobuj pomyśleć nad sytuacją gdy pająk jest już na polu sąsiadującym z muchą : )

Nvm, zapomniałem, że mucha może czekać, sorry za zamieszanie

Panda pisze:

ad3:    

A gdy mucha jest w narożniku\(\displaystyle{ (1,1)}\), pająk na \(\displaystyle{ (2,2)}\) i ruch muchy?
Ogólnie - gdy mucha stoi przy bandzie, a pająk sąsiaduje z nią wierzchołkowo i jest ruch muchy, pająk wygrywa. Należałoby chyba pokazać, że istnieje ułożenie początkowe, w którym mucha może do tego nie dopuścić. Bez tego 6p by chyba nie było

Ruch polega na tym, że najpierw mucha przemieszcza się na pole, które ma wspólny bok z polem, na którym ona się znajduje (może też pozostać w miejscu);

i polecam jednak przemyśleć przytoczoną w moim ostatnim poscie sytuację : )

Niech \(\displaystyle{ \epsilon = cos \left( \frac{2 \pi}{p}\right) + i sin \left( \frac{2 \pi}{p}\right)}\), czyli pierwiastek pierwotny p-tego stopnia z jedności.
Przyda się lemat:
Niech \(\displaystyle{ a_0, a_1, ..., a_{p-1}}\) będą liczbami wymiernymi. Wówczas, jeśli \(\displaystyle{ \sum_{k=0}^{p-1}a_k \epsilon^k = 0}\), to \(\displaystyle{ a_0 = a_1 = ... = a_{p-1}}\).
Dowód:
niech \(\displaystyle{ p(x) = \sum_{k=0}^{p-1} x^k}\) i \(\displaystyle{ q(x) = \sum_{k=0}^{p-1}a_k x^k}\). Z założenia wielomiany \(\displaystyle{ p}\) i \(\displaystyle{ q}\) mają wspólny pierwiastek (mianowicie \(\displaystyle{ \epsilon}\)). Powszechnie znany jest fakt, iż \(\displaystyle{ p}\) jest nierozkładalny w \(\displaystyle{ Q[x]}\). Toteż, skoro \(\displaystyle{ p}\) i \(\displaystyle{ q}\) nie są wzglęnie pierwsze w \(\displaystyle{ C[x]}\), to nie są też wzglęnie pierwsze w \(\displaystyle{ Q[x]}\), co w połączeniu z nierozkładalnością \(\displaystyle{ p}\) daje \(\displaystyle{ p | q}\), co w oczywisty sposób pociąga za sobą tezę lematu.

Przejdźmy do rozwiązania zadania.
Oznaczmy przez \(\displaystyle{ X_k}\) \(\displaystyle{ (k=0,1,...,p-1)}\) liczbę tych liczb spośród rozważanych, które przystają do \(\displaystyle{ k}\) mod \(\displaystyle{ p}\). Teraz, (it's easy to see) \(\displaystyle{ \sum_{k=0}^{p-1} X_k \epsilon^k = \prod_{k=1}^{\frac{p-1}{2}} (\epsilon^k + \epsilon^{-k})}\) (wynika to z tego, że jak wymnożymy ten iloczyn, to w wykładnikach pojawią się rozważane liczby, a wykładniki można redukować mod p).
Dalej, z faktu, że \(\displaystyle{ \epsilon^{p-k} = \epsilon^{-k}}\) wynika, że
\(\displaystyle{ \prod_{k=1}^{\frac{p-1}{2}} (\epsilon^k + \epsilon^{-k}) = \prod_{k=\frac{p+1}{2}}^{p-1} (\epsilon^k + \epsilon^{-k})}\), więc oznaczając przez A szukany iloczyn, otrzymamy
\(\displaystyle{ A^2 = \prod_{k=1}^{p-1} (\epsilon^k + \epsilon^{-k}) = \prod_{k=1}^{p-1} (\frac{\epsilon^{2k} + 1}{\epsilon^k}) = \prod_{k=1}^{p-1} (\epsilon^{2k} + 1) = \prod_{k=1}^{p-1} (\epsilon^k +1) = 1}\). Ostatnia równość wynika z równości \(\displaystyle{ \frac{x^p-1}{x-1} = \prod_{k=1}^{p-1}(x-\epsilon^k)}\) po podstawieniu \(\displaystyle{ x = -1}\). Stąd otrzymujemy, że \(\displaystyle{ A = \pm 1}\). Wniosek:
\(\displaystyle{ (X_0 \pm 1) + X_1 \epsilon + ... + X_{p-1} \epsilon^{p-1} = 0}\), więc na mocy lematu
\(\displaystyle{ X_0 \pm 1 = X_1 = ... = X_{p-1}}\). Ponieważ \(\displaystyle{ \sum_{k=0}^{p-1} = 2^{\frac{p-1}{2}}}\), rozwiązując banalne równanie, dostajemy \(\displaystyle{ X_1 = (2^{\frac{p-1}{2}} \pm 1)/p}\), czyli \(\displaystyle{ X_1 = \frac{1}{p} (2^{\frac{p-1}{2}} - \left( \frac{2}{p} \right) )}\), gdzie \(\displaystyle{ \left( \frac{2}{p} \right)}\) oznacza symbol Legendre'a.