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 udowodnimy, że \(\displaystyle{ |f(x)-f(y)|=|x-y|}\)
Przypuśćmy nie wprost, że dla pewnych \(\displaystyle{ 0\le y_{0}<x_{0}\le 1}\) zachodzi ostra nierówność \(\displaystyle{ |f(x_{0})-f(y_{0})|<|x_{0}-y_{0}|}\)
Z warunku \(\displaystyle{ (x-y)^{2}<|f(x)-f(y)|,}\) nierówności trójkąta i warunku \(\displaystyle{ |f(x)-f(y)|\le |x-y|}\), przy czym dla \(\displaystyle{ x_{0}, \ y_{0}}\) zachodzi nierówność ostra, dostajemy: \(\displaystyle{ 1=(1-0)^{2}\le |f(1)-f(0)|=|(f(1)-f(x_{0}))+(f(x_{0})-f(y_{0}))+(f(y_{0})-f(0))|\\ \le |f(1)-f(x_{0})|+|f(x_{0})-f(y_{0})|+|f(y_{0})-f(0)|\\<|1-x_{0}|+|x_{0}-y_{0}|+|y_{0}-0|\\=1-x_{0}+x_{0}-y_{0}+y_{0}-0=1}\)
a to jest sprzeczność.
Zatem \(\displaystyle{ |f(x)-f(y)|=|x-y|}\), wstawiamy w tej równości \(\displaystyle{ y=0}\) i mamy \(\displaystyle{ |f(x)-f(0)|=|x|}\) dla każdego \(\displaystyle{ x\in [0,1]}\), czyli dla \(\displaystyle{ x\in [0,1]}\) jest \(\displaystyle{ f(x)=x+f(0)\vee f(x)=-x+f(0)}\)
Teraz przypuśćmy nie wprost, że istnieją takie \(\displaystyle{ 0< y_{0}<x_{0}\le 1}\), że \(\displaystyle{ f(y_{0})=-y_{0}+f(0), \ f(x_{0})=x_{0}+f(0)}\).
Wówczas mamy \(\displaystyle{ |f(x_{0})-f(y_{0}|=x_{0}+y_{0}>x_{0}-y_{0}=|x_{0}-y_{0}|}\)
a to jest oczywista sprzeczność. W pełni analogicznie dla \(\displaystyle{ f(y_{0})=y_{0}+f(0), \ f(x_{0})=-x_{0}+f(0)}\) Podsumowanie: warunki zadania spełniają funkcje postaci \(\displaystyle{ f(x)=x+C}\) oraz \(\displaystyle{ f(x)=-x+C}\),gdzie \(\displaystyle{ C\in \RR}\) to dowolna stała. Powyżej wykazałem, że żadne inne nie mogą czynić zadość warunkom, proste sprawdzenie przez podstawienie i nierówność \(\displaystyle{ t^{2}\le t, \ t\in [0,1]}\) pokazuje, że istotnie są one rozwiązaniami zadania.
Z warunku Lipschitza wynika, że `f` jest ciągła, a lewa strona implikuje, że jest różnowartościowa.
Załóżmy, zatem, że jest rosnąca (jak nie, to `-f` też spełnia warunki zadania).
Jeżeli `f` spełnia warunki, to `f+c` też, więc załóżmy, że `f(0)=0` (bo funkcja ciągła osiąga kresy)
Teraz już prosto: \(\displaystyle{ (0-1)^2=1\leq f(1)-f(0)=f(1)\leq |0-1|=1}\), więc `f(1)=1`. Ponadto `f(x)-f(0)=f(x)\leq x-0=x`.
Z drugiej strony `1-f(x)=f(1)-f(x)\le 1-x` implikuje `x\le f(x)`. Zatem `f(x)=x`
O wiele łatwiejsze niż się wydawało. Oczywiście \(\displaystyle{ p=2}\) nie spełnia warunków zadania, a dalej niech \(\displaystyle{ p\ge 3}\) (wtedy oczywiście \(\displaystyle{ p-1}\) jest liczbą parzystą).
Przypuśćmy, że dla pewnego \(\displaystyle{ x\in \NN}\) zachodzi \(\displaystyle{ \frac{2^{p-1}-1}{p}=x^{2}}\), tj. \(\displaystyle{ 2^{p-1}-1=px^{2}}\),
a to, na mocy wzoru na różnicę kwadratów, jest równoważne równości \(\displaystyle{ \left(2^{\frac{p-1}{2}}-1 \right)\left(2^{\frac{p-1}{2}}+1\right)=px^{2}}\)
Liczby \(\displaystyle{ 2^{\frac{p-1}{2}}-1, \ 2^{\frac{p-1}{2}}+1}\) są liczbami nieparzystymi o różnicy \(\displaystyle{ 2}\), więc są względnie pierwsze.
Udowodnimy pokrótce, że wobec tego jest \(\displaystyle{ \left(2^{\frac{p-1}{2}}-1=py^{2}, \ 2^{\frac{p-1}{2}}+1=z^{2}\right) \vee \left(2^{\frac{p-1}{2}}-1=z^{2}, \ 2^{\frac{p-1}{2}}+1=py^{2}\right)}\) dla pewnych liczb naturalnych \(\displaystyle{ yz}\), przy czym \(\displaystyle{ yz=x}\).
Niech \(\displaystyle{ q}\) będzie liczbą pierwszą dzielącą \(\displaystyle{ x^{2}}\); wtedy oczywiście \(\displaystyle{ q}\) dzieli \(\displaystyle{ \left(2^{\frac{p-1}{2}}-1 \right)\left(2^{\frac{p-1}{2}}+1\right)}\) i z uwagi na to, że czynniki te są względnie pierwsze, \(\displaystyle{ q}\) dzieli dokładnie jeden z nich.
Ponadto każde \(\displaystyle{ q\in \PP}\) wchodzi do rozkładu \(\displaystyle{ x^{2}}\) z parzystym wykładnikiem (oczywiste). Analogicznie \(\displaystyle{ p}\) dzieli iloczyn w LHS, więc z uwagi na to, że czynniki są względnie pierwsze – dzieli dokładnie jeden z nich.
Przejdźmy do rozważenia przypadków: \(\displaystyle{ 1^{\circ}}\) Przypuśćmy, że \(\displaystyle{ 2^{\frac{p-1}{2}}-1=py^{2}, \ 2^{\frac{p-1}{2}}+1=z^{2}}\)
Przyjrzyjmy się zwłaszcza tej drugiej równości: przepiszmy ją w postaci \(\displaystyle{ 2^{\frac{p-1}{2}}=(z-1)(z+1)}\)
Wszystkie dodatnie dzielniki liczby \(\displaystyle{ 2^{\frac{p-1}{2}}}\) są postaci \(\displaystyle{ 2^{k}, \ k\in \NN}\), więc musi być \(\displaystyle{ z-1=2^{i}, \ z+1=2^{j}}\), przy czym \(\displaystyle{ i+j=\frac{p-1}{2}, \ i<j}\). Ponadto są to liczby tej samej parzystości, bo różnią się o \(\displaystyle{ 2}\), więc muszą obie być parzystymi. Jednak dla \(\displaystyle{ i,j\in \NN^{+}, \ j>i}\) mamy \(\displaystyle{ 2^{j}-2^{i}\ge 2^{i+1}-2^{i}=2^{i}\ge 2}\) z równością dla \(\displaystyle{ j=2, \ i=1}\) i właśnie ten przypadek równości musi zajść, czyli \(\displaystyle{ p-1=2\cdot (2+1)=6}\), stąd \(\displaystyle{ p=7}\)
\(\displaystyle{ 2^{\circ}}\) Teraz przypuśćmy, że dla pewnych \(\displaystyle{ y,z\in \NN^{+}}\) jest \(\displaystyle{ 2^{\frac{p-1}{2}}-1=z^{2}, \ 2^{\frac{p-1}{2}}+1=py^{2}}\)
Oczywiście przyjrzymy się tej pierwszej równości, ponieważ znacznie łatwiej prowadzi do konkluzji. Jeśli \(\displaystyle{ 4|(p-1)}\), to \(\displaystyle{ 2^{\frac{p-1}{2}}}\) jest kwadratem liczby całkowitej dodatniej nie mniejszej niż \(\displaystyle{ 2}\), więc \(\displaystyle{ 2^{\frac{p-1}{2}}-1}\) nie może być kwadratem, wszak dla \(\displaystyle{ k\in \NN^{+}}\) mamy \(\displaystyle{ (k+1)^{2}-k^{2}=2k+1>1}\).
Natomiast jeśli \(\displaystyle{ 4\nmid (p-1)}\), to albo mamy \(\displaystyle{ p=3}\), a wtedy warunki zadania są spełnione, co łatwo sprawdzamy, albo \(\displaystyle{ \frac{p-1}{2}>2}\), a wówczas \(\displaystyle{ 2^{\frac{p-1}{2}}-1\equiv 3\pmod{4}}\). Tymczasem kwadraty liczb całkowitych przystają do \(\displaystyle{ 0}\) lub \(\displaystyle{ 1}\) modulo \(\displaystyle{ 4}\), a więc w tym ostatnim przypadku mamy sprzeczność.
Podsumowanie Jedyne liczby pierwsze \(\displaystyle{ p}\), dla których \(\displaystyle{ \frac{2^{p-1}-1}{p}}\) jest kwadratem liczby naturalnej, to \(\displaystyle{ p=3, \ p=7}\).
Dla \(\displaystyle{ n=1}\) jest to twierdzenie Kroneckera; gdy \(\displaystyle{ N > \frac{1}{\epsilon} }\) należy rozważyć \(\displaystyle{ N+1}\) liczb \(\displaystyle{ \{ ma \} }\) gdy \(\displaystyle{ 1 \leq m \leq N+1}\) i użyć zsD dla \(\displaystyle{ N}\) szufladek \(\displaystyle{ < \frac{0}{N}, \frac{1}{N} ), ..., < \frac{N-1}{N}, \frac{N}{N} )}\).
Czyli jak znaleźć z tego \(\displaystyle{ k}\) oraz \(\displaystyle{ m_{i}}\)?
Dodano po 14 minutach 31 sekundach:
Zadanie 18
Ukryta treść:
Po "cd" sądzę, że reszta dowodu zginęła Molowi, a pierwszej cześci rozwiązania nie mogew znaleźć
Ad 25.
Tam nie ma żadnego pomysłu, żadnej finezji, a tylko pracochłonne obliczenia. Uznałem że szybciej wyliczę te współczynniki sumując współczynniki przy wszystkich \(\displaystyle{ x^2 \ i \ x^{14}}\) , niż wpadnę na pomysł jak szybciej i przyjemniej je wyliczyć. Może ktoś zna mniej prymitywny sposób i tu go zamieści.
5:
O ile dobrze rozumiem treść zadania, to wystarczy wskazać przykładowe ciągi aby wykazać tezę.
1) \(\displaystyle{ b>0}\)
a) \(\displaystyle{ (a \le b ) \wedge (r=1) \wedge (q=b) }\)
b) \(\displaystyle{ (a > b ) \wedge (r= \frac{-1}{4} ) \wedge (q= \frac{1}{2} ) }\)
3) \(\displaystyle{ b<0}\)
a) \(\displaystyle{ (a > b ) \wedge (r=-1) \wedge (q=-b) }\)
b) \(\displaystyle{ (a \le b ) \wedge (r= \frac{1}{4} ) \wedge (q= \frac{1}{2} ) }\)
Zauważmy, że każdą liczbę rzeczywistą można przybliżyć liczbą wymierną z oczekiwaną dokładnością ustalmy , że wybieramy
dla każdego \(\displaystyle{ a_{i}}\) taką liczbę wymierną \(\displaystyle{ q_{i}= \frac{m_{i}}{o_{i}} }\) tak, że \(\displaystyle{ \left| a_{i}-q_{i}\right| < \epsilon}\). sprowadźmy wszystkie \(\displaystyle{ q_{i}}\) do wspólnego mianownika. Otrzymamy dla każdego \(\displaystyle{ i }\). następujące nierówności \(\displaystyle{ \left| a_{i}- \frac{m'_{i}}{NWD(o_{1},o_{2},o_{3}..., o_{n})} \right| < \epsilon}\). Pomnóżmy przez ten mianownik - nazwijmy go \(\displaystyle{ O}\) otrzymamy \(\displaystyle{ \left| a_{i}-m_{i}\right| < \epsilon O}\). Jeśli na początku zaczniemy od \(\displaystyle{ \epsilon ' = \frac{\epsilon}{O} }\) to otrzymamy, że ciąg \(\displaystyle{ m_{i}}\) oraz \(\displaystyle{ k=O}\) spełniają naszą tezę.
Ostatnio zmieniony 18 lut 2021, o 23:26 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód:Poprawa wiadomości.
A jeśli odtworzę rozumowanie po znalezieniu \(\displaystyle{ O}\) dla epsilon prim, to powinno być dobrze. Dzięki temu, że O dla konstrukcji w części pierwszej i drugiej będą takie same, a przybliżenia jeszcze lepsze, to teza będzie spelniona.