Delta 12/2024

Konstrukcje indukcyjne

Bartłomiej Bzdęga

matematyka algebra kombinatoryka szkoła teoria liczb teoria mnogości

Jednym z najprostszych przykładów omawianych tu konstrukcji jest następujące rozumowanie, znane już Euklidesowi. Niech $p_{1}, p_{2}, \dots, p_{n}$ będą różnymi liczbami pierwszymi. Dowolny dzielnik pierwszy $p_{n + 1}$ liczby $p_{1} p_{2} \dots p_{n} + 1$ jest różny od $p_{1}, p_{2}, \dots, 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 $A_{1}, A_{2}, \dots, A_{n},$ używamy ich w jakiś sposób do skonstruowania kolejnego obiektu $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 ( $Δ_{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 \cdot 10^{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 \cdot 2^{n}$ dla pewnego naturalnego $k .$ Wówczas $a_{n} + 10^{n} = (k + 5^{n}) \cdot 2^{n}, a_{n} + 2 \cdot 10^{n} = (k + 2 \cdot 5^{n}) \cdot 2^{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 \geq 7$ 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 + \dots + n$ można zamienić niektóre ze znaków $+$ na $-$ w taki sposób, by jego wartość była równa $0$ lub $1.$

Wskazówka

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 \geq 2$ istnieje wielościan wypukły, którego ścianami są: jeden kwadrat i $2 n$ trójkątów rozwartokątnych.

Wskazówka

3. Dane są wektory ${\vec{v}}_{1}, {\vec{v}}_{2}, {\vec{v}}_{3}, \dots,$ każdy o długości $1.$ Udowodnić, że istnieją liczby $ε_{1}, ε_{2}, ε_{3}, \dots$ ze zbioru ${- 1, 1}$ o tej własności, że dla każdego całkowitego dodatniego $n$ zachodzi nierówność $| ε_{1} {\vec{v}}_{1} + ε_{2} {\vec{v}}_{2} + \dots + ε_{n} {\vec{v}}_{n} | \leq \sqrt{n} .$

Wskazówka

Niech ${\vec{u}}_{n} = ε_{1} {\vec{v}}_{1} + ε_{2} {\vec{v}}_{2} + \dots + ε_{n} {\vec{v}}_{n} .$ Liczbę $ε_{n + 1}$ wybieramy w taki sposób, by kąt pomiędzy wektorami ${\vec{u}}_{n}$ i $ε_{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).

Wskazówka

Załóżmy, że mamy ustalone wyrazy $a_{1}, a_{2}, \dots, a_{2 n} .$ Niech $a_{2 n + 2}$ będzie najmniejszą liczbą całkowitą dodatnią, która jeszcze nie pojawiła się w ciągu, następnie $a_{2 n + 1}$ – dowolną wspólną wielokrotnością $a_{2 n}$ i $a_{2 n + 2},$ różną od $a_{1}, a_{2}, \dots, a_{2 n}$ oraz $a_{2 n + 2} .$

5. Udowodnić, że dla każdej liczby naturalnej $n \geq 3$ 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).

Wskazówka

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 k A^{'}$ i $B \cup k B^{'}$ również je spełniają ( $k X$ 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 \geq 2$ 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ść $NWD (a, b) = | a - b |$ (XIV WLM).

Wskazówka

Mając zbiór ${a_{1}, \dots, a_{n}}$ spełniający zadane warunki, tworzymy zbiór ${b_{1}, \dots, b_{n}, b_{n + 1}}$ następująco: $b_{j} = a_{j} + a_{1} a_{2} \dots a_{n}$ dla $j = 1, 2, \dots, n$ oraz $b_{n + 1} = a_{1} a_{2} \dots a_{n} .$

7. Udowodnić, że dla $n \geq 12$ istnieje permutacja $(a_{1}, a_{2}, \dots, a_{n})$ ciągu $(1, 2, \dots, n)$ o następującej własności: $a_{k} + k$ jest kwadratem liczby naturalnej dla każdego $k \in {1, 2, \dots, n} .$

Wskazówka

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}, \dots, a_{n_{1}})$ dla liczby $n_{1}$ oraz $a_{k} = a^{2} - k$ dla $n_{1} < k \leq 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 \geq n - 2 \sqrt{2 n}$ (dlaczego?), co jest większe od $11$ dla $n \geq 26.$
Pozostaje uzasadnić twierdzenie dla liczb od 12 do 25.