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.
Najpierw redukujemy problem do przypadku \(\displaystyle{ x=3^{i}, y=5^{j}}\) bądź na odwrót, a potem dzięki kochanemu wzorkowi na różnicę kwadratów sprowadzamy te przypadki do równań \(\displaystyle{ 3^{i}=2^{m}-1}\) oraz \(\displaystyle{ 5^{j}=2{n}-1}\) a to nie są trudne równania. W sumie idea bardzo podobna.
Miałem też zupełnie inny pomysł, który zahaczal o to, że całkowitych dodatnich potęg dwójki nie da się przedstawić w postaci sumy kolejnych liczb naturalnych, ale niestety coś za bardzo się on paprał.
Jeśli chcesz, to możesz już wrzucać następne zadanie.
Równoważnie mamy \(\displaystyle{ z=\frac{\left(x^{2}-2\right)^{2}+1}{y^{2}-1}}\)
czyli ten ułamek ma być liczbą całkowitą.
Jeżeli \(\displaystyle{ y}\) jest liczbą nieparzystą, to \(\displaystyle{ y^{2}\equiv 1\pmod{8}}\), tj. \(\displaystyle{ 8|\left(y^{2}-1\right)}\). Jednakowoż mamy \(\displaystyle{ x^2\equiv 1 \pmod{4}\vee x^{2}\equiv 0\pmod{4}}\)
I w pierwszym przypadku licznik przystaje do \(\displaystyle{ 2\pmod{8}}\) a w drugim do \(\displaystyle{ 5\pmod{8}}\), a więc w żadnym z tych przypadków nie dzieli się przez osiem.
Zatem \(\displaystyle{ y}\) musi być parzyste, a wtedy \(\displaystyle{ y^{2}-1\equiv 3\pmod{4}}\)
Łatwo udowodnić nie wprost, że wtedy \(\displaystyle{ y^{2}-1}\) ma dzielnik pierwszy postaci \(\displaystyle{ 4k+3, \ k\in \NN}\)
co zostawiam jako ćwiczenie dla Czytelnika.
Weźmy taki dzielnik \(\displaystyle{ p=4k+3}\) i załóżmy nie wprost, że dzieli on liczbę \(\displaystyle{ \left(x^{2}-2\right)^{2}+1}\)
Oczywiście wtedy \(\displaystyle{ \left(p, x^{2}-2\right)=1}\)
toteż z MTF mamy \(\displaystyle{ \left(x^{2}-2\right)^{4k+2}\equiv 1\pmod{p}}\)
Z drugiej strony skoro \(\displaystyle{ \left(x^{2}-2\right)^2\equiv -1\pmod{p}}\), to \(\displaystyle{ \left(x^2-2\right)^{4k+2}\equiv -1\pmod{p}}\)
a to jest sprzeczność.
Okazuje się więc, że równanie nie ma rozwiązania.
Dodano po 1 dniu 53 minutach 43 sekundach: Nowe zadanie:
czy istnieje taka liczba pierwsza \(\displaystyle{ p\neq 3}\) i liczby całkowite \(\displaystyle{ a,b,c}\) niepodzielnie przez \(\displaystyle{ p}\), że \(\displaystyle{ p}\) dzieli obie liczby \(\displaystyle{ a+b+c, \ a^3+b^3+c^3}\)
Zauważyłem, że nie może być \(\displaystyle{ y^{2}-1=1}\) i pomyślałem, że przecież \(\displaystyle{ y^{2}-1}\) jest przeważnie dodatnie i wyraźnie wygląda na złożone, bo różnica kwadratów, ale przegapiłem \(\displaystyle{ y^{2}-1=-1}\)
To jeszcze dodam w takim razie uzasadnienie, że dodatnia liczba złożona postaci \(\displaystyle{ 4k+3}\) ma dzielnik pierwszy postaci \(\displaystyle{ p=4l+3}\). Oczywiście \(\displaystyle{ 4k+3}\) jest liczbą nieparzystą. Przypuśćmy nie wprost, że wszystkie dzielniki pierwsze tej liczby przystają do \(\displaystyle{ 1\pmod{4}}\), tj. \(\displaystyle{ 4k+3=\prod_{i=1}^{m}p_{i}^{\alpha_{i}}, \ p_{i}\in\ \PP, \ \ p_{i}\equiv 1\pmod{4}}\).
No ale wtedy \(\displaystyle{ p_{i}^{\alpha_{i}}\equiv 1\pmod{4}}\) i \(\displaystyle{ \prod_{i=1}^{m}p_{i}^{\alpha_{i}}\equiv 1\pmod{4}}\)
a to jest sprzeczność.
Jeśli \(\displaystyle{ y=0}\), to równanie spełnia dowolne \(\displaystyle{ x\in \ZZ}\) i \(\displaystyle{ z_{x}=-x^{4}+4x^{2}-5}\)
czyli rozwiązania to trójki \(\displaystyle{ (x,y,z)=\left(t,0, -t^{4}+4t^{2}-5\right)}\)
Aksjologiczna nienawiść do zera, tak jak i do zbioru pustego, na zawsze w sercu mym.
Aktualne zadanie:
czy istnieje taka liczba pierwsza \(\displaystyle{ p\neq 3}\) i liczby całkowite \(\displaystyle{ a,b,c}\) niepodzielnie przez \(\displaystyle{ p}\), że \(\displaystyle{ p}\) dzieli obie liczby \(\displaystyle{ a+b+c, \ a^3+b^3+c^3}\)
Załóżmy, nie wprost, że istnieje pewna liczba pierwsza \(\displaystyle{ p \neq 3}\), która dzieli równocześnie obie z tych liczb. Wówczas \(\displaystyle{ p \nmid a \ \wedge p \nmid b \ \wedge p \nmid c \ \wedge a+b+c \ \equiv 0 \pmod{p} \wedge a^3 + b^3 + c^3 \equiv 0 \pmod{p}}\)
A wiec \(\displaystyle{ a+b \equiv -c \pmod{p} \Rightarrow (a+b)^2 \equiv c^2 \pmod{p}}\) \(\displaystyle{ a^3 + b^3 + c^3 = (a+b)(a^2 - ab + b^2) + c^3 \equiv -c(a^2 - ab + b^2) + c^3 = -c(a^2 + 2ab - 3ab + b^2) + c^3 = \\ = -c((a+b)^2 - 3ab) + c^3 = c(c^2 - (a+b)^2 + 3ab) \equiv c \cdot 3ab = 3abc \equiv 0 \pmod{p} \Leftrightarrow p \mid 3abc \Rightarrow p \mid abc}\)
Jest to jednak niemożliwe, bo \(\displaystyle{ p}\) nie dzieli żadnej z liczb \(\displaystyle{ a, b, c}\). Stąd wynika, że nie istnieje liczba pierwsza różna od \(\displaystyle{ 3}\) dzieląca równocześnie obie te liczby.
Jest OK, wrzucaj nowe zadanie. Mnie to się od razu kojarzy z tożsamością \(\displaystyle{ a^{3}+b^{3}+c^{3}=3abc+(a+b+c)\left(a^{2}+b^{2}+c^{2}-ab-bc-ca\right)}\), ale jak widać, można się elegancko obyć bez tego.
Wystarczy zauważyć, że \(\displaystyle{ x^{y}+y^{x}=x^{y}+1^{y}+y^{x}-1^{x}=x^{y}-1^{y}+y^{x}+1^{x}}\) i skorzystać ze wzorów na różnicę potęg naturalnych oraz sumę naturalnych nieparzystych potęg, reszta to tzw. pseudointelektualny bełkot.
Ponieważ \(\displaystyle{ \NWD(x+1, x-1)\le 2}\), więc dowolna liczba pierwsza \(\displaystyle{ p>2}\) dzieli co najwyżej jedną spośród liczb \(\displaystyle{ \NWD(x+1, y-1), \ \NWD(x-1, y+1)}\)
Niech więc \(\displaystyle{ p>2}\) dzieli \(\displaystyle{ x+1}\) z wykładnikiem \(\displaystyle{ i\in \NN^{+}}\) oraz \(\displaystyle{ y-1}\) z wykładnikiem \(\displaystyle{ j\in \NN^{+}}\), wówczas \(\displaystyle{ v_{p}\left(\NWD(x+1, y-1)\right)=\min\left\{i, j\right\}, \ v_{p}\left( \text{NWW}\left(\NWD(x+1, y-1), \ \NWD(x-1, y+1)\right)\right)=\min\left\{i,j\right\}}\) i ponieważ \(\displaystyle{ x^{y}+y^{x}=x^{y}+1^{y}+y^{x}-1^{x}=(x+1)\sum_{k=0}^{y-1}(-1)^{k}x^{y-1-k}+(y-1)\sum_{k=0}^{x-1}y^{k}}\)
więc \(\displaystyle{ p^{\min\left\{i,j\right\}}|x^{y}+y^{x}}\), wszak oczywiście \(\displaystyle{ p^{\min\left\{i,j\right\}}|(x+1), \ p^{\min\left\{i,j\right\}}|(y-1)}\)
W pełni analogicznie postępujemy dla \(\displaystyle{ p>3}\) dzielącej \(\displaystyle{ \NWD(x-1, y+1)}\), tylko wtedy korzystamy z równości \(\displaystyle{ x^{y}+y^{x}=x^{y}-1^{y}+y^{x}+1^{x}}\)
Pozostaje kwestia \(\displaystyle{ p=2}\), które dzieli każdą z liczb \(\displaystyle{ x-1, \ x+1, \ y-1, \ y+1}\).
Zauważmy, że liczby \(\displaystyle{ x-1, \ x+1}\) dają różne reszty z dzielenia przez \(\displaystyle{ 4}\) i podobnie rzecz się ma z liczbami \(\displaystyle{ y-1, \ y+1}\). Zatem \(\displaystyle{ p=2}\) wchodzi do rozkładu na czynniki pierwsze co najmniej jednej z liczb \(\displaystyle{ \NWD(x+1, y-1), \ \NWD(x-1, y+1)}\) z wykładnikiem równym \(\displaystyle{ 1}\)
a oczywiście \(\displaystyle{ 2}\) wchodzi do rozkładu na czynniki pierwsze \(\displaystyle{ \text{NWW}\left(\NWD(x+1, y-1), \ \NWD(x-1, y+1)\right)}\)
z wykładnikiem równym \(\displaystyle{ \max\left\{v_{2}(\NWD(x+1, y-1)), \ v_{2} (\NWD(x-1, y+1)\right\}}\)
Czyli również wówczas wzorki załatwiają robotę w analogiczny sposób, dzięki temu, że \(\displaystyle{ \NWD(a,b)|a, \ \NWD(a,b)|b}\)
Proszę udowodnić, że dla każdej liczby całkowitej dodatniej \(\displaystyle{ n}\) istnieją parami względnie pierwsze liczby całkowite \(\displaystyle{ k_{0}, k_{1}\ldots k_{n}}\), wszystkie większe niż \(\displaystyle{ 1}\), dla których \(\displaystyle{ k_{0}k_{1}\ldots k_{n}-1}\) jest iloczynem dwóch kolejnych liczb całkowitych.
Lemat
Istnieje nieskończenie wiele liczb pierwszych \(\displaystyle{ p}\), dla którch kongruencja \(\displaystyle{ x^2 + x + 1 \equiv_{p} 0}\) ma rozwiązanie. Dowód
Niech \(\displaystyle{ p}\) takie że \(\displaystyle{ 3 \mid p-1}\) oraz \(\displaystyle{ g}\) - generator modulo \(\displaystyle{ p}\). Zauważmy, że \(\displaystyle{ x = g^{\frac{p-1}{3}}}\) spełnia warunki, gdyż \(\displaystyle{ x^2 + x + 1 = \frac{x^3 - 1}{x-1} = \frac{ (g^{\frac{p-1}{3}})^3 - 1}{g^{\frac{p-1}{3}} - 1} = \frac{g^{p-1}-1}{g^{\frac{p-1}{3}} - 1} \equiv 0 \pmod{p}}\)
Mianownik nie jest zerem dlatego, że \(\displaystyle{ 1 \le \frac{p-1}{3} < p-1}\), a \(\displaystyle{ g}\) jest generatorem. To kończy dowód lematu.
Weźmy teraz parami różne liczby pierwsze \(\displaystyle{ p_0, ..., p_n}\) takie że istnieje rozwiązanie kongruencji \(\displaystyle{ x^2 + x + 1 \equiv_{p_i} 0}\) i oznaczmy je przez \(\displaystyle{ x_i}\) (dla \(\displaystyle{ i=0,1,...,n}\)). Rozważmy układ równań:
\begin{cases} X \equiv_{p_0} x_0 \\ X \equiv_{p_1} x_1 \\ ... \\ X \equiv_{p_n} x_n \end{cases}
Na mocy chińskiego twierdzenia o resztach ma on rozwiązanie. Oznacza to, że istnieje \(\displaystyle{ X}\), dla którego \(\displaystyle{ p_i \mid X^2 + X + 1}\) (dla \(\displaystyle{ i=0,1,...,n}\)). Czyli \(\displaystyle{ p_0 p_1 ... p_n \mid X^2 + X + 1}\). W konsekwencji \(\displaystyle{ X^2 + X + 1 = k p_0 p_1 ... p_n}\), więc \(\displaystyle{ X(X+1) = k p_0 p_1 ... p_n - 1}\). Liczba \(\displaystyle{ k p_0 p_1 ... p_n}\) ma w swoim rozkładzie na czynniki pierwsze co najmniej \(\displaystyle{ n+1}\) parami różnych liczb pierwszych. W konsekwencji, można ją rozłożyć na iloczyn parami względnie pierwszych liczb całkowitych \(\displaystyle{ k_0, ..., k_n}\) wszystkich większych od 1. To kończy dowód.
Niech \(\displaystyle{ A}\) i \(\displaystyle{ B}\) będą trójkami pitagorejskimi. Udowodnić, że istnieje ciąg trójek pitagorejskich zaczynający się od \(\displaystyle{ A}\) i kończący na \(\displaystyle{ B}\), że każde dwie kolejne trójki pitagorejskie mają przynajmniej jeden element wspólny.