16. W jednym rzędzie ustawiono n słupków monet tak, że między każdymi dwoma słupkami tej samej wysokości znajduje się co najmniej jeden słupek wyższy. Najwyższy słupek zawiera k monet. Dla danej liczby k obliczyć największą możliwą wartość n.

Rozwiązanie (autor: Aleksander Jankowski). Największą możliwą wartość n dla danej liczby k oznaczać będziemy przez H(k). Oczywiście H(k) = 1 (dostawienie drugiego słupka narzuca istnienie słupka wyższego od

jednomonetowego, sprzeczność).

Dowiedziemy, że H(k) 2^{k} − 1, dla każdego k ∈ ℕ, przez indukcję po k.

1. Dla k = 1, H(k) = 1 2^{1} − 1.

2. Załóżmy, że dla pewnego k ∈ ℕ, H(k) 2^{k} − 1. Załóżmy ponadto, iż mamy pewien układ m słupków, z których najwyższy zawiera k + 1 monet i gdzie m jest największe z możliwych dla ustalonego k + 1. Oczywiście m jest skończone, m = H(k + 1).

Oczywiście jest tam co najmniej \frac{m+1}{2} słupków o wysokości 1 monety, znajdujących się na krańcach układu i pomiędzy każdymi dwoma sąsiadującymi słupkami o wysokości nie mniejszej od 2. (Gdyby ich tam nie było: można je dostawiać bez szkody dla założeń zadania, co powoduje sprzeczność z założeniem o największości m).

Obniżmy wszystkie słupki o 1 monetę: powstały układ ma co najwyżej H(k) słupków.

H(k + 1) − \frac{H(k + 1) + 1}{2}  H(k)
\frac{H(k + 1) − 1}{2} H(k)
H(k + 1) 2H(k) + 1 2(2^{k} − 1) + 1 = 2^{k+1} − 1.

Twierdzę, że H(k) = 2^{k} − 1. Pokażę, że układ o liczbie słupków H(k) jest konstruowalny.

1. Dla k = 1, H(k) = 1 = 2^{1} − 1.

2. Rozważmy układ H(k) słupków, gdzie najwyższy ma wysokość k. Podwyższmy każdy słupek o 1 monetę, a następnie między każde dwa słupki postawmy słupek jednomonetowy. Otrzymaliśmy układ 2H(k) + 1 = 2(2^{k} − 1) + 1 = 2^{k+1} − 1 słupków, z których najwyższy ma wysokość k + 1, spełniający warunki zadania. Stąd i z poprzednich obserwacji płynie wniosek iż H(k) = 2^{k} − 1, c.n.o.

26. Ile jest podzbiorów zbioru {1, 2, …, n} takich, które nie zawierają dwóch kolejnych liczb całkowitych?

Rozwiązanie (autor: Aleksander Jankowski). Przez F (n) będziemy oznaczać odpowiedź na pytanie zadania dla ustalonego n. Obliczmy najpierw F (1) i F (2). Spośród podzbiorów zbioru {1} tylko ∅ i {1}, a spośród

podzbiorów zbioru {1, 2} tylko ∅, {1} i {2} spełniają warunki zadania. Stąd F (1) = 2 i F (2) = 3.

Rozpatrzmy F (n) dla dowolnego n ∈ ℕ. Ze zbioru {1, 2, …, n} można wybrać podzbiory należące do jednej z poniższych grup:

(a) podzbiory zbioru {1, 2, …, n − 1} spełniające warunki zadania

(b) podzbiory zbioru {1, 2, …, n − 2} spełniające warunki zadania rozszerzone o element n. Jako iż należy do nich element n, nie może się tam znaleźć element n − 1.

Prowadzi to do wniosku, iż F (n) = F (n − 1) + F (n − 2). Jeśli n-ty element ciągu Fibonacciego oznaczymy przez Fib(n), to F (n) = Fib(n + 2).

Tymaczasem Fib(n) = \frac{ϕ^{n} −ϕ^{−n}}{ϕ−ϕ^{−1}} , gdzie ϕ = \frac{1+\sqrt{5}}{2} , więc F (n) = \frac{ϕ^{n+2} −ϕ^{−n−2}}{ϕ−ϕ^{−1}} . Wzór na Fib(n) można bardzo łatwo dowieść indukcyjnie.

27. Rozstrzygnij, czy istnieje funkcja f : ℝ → ℝ nieposiadająca punktów stałych i taka, że dla każdego x ∈ ℝ zachodzi f(f(f(f(f(x))))) = x.

Rozwiązanie (autor: Aleksander Jankowski). Twierdzę, ze szukaną funkcją może być na przykład

f(x) = \{ \begin{matrix}x + 4 & 5 | ⌊x⌋ \\ x − 1 & 5 ∤ ⌊x⌋ \end{matrix}

Funkcja ta nie ma punktów stałych. Rozpatrzmy pięć przypadków.

1. ⌊x⌋ ≡ 0 (mod 5) f(f(f(f(f(x))))) = f(f(f(f(x + 4)))) = x + 4 − 1 − 1 − 1 − 1 = x

2. ⌊x⌋ ≡ 1 (mod 5) f(f(f(f(f(x))))) = f(f(f(x − 1 + 4))) = x + 3 − 1 − 1 − 1 = x

3. ⌊x⌋ ≡ 2 (mod 5) f(f(f(f(f(x))))) = f(f(x − 1 − 1 + 4)) = x + 2 − 1 − 1 = x

4. ⌊x⌋ ≡ 3 (mod 5) f(f(f(f(f(x))))) = f(x − 1 − 1 − 1 + 4) = x + 1 − 1 = x

5. ⌊x⌋ ≡ 4 (mod 5) f(f(f(f(f(x))))) = x − 1 − 1 − 1 − 1 + 4 = x Funkcja ta spełnia warunki zadania.

34. Niech △ ABC będzie trójkątem równobocznym, a P dowolnym punktem leżącym na okręgu opisanym na nim, na łuku BC niezawierającym A. Udowodnij, że BP + CP = AP.

Rozwiązanie (autor: Aleksander Jankowski). Z twierdzenia Ptolemeusza, AC · BP + AB · CP = BC · AP. Jako iż AC = AB = BC, BP + CP = AP, c.n.d.

412. Niech m i n będą liczbami całkowitymi dodatnimi takimi, że m n. Niech zbiór A = {a_{1}, a_{2}, …, a_{m}} będzie dowolnym podzbiorem zbioru {1, 2, …, n}, spełniającym następujący warunek: jeśli dla pewnych 1 i j n zachodzi a_{i} + a_{j} n, to a_{i} + a_{j} ∈ A. Udowodnij, że

\frac{a_{1} + a_{2} + … + a_{m}}{m} \frac{n + 1}{2} .

Rozwiązanie (autor: Aleksander Jankowski).

Bez szkody dla ogólności zadania, niech ciąg m-elementowy (a_{i}) będzie rosnący.

Dowiedziemy wpierw, iż dla każdego k ∈ ℕ, k m, a_{m−k+1} + a_{k} n + 1.

Przypuśćmy, wbrew tezie, iż a_{m−k+1} + a_{k} n. Wówczas a_{m−k+1} + a_{i} n dla każdego naturalnego i k, jako iż ciąg (a_{i}) jest rosnący.

Rozpatrzmy zbiór P = {a_{m−k+1} + a_{1}, a_{m−k+1} + a_{2}, …, a_{m−k+1} + a_{k}} i zbiór Q = {a_{m−1+1} , a_{m−2+1} , …, a_{m−(k−1)+1} }; dla k = 0, Q = ∅. Na mocy monotoniczności ciągu (a_{i}) elementy zbioru Q są jedynymi w zbiorze A większymi od a_{m−k+1} . Na mocy założeń zadania oraz naszego przypuszczenia P ⊆ A. Wszystkie elementy zbioru P są większe od a_{m−k+1} , zatem P ⊆ Q. Niestety jednak zbiór P jest k-elementowy, a zbiór Q (k − 1)- elementowy, sprzeczność.

Gdy 2 | m,

\frac{a_{1} + a_{2} + ⋯+ a_{m}}{m} \frac{\frac{m}{2}(n + 1)}{m} = \frac{n + 1}{2} .

Gdy 2 ∤ m, zauważmy iż

a_{m− \frac{m+1}{2} +1} + a_{\frac{m+1}{2}} = 2a_{\frac{m+1}{2}} n + 1,

więc a_{\frac{m+1}{2}} \frac{m+1}{2} . Wówczas

\frac{a_{1} + a_{2} + ⋯+ a_{m}}{m} \frac{\frac{m−1}{2} (n + 1) + \frac{n+1}{2}}{m} = \frac{(m − 1)(n + 1) + n + 1}{2m} = \frac{m(n + 1)}{2m} = \frac{n + 1}{2} ,

c.n.d.

66. Udowodnij, że każdy wielościan wypukły ma ścianę trójkątną lub kąt trójścienny.

Rozwiązanie (autor: Aleksander Jankowski). Przypuśćmy, że istnieje taki wielościan wypukły, który nie ma ścian trójkątnych ani kątów

trójściennych.

Wówczas jego ściany są co najmniej czworokątne, przy czym każda krawędź należy do dwóch ścian:

2K 4S  gdzie S – liczba ścian
K 2S  (1)

Ponadto z każdego wierzchołka wychodzą co najmniej cztery krawędzie, przy czym każda krawędź łączy dwa wierzchołki:

2K 4W  gdzie W, K – odpowiednio liczba wierzchołków i krawędzi
K 2W  (2)

Podstawiając (1) do wzoru Eulera otrzymujemy

W + S = K + 2 2S + 2
W S + 2
W − 2 S  (3)

Podstawiając (2) do wzoru Eulera otrzymujemy

W + S = K + 2 2W + 2
S W + 2  (4)

(3) i (4) po zestawieniu dają oczywistą bzdurę:

W − 2 S W + 2
−2 +2

Sprzeczność.

67. Udowodnij, że dla dowolnych liczb rzeczywistych dodatnich a, b, c zachodzi nierówność:

4abc − a^{4} − b^{4} − c^{4} 1.

Rozwiązanie (autor: Aleksander Jankowski). Zastosujmy nierówność Cauchy’ego o średnich do liczb 1^{4}, a^{4}, b^{4}, c^{4}:

\sqrt[4]{1^{4} · a^{4} · b^{4} · c^{4}} \frac{1^{4} + a^{4} + b^{4} + c^{4}}{4}
abc \frac{1 + a^{4} + b^{4} + c^{4}}{4}
4abc − a^{4} − b^{4} − c^{4} 1, co należało dowieść.

68. W pewnym języku są tylko dwie litery: A i B. Słowa z tego języka spełniają następujące warunki:

(a) Jedynym słowem o długości 1 jest A.

(b) Dowolna grupa liter X_{1}X_{2} …X_{n}X_{n+1} (gdzie X_{i} ∈ {A, B} dla i = 1, 2, …, n, n + 1) tworzy słowo długości n + 1, gdy zawiera choć jedną literę A i przy tym nie jest postaci X_{1}X_{2} …X_{n}A, gdzie X_{1}X_{2} …X_{n} jest słowem długości n.

Znajdź jawny wzór na liczbę słów długości n.

Rozwiązanie (autor: Aleksander Jankowski). Twierdzę, że liczba słów o długości n wyraża się wzorem W (n) = \frac{2^{n+1} −2+n mod 2}{3} . Dowiodę

tego przez indukcję względem n.

1. Dla n = 1, W (n) = \frac{2^{2}−2+1}{3} = \frac{3}{3} = 1, co jest zgodne z założeniami zadania.

2. Załóżmy, że dla pewnego n ∈ ℕ, W (n) = \frac{2^{n+1} −2+n mod 2}{3} .

Zauważmy, że słowem o długości n + 1 może być każdy (n + 1)-elementowy ciąg liter A i B, który:

(a) nie jest ciągiem n + 1 liter B,

(b) nie jest jednym z W (n) słów n-elementowych rozszerzonych o literę A na końcu.

Stąd W (n+1) = 2^{n+1} −1−W (n) = 2^{n+1} −1− \frac{2^{n+1} −2+n mod 2}{3} = \frac{3·2^{n+1} −3−2^{n+1} +2−n mod 2}{3} = \frac{2·2^{n+1} −1−n mod 2}{3} = \frac{2^{(n+1)+1} −1−n mod 2}{3} .

Zauważmy teraz, że gdy 2 | n, to 2 ∤ n+1 i W (n+1) = \frac{2^{(n+1)+1} −1−0}{3} = \frac{2^{(n+1)+1} −2+(n+1) mod 2}{3} , a gdy 2 ∤ n, to 2 | n + 1 i W (n + 1) = \frac{2^{(n+1)+1} −1−1}{3} = \frac{2^{(n+1)+1} −2+(n+1) mod 2}{3} .

Uzyskaliśmy zatem W (n + 1) = \frac{2^{(n+1)+1} −2+(n+1) mod 2}{3} , co kończy dowód.

98. Udowodnij, że dla dowolnej liczby całkowitej nieujemnej n prawdziwa jest następująca tożsamość:

∑_{k=m}^{n} k\binom{k − 1}{m − 1} = m\binom{n + 1}{m + 1} .

Rozwiązanie (autor: Aleksander Jankowski). Aby wartość wyrażenia podanego w treści zadania była określona, potrzeba aby n m. Tezy dowiedziemy przez indukcję względem n.

1. Dla n = m, m\binom{m−1}{m−1} = m\binom{n−1}{m−1} gdyż \binom{a}{a} = 1.

2. Załóżmy, że dla pewnego n ∈ ℕ, n m, teza zachodzi. Dowiedziemy jej dla n + 1.

Zauważmy, że

m\binom{n + 1}{m + 1} + (n + 1)\binom{n}{m − 1} = \frac{m(n + 1)!}{(m + 1)!(n − m)!} + \frac{(n + 1)n!}{(m − 1)!(n − m + 1)!} =

= \frac{m(n + 1)!}{(m + 1)!(n − m)!} + \frac{m(n + 1)!}{m!(n − m + 1)!} =

= \frac{m(n + 1)!}{(m + 1)!(n − m + 1)!} (n − m + 1) + \frac{m(n + 1)!}{(m + 1)!(n − m + 1)!} (m + 1) =

= \frac{m(n + 1)!}{(m + 1)!(n − m + 1)!} (n + 2) = \frac{m(n + 2)!}{(m + 1)!(n − m + 1)!} = m\binom{n + 2}{m + 1} .

Z założenia indukcyjnego

∑_{k=m}^{n} k\binom{k − 1}{m − 1} = m\binom{n + 1}{m + 1} ,

z naszej ostatniej obserwacji

∑_{k=m}^{n+1} k\binom{k − 1}{m − 1} = m\binom{(n + 1) + 1}{m + 1} ,

co kończy dowód.

911. Znajdź wszystkie różnowartościowe funkcje f : ℝ → ℝ takie, że

f(f(x) + y) = f(x + y) + 1 dla x, y ∈ R.  (1)

Rozwiązanie (autor: Aleksander Jankowski). Niech c = f(0). Podstawiając do (1) x = 0, otrzymujemy

f(c + y) = f(y) + 1
f(y) = f(c + y) − 1.  (2)

Podstawmy (2) do (1):

f(f(x) + y) = f(c + x + y) − 1 + 1
f(f(x) + y) = f(x + y + c).

Z różnowartościowości funkcji f mamy

f(x) + y = x + y + c
f(x) = x + c.  (3)

Podstawmy (3) do (1):

f(x) + y + c = x + y + c + 1
x + c + y + c = x + y + c + 1
c = 1,  (4)

podstawiając (4) do (3) mamy f(x) = x + 1. Sprawdźmy, czy ta funkcja spełnia warunki zadania, przekształcając równoważnie (1):

f(x) + y + 1 = x + y + 1 + 1
x + 1 = x + 1,

co jest prawdą.