パズル万華鏡

面白いパズルの紹介と解説をします。

部屋割論法の理解・整数問題(1)・考察

 部屋割論法の理解・整数問題(1)・考察を示します。

 

考察

 n個の自然数がある。これらの中から2つの自然数を適当に選べば、
その差が n-1 で割り切れるような2つの数が必ずある。

 どんな自然数でもn-1で割ると、余りは0からn-2までのどれかになる。

余りについて、n-1個の部屋を用意し、n個の自然数をn-1で割った余りにしたがって、このn-1個の部屋に入れる。

 部屋割論法により、どれか2つの自然数は同じ部屋にはいることになる。

ところで、同じ部屋の2個の数の差はn-1で割り切れるので、差がn-1で割り切れるような2個の数があることになる。以上より、命題が証明された。

f:id:isemba:20190701164145j:plain