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.
Przepraszam, wrzuciłbym już w nocy, ale już mi się nie chciało I faktycznie nie jest prawdziwe dla \(\displaystyle{ t=1}\).
Może coś takiego:
Dowieść, że równanie \(\displaystyle{ 3^x+2=5^y}\) nie ma rozwiązań w liczbach naturalnych \(\displaystyle{ x,y}\), gdy \(\displaystyle{ x>1}\).
To zdanie jest świetne! Jutro z rana wklepię solva jak mnie nikt nie uprzedzi, na razie jedynie
Ukryta treść:
Dla dodatnich \(\displaystyle{ n}\): \(\displaystyle{ a_{n}=3^{F_{n}}\cdot 2^{F_{n-1}+1}-2}\)
Nietrudno indukcją pokazać, że to prawda. Jak ktoś jest zainteresowany jak otrzymać taki no cóż... mocno nieoczywisty wzór, to pisać.
Zauważmy, że \(\displaystyle{ a_{0}-1=1}\), więc nie ma dzielników pierwszych. Mamy szukać dzielników pierwszych liczb postaci \(\displaystyle{ 3^{F_{n}}\cdot 2^{F_{n-1}+1}-2-1=3\cdot\left(3^{F_{n}-1}\cdot 2^{F_{n-1}+1}-1 \right)}\)
Jak widać, do zbioru szukanych liczb pierwszych nie należy \(\displaystyle{ 2}\), zaś należy z całą pewnością \(\displaystyle{ 3}\). Niech \(\displaystyle{ p \ge 5}\). Znanym faktem jest, że dla każdego \(\displaystyle{ k}\) istnieje takie \(\displaystyle{ m}\), że \(\displaystyle{ k\mid F_{m}}\). Tego się dowodzi jakoś zasadą szufladkową, pojawiało się to parę razy na forum, jak będzie trzeba to dowiodę. Niech więc \(\displaystyle{ k=p-1}\) i niech \(\displaystyle{ m}\) będzie taką liczbą, że \(\displaystyle{ k \mid F_{m}}\). Znanym faktem jest, że \(\displaystyle{ F_{m} \mid F_{lm}}\). Wtedy dla każdego dodatniego \(\displaystyle{ l}\) mamy \(\displaystyle{ F_{lm} \equiv 0 \pmod{k}}\). Niech \(\displaystyle{ F_{m+1} \equiv r \pmod{k}}\). Zauważmy, że gdy \(\displaystyle{ d=\left(r, \ k\right)}\), to \(\displaystyle{ d=1}\). W przeciwnym razie \(\displaystyle{ d \mid k \mid F_{m+1}-r \wedge d \mid r \Rightarrow d \mid F_{m+1}}\) i \(\displaystyle{ d \mid k \mid F_{m}}\) i mamy \(\displaystyle{ \left(F_{m}, \ F_{m+1}\right) \ge d >1}\), a znanym faktem jest, że nie może to być prawdą. Zauważmy, że \(\displaystyle{ F_{m+2} = F_{m+1}+F_{m} \equiv r+0 \equiv r \pmod{k}}\). Dalej \(\displaystyle{ F_{m+3} = F_{m+2}+F_{m+1}\equiv r+r\equiv 2r \pmod{k}}\), a to nam już dalej łatwo implikuje, że \(\displaystyle{ F_{m+i} \equiv F_{i} \cdot r \pmod{k}}\). W szczególności \(\displaystyle{ F_{2m+1} \equiv F_{m+1} \cdot r \equiv r^{2}}\). Powtarzając to rozumowanie uzyskujemy, że \(\displaystyle{ F_{2m+i}\equiv F_{i} \cdot r^{2} \pmod{k}}\), a w szczególności \(\displaystyle{ F_{3m+1} \equiv r^{3} \pmod{k}}\). To dalej indukuje nam, że \(\displaystyle{ F_{lm+i} \equiv F_{i} \cdot r^{l}}\), a w szczególności \(\displaystyle{ F_{lm+1} \equiv r^{l} \pmod{k}}\). Dla \(\displaystyle{ l=\lambda\left( k\right)}\), gdzie \(\displaystyle{ \lambda}\) jest funkcją Carmichaela mamy \(\displaystyle{ F_{ml+1}=F_{m\lambda \left( k\right) +1} \equiv r^{\lambda\left(k\right)} \equiv 1 \pmod{k}}\), co wynika z określenia funkcji Carmichaela. Wtedy \(\displaystyle{ F_{lm-1}=F_{lm+1}-F_{lm}\equiv 1-0 \pmod{k}}\) i dalej \(\displaystyle{ F_{lm-2}=F_{lm}-F_{lm-1} \equiv 0 -1 \equiv -1 \pmod{k}}\).
Dla każdej liczby pierwszej \(\displaystyle{ p \ge 5}\) wystarczy położyć \(\displaystyle{ n=m\lambda\left(p-1\right)-1}\), gdzie \(\displaystyle{ m}\) to taka liczba, że \(\displaystyle{ p-1 \mid F_{m}}\), mamy bowiem \(\displaystyle{ F_{n} \equiv 1 \pmod{p-1} \Leftrightarrow p-1\mid F_{n}-1}\) oraz \(\displaystyle{ F_{n-1} \equiv -1 \pmod{p-1} \Leftrightarrow p-1\mid F_{n-1}+1}\). Ostatecznie \(\displaystyle{ 3\cdot\left(3^{F_{n}-1}\cdot 2^{F_{n-1}+1}-1 \right) = 3\cdot\left(\left( 3^{x}\right)^{p-1}\cdot \left( 2^y\right)^{p-1}-1 \right)\equiv 3\cdot\left(1 \cdot 1-1 \right) \equiv 0 \pmod{p}}\) co wynika z małego twierdzenia Fermata. Zatem szukanym zbiorem jest zbiór nieparzystych liczb pierwszych.
Mając już do pokazania \(\displaystyle{ 2^{F_{n-1}+1}\cdot 3^{F_n-1} \equiv 1\pmod{p}}\), z mtfa wystarczy znaleźć takie \(\displaystyle{ t}\), że \(\displaystyle{ p-1 \mid F_{t-1}+1 \wedge p-1 \mid F_{t}-1}\)
Czyli patrząc na pary \(\displaystyle{ (F_k,F_{k+1})}\) modulo \(\displaystyle{ p-1}\) chcemy dostać parę \(\displaystyle{ (-1,1)}\), ale rozszerzając ciąg \(\displaystyle{ F_n}\) o parę wyrazów ujemnych dostajemy \(\displaystyle{ -1,1,0,1,1,2,3,...}\), skąd istnieje para \(\displaystyle{ (-1,1)}\), a ponieważ pary \(\displaystyle{ (F_k,F_{k+1}) \pmod{p-1}}\) w końcu nam się zapętlą (znany fakt, liczba różnych par jest skończona i każda para zależy tylko od poprzedniej pary), dostajemy, że istnieje (nawet nieskończenie wiele) taka dodatnia liczba \(\displaystyle{ t}\), że \(\displaystyle{ (F_t,F_{t+1}) = (-1,1)}\), cnd.
Sprowadzamy do postaci \(\displaystyle{ n^n(n^{n^3-n}-1)}\). Jako, że \(\displaystyle{ n^3-n=(n-1)n(n+1)}\), to z MTF otrzymujemy, że aby nasza liczba nie była podzielna przez \(\displaystyle{ 5}\), musi zachodzić \(\displaystyle{ n=4k+2}\). Bawiąc się trochę z przypadkami modulo 5, wychodzi że nie dzieli się przez 5 dla k dających w dzieleniu przez 5 resztę inną niż 1.
Jak dobrze, to coś wrzucę.
A, Ponewor, jakbyś mógł, to napisz, jak doszedłeś do tego wyrazu ogólnego
Dla \(\displaystyle{ n=10}\) lub \(\displaystyle{ 14}\) podzielność zachodzi.
Rozwiązanie rekurencji:
Mamy rekurencję \(\displaystyle{ \begin{cases} x_{0}=a \\ x_{1}=b \\ x_{n+1}=\frac{x_{n}x_{n-1}}{2}+x_{n}+x_{n-1} \text{ dla dodatnich } n\end{cases}}\)
Otóż należy zaobserwować, że \(\displaystyle{ x_{n+1}=\frac{1}{2}\left(x_{n}+2\right)\left(x_{n-1}+2\right)-2}\)
i tak o to \(\displaystyle{ x_{2}=\frac{1}{2}\left(a+2\right)\left(b+2\right)-2 \\
x_{3}=\frac{1}{2}\left(\frac{1}{2}\left(a+2\right)\left(b+2\right)-2+2\right)\left(a+2\right)-2=\left(\frac{1}{2}\right)^{2}\left(a+2\right)^{2}\left(b+2\right)-2 \\
x_{4}=\frac{1}{2}\left(\left(\frac{1}{2}\right)^{2}\left(a+2\right)^{2}\left(b+2\right)-2+2\right)\left(\frac{1}{2}\left(a+2\right)\left(b+2\right)-2+2\right)-2=\left(\frac{1}{2}\right)^{4}\left(a+2\right)^{3}\left(b+2\right)^{2}-2}\)
Nietrudno spostrzec, że wykładniki przy \(\displaystyle{ \left(a+2\right)}\) i \(\displaystyle{ \left(b+2\right)}\) zachowują się zupełnie jak kolejne wyrazy ciągu Fibonacciego, tzn. każdy z nich jest sumą dwóch poprzednich. Techniczną robotą jest ustalić szczegóły. Trochę inaczej jest z wykładnikiem przy \(\displaystyle{ \frac{1}{2}}\) - ten jest sumą dwóch poprzednich zwiększoną o jeden. Są dwa wyjścia z tej sytuacji - albo wypisać kilka początkowych wyrazów ciągu \(\displaystyle{ y_{n+1}=y_{n}+y_{n-1}+1}\) i zauważyć, że są to kolejne wyrazy ciągu Fibonacciego zmniejszone o jeden, albo wykorzystać funkcje tworzące (należy sparafrazować wyprowadzenie wzoru Bineta z ich użyciem).
Ostatecznie otrzymujemy \(\displaystyle{ x_{n}=\left( \frac{1}{2}\right)^{F_{n+1}-1}\cdot\left(a+2 \right)^{F_{n}}\cdot\left(b+2 \right)^{F_{n-1}}-2}\)
Gdy wstawimy \(\displaystyle{ a=4 \wedge b=2}\):
Vax pisze:Masz źle, \(\displaystyle{ \pmod{5}}\) nasze \(\displaystyle{ n}\) musi być równe \(\displaystyle{ 2 \vee 3}\), bo jeżeli byłoby równe \(\displaystyle{ 4 \equiv -1\pmod{5}}\), to \(\displaystyle{ 5 \mid n^{n^3-n}-1}\), ostateczny wynik powinien wyjść \(\displaystyle{ n \equiv \pm 2\pmod{20}}\)
I kazał wrzucić kolejne zadanie. Może takie:
Z ciągu wszystkich kolejnych liczb naturalnych usunięto wszystkie kwadraty liczb całkowitych. Dowieść, że otrzymany w ten sposób ciąg wyraża się wzorem \(\displaystyle{ u_n=n+\left[ \sqrt{n+\left[ n\right] } \right]}\).
PS. Dzięki Ponewor
Tam powinno być chyba \(\displaystyle{ u_n = n+\left[\sqrt{n+\left[\sqrt{n}\right]}\right]}\)
Ukryta treść:
Popatrzmy co się dzieje dla \(\displaystyle{ n=k^2}\), wówczas \(\displaystyle{ u_n = k^2+\left[\sqrt{k^2+k}\right] = k^2+k}\) (gdyż \(\displaystyle{ k < \sqrt{k^2+k} < k+1}\))
Podstawmy \(\displaystyle{ n = k^2+r}\), gdzie \(\displaystyle{ 1 \le r \le k}\), wówczas:
Niech \(\displaystyle{ a,b \in \mathbb{Z}_+}\). Pokazać, że jeżeli \(\displaystyle{ a^3+b^3}\) jest kwadratem liczby całkowitej, to \(\displaystyle{ a+b}\) nie może być iloczynem dwóch różnych liczb pierwszych.
Wbrew tezie załóżmy, że \(\displaystyle{ a+b=pq}\), gdzie \(\displaystyle{ p,q}\) są liczbami pierwszymi. Skoro \(\displaystyle{ a^3+b^3}\) jest kwadratem, to \(\displaystyle{ a^2-ab+b^2}\) musi być podzielne przez \(\displaystyle{ pq}\). Mamy także \(\displaystyle{ a \equiv -b \pmod{p}}\) i \(\displaystyle{ a \equiv -b \pmod{q}}\). Z tego, że \(\displaystyle{ a^2-ab+b^2 \equiv 0 \pmod{p}}\) otrzymujemy \(\displaystyle{ 3a^2 \equiv 3b^2 \equiv 0 \pmod{p}}\). Analogicznie \(\displaystyle{ 3a^2 \equiv 3b^2 \equiv 0 \pmod{q}}\). Stąd mamy dwie możliwości:
1) \(\displaystyle{ a}\) i \(\displaystyle{ b}\) są podzielne zarówno przez \(\displaystyle{ p}\) jak i przez \(\displaystyle{ q}\). Stąd \(\displaystyle{ a=kpq \wedge b=lpq}\) dla pewnych całkowitych \(\displaystyle{ k,l \ge 1}\). Zatem \(\displaystyle{ a+b=(k+l)pq=pq}\), sprzeczność, gdyż \(\displaystyle{ k+l>1}\).
2) Jedna z liczb \(\displaystyle{ p,q}\) (niech to będzie \(\displaystyle{ p}\)) jest równa \(\displaystyle{ 3}\), a druga dzieli \(\displaystyle{ a}\) i \(\displaystyle{ b}\). Wtedy dostajemy łatwo, że \(\displaystyle{ 3q=(k+l)q}\), ale to jest również sprzeczność, gdyż wtedy \(\displaystyle{ a^3+b^3=9q^3}\), co kwadratem na pewno nie jest.
To może takie:
Dowieść, że dla każdej liczby pierwszej \(\displaystyle{ p}\) istnieje nieskończenie wiele liczb pierwszych \(\displaystyle{ q}\) takich, że \(\displaystyle{ p \mid q-1}\)
