n進法と自然数の分割

自作問題です．解答は下部に載せました．

問題

$n$ を $2$ 以上の自然数， $m$ を自然数とする． $n^m$ より小さい自然数は

$n^0 , n^1 , \ldots n^{m-1}$ から同じ数を $n$ 回以上選ばないようにして，適当に選んで足し合わせれば作ることができることを示せ．

解答

$n$ 進法における各桁の位は一桁目から順に $n^0 , n^1 , \ldots$ となっている．そして，各桁には最大で $n - 1$ 個の位の数が入る．

$n^m$ より小さい自然数は， $n$ 進法においては $m$ 桁以下で作ることができる．これは， $n^m$ より小さい自然数は， $n^0 , n^1 , \ldots n^{m-1}$ から同じ数を $n$ 回以上選ばないようにして，適当に選んで足し合わせれば作ることができるということと同値である．