Uniwersytet im. A. Mickiewicza w Poznaniu
Kilka lat temu, w czasie Szkoły Matematyki Poglądowej, w luźnej, zakulisowej rozmowie, zaproponowałem, by to, co zwykliśmy nazywać „zbiorem zadań” przemianować na „ciąg zadań” – zadania są przecież zazwyczaj ułożone w jakiejś sensownej kolejności i prawie zawsze ponumerowane. Nazwa ta niestety nie przyjęła się – prawdopodobnie dlatego, że zbyt wiele książek wymagałoby wymiany okładek. Ale do kącika pasuje.
A zadania będą, rzecz jasna, o ciągach. Mają one ten urok, że mogą dotyczyć praktycznie każdego działu matematyki. Są trochę jak Fasolki Bertiego Botta – nigdy nie wiadomo, na co się trafi…
Uwaga dotycząca oznaczeń. Przez \((a)_k^m\) rozumiemy ciąg \((a_k,a_{k+1},\ldots,a_m)\) dla ustalonych całkowitych \(k\le m\); dopuszczamy przy tym \(m=\infty,\) a niekiedy również \(k=-\infty.\) Jest to zapis analogiczny do zapisu
funkcji \(f:X\to\ldots,\) w którym określamy dziedzinę, ale nie chcemy nazywać zmiennej. W takich okolicznościach piszemy „funkcja \(f\)” i analogicznie – „ciąg \((a)\)”.
Przykład (57 OM, zmodyfikowane). Niech \(c\) będzie ustaloną liczbą całkowitą dodatnią. Ciąg \((a)_1^\infty\) liczb całkowitych dodatnich spełnia rekurencję \(a_{n+1}=\tau(a_n)+c\) dla każdego \(n\ge1,\) w czym \(\tau(m)\) oznacza liczbę dzielników liczby \(m.\) Wykazać, że ciąg \((a)\) jest od pewnego miejsca okresowy.
Rozwiązanie. Zauważmy najpierw, że \(\tau(m)\le\frac12m+1,\) gdyż w przedziale \((m/2,m)\) nie ma dzielników \(m.\) Wynika z tego, że jeśli \(a_n>2c+2,\) to \(a_{n+1} \le \frac12a_n+1+c < a_n.\) Istnieje zatem liczba \(N,\) dla której \(a_N\le2c+2.\) Z drugiej strony, jeśli \(a_n\le2c+2,\) to mamy \(a_{n+1}\le\frac12a_n+1+c\le2c+2.\) Z tego wynika, że \(1\le a_n\le2c+2\) dla wszystkich \(n\ge N.\) Zbiór wartości ciągu jest skończony (ale ciąg nie jest), a więc dla pewnych całkowitych \(M,t>0\) zachodzi równość \(a_{M+t}=a_M.\) Każdy wyraz ciągu jednoznacznie określa następny, a więc indukcyjnie dowodzimy, że \(a_{n+t}=a_n\) dla wszystkich \(n\ge M.\)
Mamy tu elementy teorii liczb, analizy i kombinatoryki. Brakuje tylko geometrii. Ale geometria będzie – jest ukryta w jednym z poniższych zadań.
Zadania
Dana jest liczba naturalna \(n\ge3\) oraz ciąg arytmetyczny \((a)=(a_1,a_2,\ldots,a_n).\) Wiadomo, że liczba \(a_1+2a_2+\ldots+na_n\) jest wymierna. Dla jakich \(n\) wynika z tego, że co najmniej jeden wyraz ciągu \((a)\) jest liczbą wymierną? (52 OM)
Wskazówka Dla wszystkich \(n\equiv 1\pmod 3.\) Wystarczą podstawowe własności ciągu arytmetycznego i wzór \(1^2+2^2+\ldots+n^2=\frac 16n(n+1)(2n+1).\)
Dany jest ciąg \((b)_0^\infty\) różnych, nieujemnych liczb całkowitych, spełniający warunki: \(b_0=0\) i \(b_n<2n\) dla \(n>0.\) Udowodnić, że dla każdej liczby całkowitej \(m\geq 0\) istnieją liczby całkowite \(k,l\ge0,\) dla których \(b_k+b_l=m.\) (70 OM)
Wskazówka Dla \(m=2n-1\) w jednej z par \((k,m-k)\) (\(0\le k<n\)) obie liczby są wyrazami ciągu \((b)\) (zasada szufladkowa). Dla \(m=2n\) jest podobnie, tylko trzeba rozważyć przypadki, w których \(n\) jest lub nie jest wyrazem ciągu \((b).\)
Ciąg \((a)_1^\infty\) ma taką własność, że dla wszystkich całkowitych dodatnich \(k,\) \(l\) zachodzi podzielność \(k+l\mid a_k+a_l.\) Udowodnić, że jeśli \(k\neq l,\) to \(k-l\mid a_k-a_l.\) (74 OM)
Wskazówka \(a_k-a_l=(a_k+a_m)-(a_l+a_m).\) Potrzebujemy takiego \(m,\) żeby \(k-l\mid k+m,l+m.\)
Rozważmy zbiór wszystkich \(n\)-wyrazowych ciągów o wyrazach ze zbioru \(\{1,2,\ldots,k\}.\) Z każdego takiego ciągu wybieramy najmniejszy wyraz. Udowodnić, że suma wszystkich wybranych wyrazów jest równa \(1^n+2^n+\ldots+k^n.\) (54 OM)
Wskazówka Jest dokładnie \((k-m+1)^n-(k-m)^n\) takich ciągów z minimum równym \(m.\)
Dana jest liczba naturalna \(k.\) Ciąg \((a)_1^\infty\) określamy równościami: \(a_1=k+1\) oraz \(a_{n+1}=a_n^2-ka_n+k\) dla \(n\ge1.\) Wykazać, że jeśli \(m\neq n,\) to liczby \(a_n\) i \(a_m\) są względnie pierwsze. (53 OM)
Wskazówka Niech \(P_n=a_1a_2\ldots a_{n-1}\) (\(P_1=1\)). Indukcyjnie \(a_n=P_n+k\) oraz \(a_n\equiv 1\pmod k.\) Dla \(n<m\) mamy \(a_n\mid P_m.\) Resztę roboty wykona algorytm Euklidesa.
Dla każdej liczby całkowitej dodatniej \(n\) wyznaczyć największą możliwą długość ciągu spełniającego następujące trzy warunki:
wszystkie wyrazy należą do zbioru \(\{1,2,\ldots,n\},\)
żadne dwa kolejne wyrazy nie są równe,
w wyniku wykreślenia części wyrazów nie można otrzymać ciągu postaci \((x,y,x,y)\) dla \(x\neq y.\) (62 OM)
Wskazówka Nietrudno znaleźć taki \((2n-1)\)-wyrazowy ciąg. Wykażmy indukcyjnie, że dłuższego nie ma. Dla \(n>1\) w najdłuższym ciągu – nazwijmy go \((a)_1^m\) – pewna wartość się powtarza. Niech \(a_i=a_j=x,\) przy czym w ciągu \((a')=(a_{i+1},\ldots,a_{j-1})\) nie występuje \(x.\) Założenie indukcyjne stosujemy do ciągów \((a')\) i \((a”)\!=\!(a_1,\ldots,a_{i-1},x,a_{j+1},\ldots,a_m),\) które spełniają wymagane warunki i mają rozłączne zbiory wartości.
Ustalmy liczbę pierwszą \(p\) oraz liczby całkowite dodatnie \(a,n<p.\) Niech \(A\) będzie zbiorem reszt z dzielenia przez \(p\) liczb \(a,2a,3a,\ldots,na.\) Dowieść, że ze zbioru \(A\) można wybrać \(\lfloor\sqrt{n}\rfloor\) elementów, które uporządkowane rosnąco są kolejnymi wyrazami pewnego ciągu arytmetycznego. (11 WLM)
Wskazówka Niech \(r_k\) będzie resztą z dzielenia \(ka\) przez \(p.\) Ciąg \((r)_1^n\) jest różnowartościowy i dla pewnych różnych \(k_1,k_2\in\{0,1,\ldots,\lfloor\sqrt n\rfloor\}\) zachodzi nierówność \(|r_{k_1}-r_{k_2}|<p/\lfloor\sqrt n\rfloor.\) Dla \(d=|k_1-k_2|\) ciąg \((r_{kd})_{k=1}^{\lfloor\sqrt{n}\rfloor}\) jest arytmetyczny.
Niech \(n\ge3\) będzie liczbą naturalną. Ciąg \((C)_0^n\) liczb nieujemnych spełnia warunek \(C_pC_r+C_qC_s=C_{p+q}C_{q+r}\) dla wszystkich całkowitych \(p,q,r,s\ge0\) spełniających równość \(p+q+r+s=n.\) Znając \(C_1=1,\) wyznaczyć wszystkie możliwe wartości \(C_2.\) (60 OM)
Wskazówka Rozważmy wielokąt foremny \(A_0A_1\ldots A_{n-1}\) z \(|A_0A_1|=1\) i przyjmijmy \(C_i=|A_0 A_i|\) (z konwencją \(A_n=A_0\) i \(C_n=C_0=0\)). Zgodnie z twierdzeniem Ptolemeusza ciąg \((C)_0^n\) spełnia opisane w treści zależności. To samo twierdzenie pozwala uzasadnić (choć jest to trudniejsze), że zależność z zadania jednoznacznie wyznacza wyrazy ciągu \((C)_0^n.\)
Ciąg \((a)_1^\infty\) zdefiniowany jest następująco \(a_1=\frac12\) oraz \(a_{k+1}=\frac1{1+a_k-a_k^2}\) dla \(k\ge1.\) Dowieść, że \(a_1\cdot a_2 \cdot \ldots \cdot a_n < \frac1{\sqrt{2n}}\) dla wszystkich \(n\ge1.\) (5 WLM)
Wskazówka Indukcyjnie \(0<a_n<1\) oraz \((a_1a_2\ldots a_n)^2=\frac 1{a_{n+1}}-1.\) Dla \(b_n=1/(\frac 1{a_{n+1}}-1)\) mamy \(b_n+\frac 1{b_n}=b_{n+1}-2,\) indukcyjnie \(b_n>2n.\)