XXXVII OM - I - Zadanie 9

Zawody matematyczne:

XXXVII OM, 1985-1986

Etap:

Dowieść, że każda liczba naturalna mniejsza od $n!$ jest sumą co najwyżej $n$ różnych liczb naturalnych dzielących $n!$ .

Rozwiązanie

Dowód prowadzimy przez indukcję względem $n$ . Dla $n = 1$ twierdzenie jest spełnione ,,w próżni'' (nie ma liczb naturalnych mniejszych od $1!$ ). Ustalmy liczbę naturalną $n$ i załóżmy, że teza twierdzenia jest dla niej prawdziwa. Dowiedziemy tezy dla $n + 1$ .

Weźmy dowolną liczbę naturalną $N < (n + 1)!$ . Mamy wykazać, że liczba $N$ dopuszcza przedstawienie w postaci

$ (1) \qquad N = sum_{i=1}^m D_i;\ m \leq n+1,\ D_i|(n+1)!,\ D_1 > \ldots > D_m. $

Dzieląc $N$ przez $n + 1$ dostajemy iloraz $q$ i resztę $r$ :

$ (2) \qquad N=q(n+1)+r;\ q \geq 0,\ 0 \leq r < n+1. $

Gdy $q = 0$ , wówczas $N = r$ dzieli $(n+1)!$ ; wystarczy więc przyjąć jako (1) przedstawienie z jednym tylko składnikiem, równym $r$ .

Gdy $q > 0$ , to wobec nierówności $N < (n + 1)!$ musi być $q < n!$ . W myśl założenia indukcyjnego liczba $q$ jest sumą postaci

$ q = \sum_{i=1}^k d_i;\ k \leq n,\ d_i | n!, \ d_1> \ldots > d_k. $

Stąd wobec (2)

$ N = \sum_{i=1}^k d_i(n+1)+r. $

Liczby $d_i(n+1)$ są dzielnikami $(n+1)!$ . Jeśli więc $r = 0$ , to otrzymujemy przedstawienie (1) przyjmując $m = k$ , $D_i = d_i (n+1)$ dla $i=1, \ldots, k$ . Jeśli natomiast $r > 0$ , przyjmujemy $m = k+1$ , $D_i=d_i(n + 1)$ dla $i = 1, \ldots, k$ oraz $D_{k+1} = r$ . Nierówności $D_1 > \ldots > D_k$ wynikają z analogicznych nierówności między liczbami $d_i$ . Nierówność $D_k > D_{k+1}$ wyniknie stąd, że $d_k \geq 1$ , a $r < n+1$ .

Zgodnie z zasadą indukcji, twierdzenie jest prawdziwe dla każdej liczby naturalnej $n$ .