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.
\(\displaystyle{ s \in \left\langle -p;p-k+1\right\rangle}\)
Jednym słowem, długość zbioru \(\displaystyle{ A_{k}}\) mieści się w granicy od jeden do: \(\displaystyle{ p+1}\)
Musimy wymóc od funkcji f jeszcze jednej własności, otóż, jeżeli wartości funkcji będą należeć do zbioru \(\displaystyle{ A_{k}}\), to również wartościami funkcji muszą być brzegi zbioru \(\displaystyle{ A_{k}}\)
I jeszcze jedno , zbiorów o długości k jest:
\(\displaystyle{ (2p+2-k)}\)
znaczy:
\(\displaystyle{ s \wedge s+(k-1)}\)
To da nam , że nic nie będzie się powtarzać.
więc zaczynajmy:
1). dla:
\(\displaystyle{ k=1}\)
jest możliwości widać gołym okiem: \(\displaystyle{ 2p+1}\)
Wykażemy, że każde rozwiązanie tego układu równań funkcyjnych spełnia warunek \(\displaystyle{ f\left(\frac{p}{q}\right)=\frac{p+q}{2}f(1)}\) dla \(\displaystyle{ (p,q)=1, \ p,q\in\NN^{+}}\), przy czym \(\displaystyle{ f(1)}\) jest dowolnie wybraną liczbą całkowitą.
Zaczniemy od dowodu indukcyjnego następującego spostrzeżenia: jeśli \(\displaystyle{ r}\) jest dowolną wymierną liczbą dodatnią, to równość \(\displaystyle{ f(n+r)=\frac{n+r+1}{r+1}f(r) \ \spadesuit}\) zachodzi dla wszystkich \(\displaystyle{ n\in \NN^{+}}\) \(\displaystyle{ 1^{\circ}}\) Dla \(\displaystyle{ n=1}\) mamy wykazać \(\displaystyle{ f(r+1)=\frac{r+2}{r+1}f(r)}\), co się przekształca do \(\displaystyle{ (r+1)f(r+1)=(r+2)f(r)}\)
Rzecz jasna, mamy \(\displaystyle{ r+1>1}\), zatem ta równość jest konsekwencją drugiego z równań układu: \(\displaystyle{ xf(x)=(x+1)f(x-1), \ x>1 \ (*)}\)
dla \(\displaystyle{ x:=r+1}\). \(\displaystyle{ 2^{\circ}}\) Przypuśćmy, że dla pewnego \(\displaystyle{ n\in \NN^{+}}\) zachodzi \(\displaystyle{ f(n+r)=\frac{n+r+1}{r+1}f(r)}\)
Wówczas dostajemy znów na mocy \(\displaystyle{ (*), \ (n+1+r)f(n+1+r)=(n+r+2)f(n+r)=(n+r+2)\cdot \frac{n+r+1}{r+1}f(r)}\)
a stąd natychmiast \(\displaystyle{ f(n+1+r)=\frac{n+r+2}{r+1}f(r)}\)
co kończy krok indukcyjny.
Wstawiając w otrzymanej równości \(\displaystyle{ r=1}\) dostajemy \(\displaystyle{ f(n+1)=\frac{n+2}{2}f(1), \ n\in \NN^{+}}\)
a ponieważ \(\displaystyle{ \frac{1+1}{2}f(1)=f(1)}\), więc ogólnie możemy zapisać \(\displaystyle{ f(n)=\frac{n+1}{2}f(1), \ n\in\NN^{+}}\)
Z uwagi na równość \(\displaystyle{ f(x)=f\left(\frac{1}{x}\right)}\) dostajemy teraz \(\displaystyle{ f\left(\frac{1}{n}\right)=\frac{n+1}{2}f(1), \ n\in\NN^{+}}\)
Następnie przechodzimy do rozwikłania tajemnicy \(\displaystyle{ f\left(\frac{p}{q}\right), \ p,q\in \NN^{+}, \ (p,q)=1}\)
W tym celu przyda się algorytm Euklidesa. Postępujemy następująco:
jeśli \(\displaystyle{ p<q}\), to zapisujemy \(\displaystyle{ f\left(\frac{p}{q}\right)=f\left(\frac{q}{p}\right)}\), w przeciwnym razie nie robimy nic.
Następnie dzielimy z resztą większą z liczb \(\displaystyle{ p,q}\) przez mniejszą, jeśli np. \(\displaystyle{ p>q}\), to \(\displaystyle{ p=kq+r, \ r\in\left\{1,\ldots q-1\right\}}\) i wówczas mamy \(\displaystyle{ f\left(\frac{p}{q}\right)=f\left(k+\frac{r}{q}\right)=\frac{k+\frac{r}{q}+1}{\frac{r}{q}+1}f\left(\frac{r}{q}\right)}\)
Po tym kroku korzystamy z \(\displaystyle{ f\left(\frac{r}{q}\right)=f\left(\frac{q}{r}\right)}\) i tak dalej, aż uzyskamy resztę równą \(\displaystyle{ 1}\).
Jako że \(\displaystyle{ \frac{k+\frac{r}{q}+1}{\frac{r}{q}+1}=\frac{kq+r+q}{r+q}=\frac{p+q}{r+q}}\),
rozważenie \(\displaystyle{ r=1}\) skłania nas do postawienia hipotezy, że \(\displaystyle{ f\left(\frac{p}{q}\right)=\frac{p+q}{2}f(1), \ p,q\in \NN^{+}, \ (p,q)=1}\)
Udowodnimy ją za pomocą indukcji zupełnej po sumie \(\displaystyle{ p+q}\).
Gdy \(\displaystyle{ p+q=2}\), to nasza hipoteza niewątpliwie jest prawdziwa, wszak jedyna możliwość czyniąca zadość takiemu warunkowi to \(\displaystyle{ p=q=1}\) i mamy \(\displaystyle{ f(1)=f\left(\frac{1}{1}\right)=\frac{1+1}{2}f(1)}\)
Przypuśćmy, że dla pewnej liczby \(\displaystyle{ m\in \NN^{+}, \ m>2}\) własność \(\displaystyle{ f\left(\frac{p}{q}\right)=\frac{p+q}{2}f(1)}\) zachodzi dla wszystkich takich par względnie pierwszych liczb całkowitych dodatnich \(\displaystyle{ p,q}\), że \(\displaystyle{ p+q<m}\). Niech teraz \(\displaystyle{ p_{1}, q_{1}\in \NN^{+}, \ (p_{1}, q_{1})=1, \ p_{1}+q_{1}=m}\)
Dla ustalenia uwagi (jedyne, co się ewentualnie zmienia, to zamiana \(\displaystyle{ p_{1}, q_{1}}\) miejscami z tożsamości \(\displaystyle{ f(x)=f\left(\frac{1}{x}\right)}\)) niech \(\displaystyle{ p_{1}>q_{1}}\). Mamy wówczas \(\displaystyle{ p_{1}=q_{1}\cdot k_{1}+r_{1}}\), przy czym \(\displaystyle{ k_{1}\in \NN^{+}, \ r_{1}\in \left\{1,2\ldots q_{1}-1\right\}}\)
Otrzymujemy wówczas \(\displaystyle{ f\left(\frac{p_{1}}{q_{1}}\right)=f\left(k_{1}+\frac{r_{1}}{q_{1}}\right)=\frac{k_{1}+\frac{r_{1}}{q_{1}}+1}{\frac{r_{1}}{q_{1}}+1}f\left(\frac{r_{1}}{q_{1}}\right)=\frac{k_{1}+\frac{r_{1}}{q_{1}}+1}{\frac{r_{1}}{q_{1}}+1}\cdot \frac{r_{1}+q_{1}}{2}f(1)}\)
przy czym przedostatnia równość wynika z udowodnionego faktu \(\displaystyle{ (\spadesuit)}\), a ostatnia z założenia indukcyjnego, wszak \(\displaystyle{ r_{1}+q_{1}\le k_{1}q_{1}+r_{1}<k_{1}q_{1}+r_{1}+q_{1}=p_{1}+q_{1}=m}\)
Pozostaje odnotować, że \(\displaystyle{ \frac{k_{1}+\frac{r_{1}}{q_{1}}+1}{\frac{r_{1}}{q_{1}}+1}\cdot \frac{r_{1}+q_{1}}{2} =\frac{p_{1}+q_{1}}{2}}\)
To kończy dowód.
Innymi słowy jest \(\displaystyle{ \aleph_{0}}\) takich funkcji, każdą z nich możemy w pełni poznać przez ustalenie wartości \(\displaystyle{ f(1)}\), a wówczas wartości na pozostałych argumentach są zadawane wg \(\displaystyle{ f\left(\frac{p}{q}\right)=\frac{p+q}{2}f(1), \ (p,q)=1}\)
PS To zadanie już chyba widziałem w jakimś późniejszym miksie, jak teraz myślę…
PPS Naprawdę miło byłoby, gdybyś reagował na moje wątpliwości co do treści zadań, jak w miksie szesnastym dotyczącym teorii liczb.
Dodano po 7 godzinach 35 minutach 1 sekundzie:
21.:
\(\displaystyle{ G_{0}=1, \ G_{1}=\frac{1}{2}, \ G_{n+1}=\frac{1}{\frac{1}{G_{n}}+\frac{1}{G_{n-1}}-1}, \ n\ge 1}\)
Dowód tego to trywialne wykorzystanie zależności rekurencyjnej ciągu \(\displaystyle{ F_{n}}\), natomiast mnie bardziej zastanawia *w szczególności*. Zabrałbym się za to w ten sposób: \(\displaystyle{ G_{n}}\) to funkcja wymierna od \(\displaystyle{ F_{n}}\), która jest odwracalna (bo malejąca) w nieujemnych. Konkretnie funkcja \(\displaystyle{ h(F_{n}), \ h(x)=\frac{1}{x+1}}\).
Gdyby było \(\displaystyle{ G_{n+1}=f(G_{n})}\) dla pewnej funkcji \(\displaystyle{ f}\), to \(\displaystyle{ F_{n+1}=h^{-1}(G_{n+1})=h^{-1}(f(h(F_{n})))}\)
Czyli w zasadzie sprowadziliśmy problem do podobnego pytania, czy istnieje taka funkcja \(\displaystyle{ \kappa}\), że dla dowolnego \(\displaystyle{ n\in \NN}\) zachodzi \(\displaystyle{ F_{n+1}=\kappa(F_{n})}\)
(jeszcze się tutaj pojawia jedna subtelność, ale mniejsza z tym). Odpowiedź na to pytanie powinna być znana. Nie żebym ją znał.
