もう一人のY君

iPhoneアプリのレビューやアップデートレビューなどを書いています. たまに数学の記事も書きます.

もう一人のY君 MENU  MENU

【数学】2017にまつわる問題の解説

170104_00

 既に2日程経ってしまいましたが2chで2017にまつわる数学の問題があったので自分なりにもうちょっと分かりやすく解説したいな…と思います.

 

 

問題

 { \displaystyle 1 } が { \displaystyle n } 個並んだ数 { \displaystyle 111\dots 1 } のうち, { \displaystyle 2017 } で割り切れるものが存在することを示せ.

 (但し { \displaystyle n } は正整数)

 

 

解説

 スレッドでは「鳩の巣原理」を利用した証明が与えられています.

 

[鳩の巣原理]

 { \displaystyle m } 個の箱の中に { \displaystyle n } 個の物を入れるとき, { \displaystyle m\lt n } であるならば { \displaystyle m } 個の箱の少なくとも1つは { \displaystyle 2 } 個以上の物が入っている.

 

 具体的な数字で考えてみれば分かることだと思います.

 これを使ってみましょう.

 

 { \displaystyle 1 } が { \displaystyle n } 個並んだ数を { \displaystyle f(n) } とします, このとき

 

{ \displaystyle f(n) = \sum_{k=1}^n10^{k-1} }

 

であることは直ぐに分かると思います.

 

 また除法の定理から, 任意の整数 { \displaystyle a, b(\neq0) } に対して

 

{ \displaystyle a=bq+r,\quad 0\lt r\leq b }

 

となるような整数の組 { \displaystyle (q, r) } がただ一組存在します.

 上記の通り { \displaystyle a, b } がどのような組あっても余り { \displaystyle r } は { \displaystyle 0,1,2,\dots,b-1 } の, 互いに異なる { \displaystyle b } 種類であることは明らかです.

 

 今回は { \displaystyle b=2017 } に相当するわけですね.

 

 すると例えば { \displaystyle f(1), f(2), f(3),\dots, f(2018) } の2018個の数を考えると, 鳩の巣原理からこの2018個のうち少なくとも2つは2017で割った余りが同じであるということになります.

 

 その2数を { \displaystyle f(s), f(t)\quad (s\lt t) } とでもすると, この2数は余りが同じですから

 

{ \displaystyle f(s) = 2017q'+r' \\ f(t) = 2017q''+r' }

 

となるような整数の組 { \displaystyle (q',r'),\, (q'',r') } がただ一組ずつ取れます.

この2式を辺々引くと

 

{ \displaystyle f(t)-f(s) = 2017(q''-q') }

 

, これは { \displaystyle f(t)-f(s) } が2017で割り切れることを意味します.

 

 更に { \displaystyle f(t)-f(s) } を見てみると

 

{ \displaystyle f(t)-f(s) \\ = \sum_{k=1}^t 10^{k-1} - \sum_{k=1}^s 10^{k-1} \\ = 111\dots11000\dots 0 \quad \left(\text{1がt-s個, 0がs個並ぶ}\right) \\ = f(t-s)\times 10^s }

 

となります.

 つまり { \displaystyle f(t)-f(s) } は { \displaystyle 2017 } で割り切れ, かつ { \displaystyle f(t-s) } と { \displaystyle 10^s } の積で表すことができるということです※1.

 

 { \displaystyle 2017 } は素数ですから, { \displaystyle f(t-s) } か { \displaystyle 10^s } のいづれかで割り切れることになります.

 しかし後者は { \displaystyle 2 } と { \displaystyle 5 } のみを約数とする数ですから { \displaystyle 2017 } で割り切れません.

 よって { \displaystyle f(t-s) } が { \displaystyle 2017 } で割り切れることになります.

 

 { \displaystyle f(t-s) } とは  { \displaystyle f(\,) } の定義から { \displaystyle 1 }{ \displaystyle t-s } 個並ぶ自然数のことですから, これが望む数ということになります. { \displaystyle \quad\square }

 

 

 因みにですが, { \displaystyle f(n) } は連続した数ではありませんから, 例えば { \displaystyle f(1) } と { \displaystyle f(2018) } のそれぞれを { \displaystyle 2017 } で割った余りが同じである保証はありません.

 あくまでもこの2018個のどれか少なくとも2つ…ということが分かるに留まります.

 

 またこの証明から分かることは, このような数 { \displaystyle f(n) } は { \displaystyle n\leq 2017 } の範囲に少なくとも1つある…ということでもありますね.

 

 こういう証明をすぐ思いつくって羨ましいですよね…

 僕は時間かけないといけないくらい退化してしまいました.

 

 

訂正

※1

×:つまり { \displaystyle f(t-s) }

○:つまり { \displaystyle f(t)-f(s) }