XIX OM - III - Zadanie 4

Dana jest liczba naturalna $ n>2 $. Podać taki zbiór $ n $ liczb naturalnych $ a_1, a_2, \ldots, a_n $, żeby w zbiorze sum

\[<br />
a_i + a_j \quad (i = 1,2, \ldots,n, \quad j= 1,2, \ldots,n, \; i\neq j)<br />
\]

było możliwie najmniej liczb różnych oraz taki zbiór $ n $ liczb naturalnych $ b_1, b_2, \ldots, b_n $, żeby w zbiorze sum

\[<br />
b_i + b_j \quad (i = 1,2, \ldots,n, \quad j= 1,2, \ldots,n, \; i\neq j)<br />
\]

było możliwie najwięcej liczb różnych.

Rozwiązanie

Gdy $ Z $ jest skończonym zbiorem liczb, umówimy się oznaczać symbolem $ l(Z) $ liczbę różnych wartości, jakie mają sumy dwóch liczb należących do $ Z $.

1) Niech $ A $ będzie zbiorem $ n > 2 $ liczb naturalnych $ a_i $ ($ i = 1,2,\ldots, n $) tak oznaczonych, że

\[<br />
(1) \qquad  a_1 < a_2 < \ldots < a_n.<br />
\]

Ponieważ

\[<br />
(2) \qquad<br />
a_1 + a_2 < a_1 + a_3< \ldots  < a_1 + a_n < a_2 + a_n < a_3 + a_n < \ldots < a_{n-1} + a_n,<br />
\]

więc w zbiorze sum $ a_i + a_j $ jest co najmniej $ 2n - 3 $ liczb różnych, tj. $ l(A) \geq 2n - 3 $.

Jeśli zatem utworzymy taki zbiór $ A $, że $ l(A) = 2n - 3 $, będzie to zbiór jakiego poszukujemy. Trzeba w tym celu dobrać liczby $ a_1, a_2, \ldots, a_n $ w taki sposób, żeby każda suma $ a_i + a_j $ była równa którejś z sum występujących w (2), tzn. jednej z sum $ a_1 + a_j $ ($ j = 2,3, \ldots,n $), lub jednej z sum $ a_i + a_n $ ($ i = 2,3,\ldots, (n-1) $).

Wykażemy, że przypadek taki zachodzi, gdy liczby zbioru $ A $ tworzą postęp arytmetyczny.

Załóżmy, że

\[<br />
a_2 - a_1 = a_3 - a_2 = \ldots = a_n - a_{n-1} = d > 0.<br />
\]

Według znanych wzorów

\[<br />
(3) \qquad  a_k = a_1 + (k-1)d= a_n- (n-k)d \textrm{ dla } k = 1,2 \ldots, n.<br />
\]

Rozpatrzmy sumę $ a_i + a_j $, gdzie $ 1 \leq i < j \leq n $.

Gdy $ i + j \leq n $, wtedy na mocy (3)

\[<br />
(4) \qquad  a_i + a_j = a_1 + (i - 1) d + a_1 + (j- 1)d = a_1 + [a_1 + (i+j+2)d] = a_1 + a_{i+j-1};<br />
\]

gdy zaś $ i + j>n $, wtedy według (3)

\[<br />
(5) \qquad  a_i + a_j = a_1 + (i - 1)d   + a_n - (n - j) d = a_n +  [a_1 + (i + j  - n - 1)d] = a_{i+j-n} + a_n.<br />
\]

Z (4) i (5) wynika, że każda suma $ a_i + a_j $ jest równa jednej z sum (2), zatem $ l(A) = 2n - 3 $, c.n.d.

b) Zbiór liczb naturalnych $ B = \{ b_1, b_2, \ldots , b_n\} $ o możliwie największej liczbie $ l(B) $ różnych wartości sum $ b_i + b_j $ ($ i,j= 1,2,\ldots, n $, $ i \ne j $), uzyskamy wtedy, gdy wszystkie sumy $ b_i + b_j $, będą różnymi liczbami; wówczas $ l (B) = \frac{1}{2} n (n - 1) $.

Zbiorem takim jest na przykład zbiór wyrazów postępu geometrycznego

\[<br />
(6) \qquad  1, q, q^2, \ldots, q^{n-1},<br />
\]

którego iloraz $ q $ jest liczbą naturalną większą od $ 1 $.

Przypuśćmy bowiem, że dla pewnych wyrazów ciągu (6) zachodzi równość

\[<br />
(7) \qquad  q^i + q^j= g^k + q^l, \textrm{ gdzie } i < j,\ k < l;<br />
\]

wtedy

\[<br />
(8) \qquad  q^i (1 + q^{j-i}) = q^k (1 + q^{l-k}).<br />
\]

Ponieważ liczby $ 1 + q^{j-i} $ i $ 1 + q^{l-k} $ są pierwsze względem $ q $, więc z równości (8) wynika, że $ q^k $ jest podzielne przez $ q^i $, a $ q^i $ przez $ q^k $. Zatem $ k = i $, a wobec (7) także $ l = j $, tzn. równość (7) nie może zachodzić, gdy $ q^i $, $ q^j $ nie są tymi samymi wyrazami ciągu (6), co $ q^k $, $ q^l $.

Uwaga 1. Niech $ A $ będzie zbiorem liczb $ a_1 < a_2< \ldots < a_n $ ($ n > 2 $), dla którego liczba $ l (A) $ różnych wartości sum $ a_i + a_j $ wynosi $ 2n - 3 $, czyli jest możliwie najmniejsza. Postawimy pytanie, czy ciąg $ a_1, a_2, \ldots, a_n $ musi być postępem arytmetycznym?

Łatwo zauważyć, że tak nie jest, gdy $ n = 3 $, ani gdy $ n = 4 $. Z nierówności $ a_1 < a_2 < a_3 $ wynika bowiem, że $ a_1 + a_2 < a_1 + a_3 < a_2 + a_3 $ więc dla zbioru $ A $ trzech różnych liczb zawsze $ l(A) = 3 $. Aby zaś dla zbioru $ A $ liczb $ a_1 < a_2< a_3< a_4 $ było $ l(A) = 5 $, trzeba tylko, żeby zachodziła równość $ a_4 - a_3 = a_2 - a_1 $.

Udowodnimy, że gdy $ n \geq 5 $, wtedy każdy zbiór $ A $ złożony z $ n $ liczb, dla którego $ l(A) = 2n - 3 $, jest zbiorem wyrazów postępu arytmetycznego.

Dla $ n = 5 $ teza tego twierdzenia jest prawdziwa. Istotnie, gdy dany jest zbiór $ A $ pięciu liczb

\[<br />
(1) \qquad  a_1 < a_2 < a_3 < a_4 < a_5,<br />
\]

wtedy

\[<br />
(2) \qquad  a_1 + a_2 < a_1 + a_3 < a_1 + a_4 < a_1 + a_5 < a_2 + a_5 < a_3 + a_5 < a_4 + a_5<br />
\]

i

\[<br />
(3) \qquad  a_2 + a_3 < a_2 + a_4 < a_3 + a_4,<br />
\]

więc jeśli $ l(A) = 2 \cdot 5 - 3 = 7 $, to każda z sum występujących w (3) musi być równa jednej z siedmiu sum występujących w (2). Ponieważ zaś każda z sum (3) jest większa niż $ a_1 + a_3 $, a mniejsza niż $ a_3 + a_5 $, więc zachodzą równości

\[<br />
a_2 + a_3 = a_1 + a_4, \ a_2 + a_4 = a_1 + a_5, \    a_3 + a_4 = a_2 + a_5,<br />
\]

z których wynika, że

\[<br />
a_2 - a_1 = a_4 - a_3,\ a_2 - a_1 = a_5 - a_4,     a_3 - a_2 = a_5 - a_4,<br />
\]

co oznacza, że ciąg (1) jest postępem arytmetycznym.

Załóżmy, że teza twierdzenia jest prawdziwa dla pewnego $ n \geq 5 $. Niech $ A $ będzie zbiorem liczb

\[<br />
(4) \qquad  a_1 < a_2 < \ldots < a_n < a_{n+1},<br />
\]

dla którego $ l(A) = 2(n + 1) - 3 $.

Weźmy pod uwagę zbiory

\[<br />
A' = \{ a_1, a_2,\ldots,a_n \},<br />
\]
\[<br />
A'' = \{ a_2, a_3,\ldots,a_n, a_{n+1} \}.<br />
\]

Wykażemy, że

\[<br />
l(A') = l(A'') = 2n - 3.<br />
\]

Istotnie, jeśli liczby $ a_i $, $ a_j $ ($ i< j $) zbioru $ A $ należą do zbioru $ A' $, to

\[<br />
a_i + a_j  < a_{n-1} + a_{n+1} < a_n + a_{n + 1},<br />
\]

więc liczba różnych wartości sum $ a_i + a_j $ jest dla zbioru $ A' $ co najmniej o $ 2 $ mniejsza niż dla zbioru $ A $, tj.

\[<br />
l(A') \leq l(A) - 2 = 2n - 3.<br />
\]

Wiemy zaś, że

\[<br />
l(A') \geq 2n - 3.<br />
\]

Zatem $ l(A') = 2n - 3 $.

Podobnie, jeśli liczby $ a_i $, $ a_j $ ($ i < j $) zbioru $ A $ należą do zbioru $ A'' $, to

\[<br />
a_i + a_j > a_1 + a_3 > a_1 + a_2,<br />
\]

skąd wynika, że $ l(A'') \leq l(A) - 2 = 2n - 3 $, a że $ l(A'') \geq 2n - 3 $, więc $ l(A'') = 2n - 3 $.

Na mocy założenia indukcyjnego ciągi $ a_1, a_2, \ldots, a_n $ i $ a_2, a3,\ldots, a_{n+1} $ są postępami arytmetycznymi, a wobec tego ciąg $ a_1, a_2, \ldots, a_n, a_{n+1} $ jest również postępem arytmetycznym, tzn. teza twierdzenia jest prawdziwa dla zbiorów złożonych z $ n + 1 $ liczb. Według zasady indukcji jest ona tedy prawdziwa dla każdego naturalnego $ n \geq 5 $.

Uwaga 2. Przykładów takiego zbioru $ B = \{b_1, b_2,\ldots, b_n \} $, że $ l(B) = \frac{1}{2} n(n-1) $ można podać wiele. Własność tę ma np. zbiór $ n $ kolejnych wyrazów ciągu Fibonacci'ego *), tj. ciągu liczb $ b_n $ określonego wzorami $ b_1 =0 $, $ b_2 = 1 $, a dla każdego $ n > 2 $ $ b_n = b_{n-1}+ b_{n-2} $.

Pierwszymi wyrazami tego ciągu są zatem liczby $ 0, 1, 1, 2, 3, 5, 8,  13, \ldots $.

Dowód, że każda z sum $ b_i + b_j $ jest inną liczbą, łatwo przeprowadzić metodą indukcji.

Komentarze

Dodaj nową odpowiedź