XIX OM - III - Zadanie 4

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

III

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

$ a_i + a_j \quad (i = 1,2, \ldots,n, \quad j= 1,2, \ldots,n, \; i\neq j) $

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

$ b_i + b_j \quad (i = 1,2, \ldots,n, \quad j= 1,2, \ldots,n, \; i\neq j) $

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

$ (1) \qquad a_1 < a_2 < \ldots < a_n. $

Ponieważ

$ (2) \qquad 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, $

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

$ a_2 - a_1 = a_3 - a_2 = \ldots = a_n - a_{n-1} = d > 0. $

Według znanych wzorów

$ (3) \qquad a_k = a_1 + (k-1)d= a_n- (n-k)d \textrm{ dla } k = 1,2 \ldots, n. $

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

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

$ (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}; $

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

$ (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. $

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

$ (6) \qquad 1, q, q^2, \ldots, q^{n-1}, $

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ść

$ (7) \qquad q^i + q^j= g^k + q^l, \textrm{ gdzie } i < j,\ k < l; $

wtedy

$ (8) \qquad q^i (1 + q^{j-i}) = q^k (1 + q^{l-k}). $

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

$ (1) \qquad a_1 < a_2 < a_3 < a_4 < a_5, $

wtedy

$ (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 $

$ (3) \qquad a_2 + a_3 < a_2 + a_4 < a_3 + a_4, $

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

$ a_2 + a_3 = a_1 + a_4, \ a_2 + a_4 = a_1 + a_5, \ a_3 + a_4 = a_2 + a_5, $

z których wynika, że

$ a_2 - a_1 = a_4 - a_3,\ a_2 - a_1 = a_5 - a_4, a_3 - a_2 = a_5 - a_4, $

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

$ (4) \qquad a_1 < a_2 < \ldots < a_n < a_{n+1}, $

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

Weźmy pod uwagę zbiory

$ A' = \{ a_1, a_2,\ldots,a_n \}, $

$ A'' = \{ a_2, a_3,\ldots,a_n, a_{n+1} \}. $

Wykażemy, że

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

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

$ a_i + a_j < a_{n-1} + a_{n+1} < a_n + a_{n + 1}, $

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.

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

Wiemy zaś, że

$ l(A') \geq 2n - 3. $

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

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

$ a_i + a_j > a_1 + a_3 > a_1 + a_2, $

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.