- ベストアンサー
問題の意味を教えてください
こんばんは、質問させていただきます。2003年度国際数学オリンピックA1問題を見ていたのですが、質問の意味がいまいちよくわかりません。 答えを見ても質問自体が何を問うているのか、教えていただけると有り難いです。 2003年度国際数学オリンピックA1問題 http://www.kalva.demon.co.uk/imo/isoln/isoln031.html
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
だいぶ意訳と補足をしました 問題 Sは1から1,000,000までの整数からなる集合である． Sの部分集合で要素数が101である任意のものをAとする． このとき，Aに対して 以下の条件を満たす異なる100個のSの要素 x_{1}，・・・，x_{100}が存在することを示せ 条件：100個の集合 {a + x_{i} | a は Aの要素} の任意の二つをとっても， それらには共通の要素が存在しない 解： k個の異なるSの要素 x_1, x_2, ... , x_k がとれたとする x_i + a_m - a_n (i=1,2,...,k, A={a_1,a_2,...,a_{101}}として m，nは1から101までの整数で相異なる) の形で表される整数には k・101・100個の値がある ＃Aから異なる2個を取り出すのに101・100通り ＃これが各iについてあるからk・101・100通り したがって，次のx_{k+1}はこれら k・101・100個の値をとることはできない ＃もし，x_{k+1}=x_i+a_m-a_nとなったら ＃x_{k+1}+a_n = x_i + a_mとなって ＃x_{k+1}+Aとx_i+Aに共通部分ができてしまう また，x_{k+1}は当然，それまでのx_1,...,x_kの k個の値もとることができない したがって，x_{k+1} は k・101・100 + k 個の値をとることができない ＃逆に言えば，これら以外の値ならなんでもOK ＃というのがこの問題の肝です さて，ここで 99·101·100 + 99 = 10^6 - 1 である． したがって 99個まで条件を満たすようなx_iをとることができれば 条件を満たすSの残りは一個しかない したがって，100とることができる ＃ここでわかるのは100個がぎりぎりであって ＃101個以上のこのようなx_iをとることはできない ＃ということです 蛇足： 分かりにくいですが，一種の帰納法です いきなり最後で99個とれたことになってますが k=1だと1・101・100は1,000,000より小さいので 条件を満たすようなx_1，x_2はとれます これを順番にやっていくのですが k個のときk・101・100が1,000,000未満でさえあれば k+1番目x_{k+1}は確保できます それで99個のときを計算すると もう残り一個しかないので それをx_{100}として終わりということです 。。。きわめてエレガントというか さすがIMOです
お礼
とてもよくわかり、とても役に立ちました。 細かい説明本当にありがとうございました。この場を借りて御礼申し上げます。