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.
szkic Niech \(\displaystyle{ a_n=f(n)}\), W ciagu \(\displaystyle{ 1,...,f(n)}\) mamy liczby \(\displaystyle{ f(1),
...,f(n)}\), tj te które nie są kwadratami oraz liczby \(\displaystyle{ 1^2, 2^2, ...,k^2}\)
Musi być \(\displaystyle{ f(n)=n+k}\) (z def \(\displaystyle{ f}\)) i \(\displaystyle{ k^2 < f(n)<(k+1)^2}\)
łatwo uzyskac \(\displaystyle{ k < \sqrt{n} + \frac{1}{2} <k+1}\) tj teze
Całkowite są liczby \(\displaystyle{ \frac{a^2c + b^2a + c^2b}{abc}}\) i \(\displaystyle{ \frac{a^2b + b^2c + c^2a}{abc}}\), czyli \(\displaystyle{ abc|a^2c + b^2a + c^2b, \ a^2b + b^2c + c^2a}\). Niech \(\displaystyle{ d=(a,b,c)}\). Dla pewnych całkowitych \(\displaystyle{ p, \ q, \ r}\), \(\displaystyle{ a=pd, \ b=qd, \ c=rd}\), przy czym \(\displaystyle{ (p,q,r)=1}\). Z założeń o podzielności po podzieleniu stronami przez \(\displaystyle{ d^3}\) mamy \(\displaystyle{ pqr|p^2r+q^2p+r^2q, \ p^2q+q^2r+r^2p}\). Tak naprawdę dowiedliśmy dotychczas, że możemy b.s.o założyć \(\displaystyle{ (a,b,c)=1}\).
Przypuśćmy teraz wbrew tezie, że któraś z tych liczb ma różny od 1 moduł, czyli b.s.o. istnieje liczba pierwsza \(\displaystyle{ s}\) dzieląca \(\displaystyle{ p}\). Wtedy z pierwszej z podzielności mamy \(\displaystyle{ s|r^2q}\), więc b.s.o. \(\displaystyle{ s|q}\). Weźmy \(\displaystyle{ k, \ l}\) takie, że \(\displaystyle{ s^k||p}\) i \(\displaystyle{ s^l||q}\) (\(\displaystyle{ k,l \geq 1}\)), załóżmy też b.s.o., że \(\displaystyle{ k \geq l}\). Z pierwszej podzielności mamy \(\displaystyle{ s^{k+l}|r^2q}\) (pozostałe człony wobec założenia na pewno są podzielne), co daje \(\displaystyle{ s|r}\). Otrzymaliśmy sprzeczność z założeniem \(\displaystyle{ (p,q,r)=1}\).
Zadanie 31:
Niech \(\displaystyle{ k=2+2\sqrt{28n^2+1}}\), \(\displaystyle{ k \in \mathbb{Z}}\). Przez proste przekształcenia otrzymujemy \(\displaystyle{ k(k-4)=16 \cdot 7n^2}\). Oczywiście liczba \(\displaystyle{ k}\) musi być podzielna przez 4, więc podstawiamy \(\displaystyle{ k=4a}\), otrzymując po podzieleniu stronami przez 16: \(\displaystyle{ a(a-1)=7n^2}\). Liczby \(\displaystyle{ a}\) i \(\displaystyle{ a-1}\) jako kolejne liczby naturalne są względnie pierwsze, więc zachodzi jeden z dwóch przypadków (ze względu na to, która z nich jest podzielna przez 7):
1. \(\displaystyle{ 7|a}\) oraz \(\displaystyle{ a-1}\) jest kwadratem; z pierwszego \(\displaystyle{ a \equiv 6 \ (\hbox{mod 7})}\), co jest sprzeczne z drugim
2. \(\displaystyle{ 7|a-1}\) oraz \(\displaystyle{ a}\) jest kwadratem
Jak widać, zachodzi drugi przypadek, co w szczególności dowodzi, że \(\displaystyle{ k=4a}\) jest kwadratem. Spróbujmy teraz znaleźć takie \(\displaystyle{ n}\). W gruncie rzeczy chodzi o znalezienie takiego \(\displaystyle{ a}\), że \(\displaystyle{ 7|a-1}\), przy czym \(\displaystyle{ a}\) i \(\displaystyle{ \frac{a-1}{7}}\) to kwadraty. Innymi słowy, podstawiając \(\displaystyle{ p^2=a}\) i \(\displaystyle{ q^2=\frac{a-1}{7}}\), o rozwiązanie równania \(\displaystyle{ p^2-7q^2=1}\). Skądinąd (równanie Pella) umiemy znaleźć rozwiązania (jest ich nieskończenie wiele); ograniczę się do podania \(\displaystyle{ (8,3)}\) i \(\displaystyle{ (127,48)}\). Otrzymujemy stąd \(\displaystyle{ n=24}\) i \(\displaystyle{ n=6096}\) (oczywiście mogę podawać dalsze, ale nie będzie to bardzo ciekawe).
Zadanie 39:
Interesują nas nieparzyste reszty kwadratowe modulo \(\displaystyle{ 2^n}\). Na początek sprawdźmy, że dla nieparzystego \(\displaystyle{ x}\), \(\displaystyle{ x^2 \equiv 1 \ (\hbox{mod 8})}\). Dowodzi to implikacji w jedną stronę.
Najpierw pokażę indukcyjnie, że każda taka reszta jest przyjmowana dokładnie 4 razy. Dla \(\displaystyle{ n=3}\) właśnie to sprawdziliśmy. Załóżmy, że zachodzi dla \(\displaystyle{ n}\). Dla nieparzystego \(\displaystyle{ x}\) wszystkimi liczbami o kwadracie przystającym do \(\displaystyle{ x^2}\) modulo \(\displaystyle{ 2^n}\) są \(\displaystyle{ x, \ 2^n-x, \ 2^{n-1}-x, \ 2^{n-1}+x}\) (można sprawdzić, że tak jest i ponadto, że są to liczby parami nieprzystające). Przejdźmy do tezy indukcyjnej. Jeśli \(\displaystyle{ y^2 \equiv x^2 \ (\hbox{mod 2^{n+1}})}\), to w szczególności \(\displaystyle{ y^2 \equiv x^2 \ (\hbox{mod 2^{n}})}\), więc \(\displaystyle{ y}\) przystaje do którejś z tamtych czterech liczb modulo \(\displaystyle{ 2^n}\). Jest zatem jedną z tych czterech lub jest większa o \(\displaystyle{ 2^n}\) od którejś z nich. Można jednak sprawdzić, że z ośmiu liczb \(\displaystyle{ x, \ 2^n-x, \ 2^{n-1}-x, \ 2^{n-1}+x, \ 2^n + x, \ 2^{n+1}-x, \ 2^n+2^{n-1}-x, \ 2^n+2^{n-1}+x}\) tylko cztery spełniają \(\displaystyle{ y^2 \equiv x^2 \ (\hbox{mod 2^{n+1}})}\); są to \(\displaystyle{ x, \ 2^{n+1}-x, \ 2^n-x, \ 2^n+x}\). Dowiedliśmy więc tezy indukcyjnej.
Każdy kwadrat liczby nieparzystej daje resztę 1 modulo 8 i każda nieparzysta reszta kwadratowa jest przyjmowana dokładnie 4 razy. Ponieważ liczb nieparzystych jest dokładnie 4 razy więcej od liczb dających resztę 1 modulo 8, więc każda z tych ostatnich jest resztą kwadratową, co należało wykazać.
Modulo \(\displaystyle{ 2^5}\), czyli 32, do 1 przystają kwadraty liczb 1, 15, 17, 31.
Zadanie 22:
Jest jasne, że \(\displaystyle{ a_{n+1} \geq a_n+1}\). Zobaczmy, co się dzieje, gdy \(\displaystyle{ a_{n+1} > a_n+1}\), czyli gdy ciąg \(\displaystyle{ a_n}\) coś przeskakuje. Wówczas \(\displaystyle{ \left[\sqrt{n}+\frac{1}{2}\right]<\left[\sqrt{n+1}+\frac{1}{2}\right]}\), istnieje zatem liczba naturalna \(\displaystyle{ k}\) taka, że \(\displaystyle{ \sqrt{n}+\frac{1}{2} < k \leq \sqrt{n+1}+\frac{1}{2}}\). Po przekształceniach mamy stąd \(\displaystyle{ n < k^2-k+\frac{1}{4} \leq n+1}\), więc oczywiście \(\displaystyle{ n=k^2-k}\). Łatwo sprawdzić, że wówczas \(\displaystyle{ \left[\sqrt{n}+\frac{1}{2}\right]=k-1}\), \(\displaystyle{ \left[\sqrt{n+1}+\frac{1}{2}\right]=k}\), zatem \(\displaystyle{ a_n=k^2-1}\) i \(\displaystyle{ a_{n+1}=k^2+1}\). Zgodnie z oczekiwaniami, ciąg \(\displaystyle{ a_n}\) omija dokładnie kwadraty.
Nie zauważyłem wcześniej, że 22. już było wrzucone.
Zadanie 18:
Skoro \(\displaystyle{ q|A}\), to \(\displaystyle{ q|A(a-1)=a^p-1}\). Z MTF \(\displaystyle{ q|a^{q-1}-1}\). Zgodnie ze znanym lematem \(\displaystyle{ p}\) musi być rzędem \(\displaystyle{ a}\) modulo \(\displaystyle{ q}\) (bo \(\displaystyle{ p}\) jest pierwsze)*, a więc \(\displaystyle{ p|q-1}\).
* Rzędem może być jeszcze 1, co oznaczałoby \(\displaystyle{ a=1}\). Wtedy \(\displaystyle{ A=p}\), więc \(\displaystyle{ q=p}\). Teza wydaje się nie zachodzić, co nasuwa przypuszczenia, że brakuje jakiegoś założenia.
PS: czekoladowy - jakoś nie podoba mi się twoje przejście do układu równań; czy pod tym kryje się coś, czego nie widzę?
Dowód indukcyjny. Daruję sobie pierwszą fazę, łatwo sprawdzić, co trzeba. Załóżmy, że mamy rozwinięcie Cantora dla wszystkich \(\displaystyle{ n < m!}\). Weźmy więc \(\displaystyle{ m! \leq n < (m+1)!}\), podzielmy z resztą: \(\displaystyle{ n = a \cdot m! + b}\). Mamy \(\displaystyle{ b<m!}\), więc \(\displaystyle{ b}\) ma rozwinięcie Cantora i to rozwinięcie oczywiście ma współczynnik 0 przy \(\displaystyle{ m!}\). Z kolei z \(\displaystyle{ n<(m+1)!}\) wynika \(\displaystyle{ a \leq m}\), więc przez dodanie współczynnika \(\displaystyle{ a}\) do rozwinięcia \(\displaystyle{ b}\) mamy rozwinięcie dla \(\displaystyle{ n}\).
Dla ustalonego \(\displaystyle{ m}\) rozwinięć \(\displaystyle{ \sum_{k=1}^m a_k \cdot k!}\) jest dokładnie \(\displaystyle{ 1 \cdot 2 \cdot \ldots \cdot (m+1) = (m+1)!}\) (współczynnik \(\displaystyle{ a_k}\) wybieramy na \(\displaystyle{ k+1}\) sposobów, bo \(\displaystyle{ 0 \leq a_k \leq k}\)). Ponadto, jak się okazuje, można otrzymać co najwyżej \(\displaystyle{ (m+1)!}\) sum, bo \(\displaystyle{ 0 \leq \sum_{k=1}^m a_k \cdot k! \leq \sum_{k=1}^m k \cdot k! = \sum_{k=1}^m \left( (k+1)! - k! \right) = (m+1)! - 1}\). Pokazaliśmy, że każdą z nich da się otrzymać, a więc każdą na dokładnie jeden sposób.
Zadanie 68:
Weźmy zbiór \(\displaystyle{ A}\) spełniający te warunki. Niech \(\displaystyle{ M=\hbox{max}A}\), \(\displaystyle{ m=\hbox{min}A}\). Jeśli \(\displaystyle{ k \in A}\) i \(\displaystyle{ k<M}\), to \(\displaystyle{ \frac{k^2}{M-k} \in A}\), więc \(\displaystyle{ \frac{k^2}{M-k} \leq M}\). Wymnażamy przez mianownik i mamy nierówność kwadratową. Łatwo sprawdzić, że równość nie zachodzi (równanie kwadratowe ma niewymierne pierwiastki). Z nierówności tej mamy \(\displaystyle{ k \leq \frac{\sqrt{5}-1}{2} \cdot M}\). W ten sposób możemy tworzyć kolejne ograniczenia \(\displaystyle{ k \leq a_n \cdot M}\), poczynając od \(\displaystyle{ a_1=1}\). Z nierówności \(\displaystyle{ \frac{k^2}{M-k} \leq a_n \cdot M}\) otrzymujemy ograniczenie \(\displaystyle{ k \leq a_{n+1} \cdot M}\), gdzie \(\displaystyle{ a_{n+1} = \frac{\sqrt{a_n(a_n+4)}-a_n}{2}}\). Łatwo sprawdzić, że jeśli \(\displaystyle{ a_n \geq \frac{1}{2}}\), to \(\displaystyle{ a_{n+1} \leq a_n}\). Dlatego zachodzi jeden z dwóch przypadków:
1. \(\displaystyle{ a_n < \frac{1}{2}}\) dla pewnego \(\displaystyle{ n}\), czyli w szczególności mamy ograniczenie \(\displaystyle{ k \leq \frac{1}{2}M}\).
2. Jest przeciwnie - wtedy \(\displaystyle{ (a_n)}\) jest ograniczony z dołu przez \(\displaystyle{ \frac{1}{2}}\) i nierosnący, więc ma granicę \(\displaystyle{ g}\). Ze wzoru rekurencyjnego: \(\displaystyle{ g = \lim_{n \to \infty} a_n = \lim_{n \to \infty} a_{n+1} = \frac{\sqrt{g(g+4)}-g}{2}}\),
skąd \(\displaystyle{ g=\frac{1}{2}}\). Mamy więc ograniczenia dowolnie bliskie \(\displaystyle{ \frac{1}{2}}\), a więc także \(\displaystyle{ k \leq \frac{1}{2}M}\).
Z innej beczki: \(\displaystyle{ \frac{m^2}{M-m} \in A}\), więc \(\displaystyle{ \frac{m^2}{M-m} \geq m}\), skąd \(\displaystyle{ m \geq \frac{1}{2}M}\). W połączeniu z poprzednim oszacowaniem oznacza to, że \(\displaystyle{ A= \{ m, 2m \}}\). Łatwo sprawdzić, że każdy taki zbiór (\(\displaystyle{ m}\) całkowite dodatnie) spełnia warunki zadania.
\(\displaystyle{ \frac{b+c}{a}+\frac{c+a}{b}+\frac{a+b}{c}=0 \Leftrightarrow (b+c)bc+(c+a)ca+(a+b)ab=0 \Leftrightarrow b^2c+bc^2+c^2a+ca^2+a^2b+ab^2=0 \Leftrightarrow a^2(b+c)+b^2(c+a)+c^2(a+b)=0 \Leftrightarrow}\) \(\displaystyle{ \begin{cases} a+b=0 \\ b+c=0 \\ c+a=0 \end{cases} \Rightarrow \begin{cases} a=-b \\ c=-b \\ c=-a \end{cases} \Rightarrow \begin{cases} a=c \\ c=-a \end{cases}}\)
I to jest sprzeczność, przypadek równy zero pominąłem bo dzielimy przez wszystkie liczby więc 0 być nie mogą
robin5hood masz racje w tym przejściu popełniłem ten sam błąd co czekoladowy (nieświadomie założyłem że a,b,c należą do N) i dopiero potem zakładałem że należą do C. Co oznacza że mój dowód jest tyle samo wart co poprzedni