Afiliacja: Uniwersytet im. A. Mickiewicza w Poznaniu
Jednym z najprostszych przykładów omawianych tu konstrukcji jest następujące rozumowanie, znane już Euklidesowi. Niech \(p_1,p_2,\ldots,p_n\) będą różnymi liczbami pierwszymi. Dowolny dzielnik pierwszy \(p_{n+1}\) liczby \(p_1p_2\ldots p_n+1\) jest różny od \(p_1,p_2,\ldots,p_n.\) Możemy w ten sposób utworzyć nieskończony ciąg różnych liczb pierwszych.
Ogólna idea jest następująca. Mając już obiekty \(\mathcal{A}_1,\mathcal{A}_2,\ldots,\mathcal{A}_n,\) używamy ich w jakiś sposób do skonstruowania kolejnego obiektu \(\mathcal{A}_{n+1}.\) Tymi obiektami mogą być liczby, ale również zbiory, funkcje, konfiguracje geometryczne bądź kombinatoryczne i wiele innych.
Jako dodatkowe przykłady podam tu dwa zadania, które ukazały się już w kąciku numer 7 (\(\Delta_{19}^7\)), poświęconemu indukcji.
Przykład 1. Dla każdego całkowitego dodatniego \(n\) istnieje \(n\)-cyfrowa wielokrotność liczby \(2^n,\) w której zapisie nie ma innych cyfr niż \(1\) i \(2.\) Rozwiązanie. Powiedzmy, że dla pewnego \(n\) znamy już szukaną liczbę \(a_n.\) Wykażemy, że możemy przyjąć \(a_{n+1}=a_n+10^n\) lub \(a_{n+1}=a_n+2\cdot10^n.\) Są to liczby \((n+1)\)-cyfrowe powstałe przez dopisanie na początku zapisu dziesiętnego liczby \(a_n\) cyfry \(1\) lub \(2.\) Zapiszmy \(a_n=k\cdot2^n\) dla pewnego naturalnego \(k.\) Wówczas \[a_n+10^n = (k+5^n)\cdot2^n, \ \ \ a_n+2\cdot10^n = (k+2\cdot5^n)\cdot2^n.\] Jeśli \(k\) jest liczbą nieparzystą, to pierwsza z powyższych liczb dzieli się przez \(2^{n+1},\) a jeśli parzystą – druga. Konstrukcję rozpoczynamy od \(a_1=2.\)
Przykład 2. Dla każdej liczby naturalnej \(n\ge7\) można tak umieścić na okręgu liczby od \(1\) do \(n,\) by wartość bezwzględna różnicy sąsiednich liczb zawsze była kwadratem liczby naturalnej.
Rozwiązanie. Wykażemy mocniejszą tezę – można to zrobić tak, by dodatkowo liczby \(n\) i \(n-1\) sąsiadowały. Jeśli znamy takie rozmieszczenie dla \(n\) liczb, to możemy łatwo otrzymać analogiczne dla \(n+3\) liczb – wystarczy pomiędzy \(n\) i \(n-1\) wpisać kolejno: \(n+1,\) \(n+2,\) \(n+3.\) Aby dokończyć dowód, trzeba jeszcze podać konstrukcje dla \(n=7,8,9.\) Są one następujące: \[7,6,2,1,5,4,3; \ \ \ 8,7,6,5,1,2,3,4; \ \ \ 9,8,4,3,7,6,2,1,5.\] Bardzo istotne jest, by oprócz kroku indukcyjnego konstrukcji sformułować i uzasadnić odpowiednie warunki początkowe, gwarantujące, że dane obiekty istnieją dla każdego \(n,\) które nas interesuje.
Zadania
1. Udowodnić, że dla \(n>1\) w wyrażeniu \(0+1+2+\ldots+n\) można zamienić niektóre ze znaków \(+\) na \(-\) w taki sposób, by jego wartość była równa \(0\) lub \(1.\)
Jeśli \(s\in\{0,1\},\) to \(s-(n+1)+(n+2)\in\{0,1\}\) albo \(s+(n+1)-(n+2)\in\{0,1\}.\)
2. Dowieść, że dla każdego naturalnego \(n\ge2\) istnieje wielościan wypukły, którego ścianami są: jeden kwadrat i \(2n\) trójkątów rozwartokątnych.
W kroku indukcyjnym do jednej ze ścian trójkątnych danego wielościanu doklejamy czworościan. Wypukłość wielościanu i rozwartokątność ścian trójkątnych można zagwarantować, dobierając odpowiednio wysokość doklejonego czworościanu.
3. Dane są wektory \(\vec{v}_1,\vec{v}_2,\vec{v}_3,\ldots,\) każdy o długości \(1.\) Udowodnić, że istnieją liczby \(\varepsilon_1,\varepsilon_2,\varepsilon_3,\ldots\) ze zbioru \(\{-1,1\}\) o tej własności, że dla każdego całkowitego dodatniego \(n\) zachodzi nierówność \(|\varepsilon_1\vec{v}_1+\varepsilon_2\vec{v}_2+\ldots+\varepsilon_n\vec{v}_n|\le\sqrt{n}.\)
Niech \(\vec{u}_n=\varepsilon_1\vec{v}_1+\varepsilon_2\vec{v}_2+\ldots+\varepsilon_n\vec{v}_n.\) Liczbę \(\varepsilon_{n+1}\) wybieramy w taki sposób, by kąt pomiędzy wektorami \(\vec{u}_n\) i \(\varepsilon_{n+1}\vec{v}_{n+1}\) był nie mniejszy niż \(90^\circ.\)
4. Wykazać, że istnieje ciąg liczb całkowitych dodatnich, w którym każda liczba całkowita dodatnia występuje dokładnie raz, a przy tym każdy wyraz, począwszy od drugiego, jest dzielnikiem lub wielokrotnością poprzedniego wyrazu (II WLM).
Załóżmy, że mamy ustalone wyrazy \(a_1,a_2,\ldots,a_{2n}.\) Niech \(a_{2n+2}\) będzie najmniejszą liczbą całkowitą dodatnią, która jeszcze nie pojawiła się w ciągu, następnie \(a_{2n+1}\) – dowolną wspólną wielokrotnością \(a_{2n}\) i \(a_{2n+2},\) różną od \(a_1,a_2,\ldots,a_{2n}\) oraz \(a_{2n+2}.\)
5. Udowodnić, że dla każdej liczby naturalnej \(n\ge3\) istnieją dwa rozłączne \(n\)-elementowe zbiory, \(A\) i \(B,\) zawierające wyłącznie liczby całkowite dodatnie spełniające następujący warunek: sumy wszystkich elementów w zbiorach \(A\) i \(B\) są równe oraz iloczyny wszystkich elementów w zbiorach \(A\) i \(B\) są równe (LXI OM).
Niech \(A\) i \(B\) będą zbiorami \(n\)-elementowymi, a \(A'\) i \(B'\) zbiorami \(m\)-elementowymi spełniającymi wymagane warunki. Wówczas dla odpowiednio dużego \(k\) zbiory \((m+n)\)-elementowe \(A\cup kA'\) i \(B\cup kB'\) również je spełniają (\(kX\) oznacza zbiór wszystkich elementów zbioru \(X\) pomnożonych przez \(k\)). Wystarczy więc znaleźć odpowiednie pary zbiorów dla \(n=3,4,5.\)
6. Dowieść, że dla każdej liczby naturalnej \(n\ge2\) istnieje \(n\)-elementowy zbiór \(A\) liczb całkowitych dodatnich o następującej własności: dla każdych dwóch różnych elementów \(a,b\in A\) zachodzi równość \(\texttt{NWD}(a,b)=|a-b|\) (XIV WLM).
Mając zbiór \(\{a_1,\ldots,a_n\}\) spełniający zadane warunki, tworzymy zbiór \(\{b_1,\ldots,b_n,b_{n+1}\}\) następująco: \(b_j=a_j+a_1a_2\ldots a_n\) dla \(j=1,2,\ldots,n\) oraz \(b_{n+1}=a_1a_2\ldots a_n.\)
7. Udowodnić, że dla \(n\geq 12\) istnieje permutacja \((a_1,a_2,\ldots,a_n)\) ciągu \((1,2,\ldots,n)\) o następującej własności: \(a_k+k\) jest kwadratem liczby naturalnej dla każdego \(k\in\{1,2,\ldots,n\}.\)
Załóżmy, że liczby \(n_1<n_2\) mają tę własność, że \(n_1+n_2+1=a^2\) dla pewnej liczby naturalnej \(a.\) Wówczas jeśli szukana permutacja istnieje dla liczby \(n_1,\) to również istnieje dla liczby \(n_2.\) Dla dowodu rozważmy odpowiednią permutację \((a_1,\ldots,a_{n_1})\) dla liczby \(n_1\) oraz \(a_k=a^2-k\) dla \(n_1<k\le n_2.\) Załóżmy teraz indukcyjnie, że opisana w zadaniu własność zachodzi dla każdej liczby \(m\) spełniającej \(12\leq m<n.\) Wybierzmy największe takie \(m<n,\) że \(m+n+1\) jest kwadratem. Wtedy \(m\ge n-2\sqrt{2n}\) (dlaczego?), co jest większe od \(11\) dla \(n\ge26.\)
Pozostaje uzasadnić twierdzenie dla liczb od 12 do 25.