XXXVII OM - I - Zadanie 9

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

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

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

\[<br />
(2) \qquad N=q(n+1)+r;\   q \geq 0,\ 0 \leq r < n+1.<br />
\]

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

\[<br />
q = \sum_{i=1}^k d_i;\    k \leq n,\     d_i | n!, \    d_1> \ldots > d_k.<br />
\]

Stąd wobec (2)

\[<br />
N = \sum_{i=1}^k d_i(n+1)+r.<br />
\]

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

Komentarze

Dodaj nową odpowiedź