ある集合を 9で割った余りで 9個のグループに類別したとき
同じグループ内の数の差は 9の倍数
1つのグループに7個の数が属していると
そのグループ内での2数の差がすべて18以上の9の倍数であるとすると
18*(7-1)=108>100 となるので矛盾⇒ 差が9である2数が存在します。
6*9+1=55 から
55個の数があるとき、9で割った余りで類別すると、必ず7個入るグループができ、そのグループ内に
差が9である2数が存在することになる。
と考えました。(鳩ノ巣原理)
・uchinyanさんのもの Orz〜
1 〜 100 を 9 で割った余りで分類します。
すると,余りが 0,2 〜 8 のグループには 11 個ずつ,余りが 1 のグループには 12 個,に分かれます。
このとき,同じグループから取った二つの差は 9 の倍数になり,異なるグループから取った二つの差は 9 の倍数にはなりません。
そこで,二つの差が 9 になるのは同じグループ内の小さい順に並べたときに隣り合う二つのときだけです。
これより,全く二つの差が 9 にならない最大個数の場合は,同じグループ内から隣り合う二つを抜き出さない場合なので,6 * 9 = 54 個。
これに一つでも加わるとどれかのグループ内に隣り合う二つができるので,必ずそこで二つの差が9 になります。
そこで,必ず二つの差が 9 になることがある最小の個数は,54 +1 = 55 個,になります。
この問題を解くには次で十分な気もします。
二つの差が 9 にならない場合を考えます。
1 に対しては 10 は含まれてはダメ,2 に対しては 11 は含まれてはダメ,...,と考えていくと,
1 〜 9,19 〜 27,37 〜 45,55 〜 63,73 〜 81,91 〜 99
となる場合がどの二つを選んでもその差は 9 にならず,これに抜けているどの数を加えてもそこで差が 9 になる,と分かるので,
必ず二つの差が 9 になることがある最小の個数は,9 * 6 + 1 = 55 個,になります。
もちろん,100 から初めて小さくしていってもよく,この場合は,二つの差が 9 にならない最大の場合は,
100 〜 92,82 〜 74,64 〜 56,46 〜 38,28 〜 20,10 〜 2
後は同じように,必ず二つの差が 9 になることがある最小の個数は,9 * 6+ 1 = 55 個,になります。
これら二つは,最初の解法で,9 で割った余りが 1 のグループで数をどう取るかに対応していますね。
・わたしの...
地道に...最悪の場合を考えましたぁ...^^;
1〜9 のとき...10〜18はX
19〜27...28〜36はX
37〜45...46〜54はX
55〜63...64〜72はX
73〜81...82〜90はX
91〜99...100はX
つまり...9*6=54個までは差が9のものは0
これに他の1個(100以外)を加えたら差が9のものが2ペアできる。
しかし、100と他の数を選んだら...3ペアとなるので...2ペアになる場合は...54+1=55個が最小ね ^^
*わたしゃ、2ペアできるんだと勘違いしてました...^^;...