こんにちは！カサニマロです！
本ブログの後半では、鳩の巣原理を用いた難問にもチャレンジしてみようと思います。
今日の問題はこちら！
任意の自然数がn+1個ある。その中から差がnの倍数になるような２つの数が存在するか？
例えば、n = 9なら、１０個自然数があって、その１０個から数字を２つ選んで、その差が９の倍数になるかどうか
答え
答え：必ず存在する。
【解説】
自然数をnで割ったときの余りは0,1,,,,,,n-1 のnパターン。
数字がn+1個あれば、nで割った時の余りにカブりが必ず出る。（終了）
鳩の巣原理
以下、ムズめだし読まなくてもいいです。（色々ササッと書いています）
p羽の鳩がいてh個の巣がある時、少なくとも１つの巣には少なくとも[p/h]羽の鳩がいる。（[π]=4）
10羽、巣４個→[10/4]=3→どっかの巣に３匹以上いる
10×10のチェス盤上に41個のルーク（前後左右ならどこまでも進めるやつ）が置かれている。お互いに1回の移動で届かないルークが5個は必ず存在している。【上級】
解説
わざわざ「p羽の鳩がいてh個の巣がある時、少なくとも１つの巣には少なくとも[p/h]羽の鳩がいる」を紹介したので使うだろう。
列と行があるが、列だけ考えてみる。
10列に注目する。
[41/10]=5
どこかの列には5個以上ルークがある。
その列を除外して考えると、最大10個のルークがあるので10個除外してみる。
今、9列に31個のルークがある。
[31/9]=4
どこかの列には4個以上ルークがある。
その列を除外して考えると、最大10個のルークがあるので10個除外してみる。
今、8列に21個のルークがある。
[21/8]=3
これを続けると、どっかの列に5個以上ルークある。別のどっかの列に4個以上ルークある。どっかの列に３個以上ルークある、、、となる。
step1. 「1個以上ルーク」の列から1つルークを選ぶ。
step2. 「2個以上ルーク」の列から1つルークを選ぶ。（step1のルークと”行”が被らないルークを選べる）
……..
step5.
以上より、お互いに１回の移動で届かないルークが5個ある。（終了）
正の整数
n個の整数がある時、nの倍数であるような整数があるか、いくつかの和がnの倍数であることを示そう。【上級】
メタいけど鳩の巣だろう。n=10なら、1,11,21,,,,91なら10の倍数ないけど、全部足したら10の倍数。こんな感じで、nの倍数を避けたら、和でn倍が作れるんだろうな。ワンチャン帰納法？
「n倍数を避けて、和がnの倍数にならないようにn個整数を選ぼうとしてムリ」って背理法でいける？
解説
「n倍数を避けて、和がnの倍数にならないようにn個整数を選ぼうとしてムリ」っていう背理法でやってみる。
n個整数を選ぶとき、mod nにすると、0,1,2,,,,n-1のn通りのどれかになる。
0以外のn-1通りからn個選んでみる。
1,2,3,,,,,,n-1の中から１つ数を選ぶ。
次に1,2,3,,,,,,n-1の中から１つ選んで、和をaとするとa (mod n)(aは1,2,3,,,,,,nのどれかになる)は元の２つと異なる。（変化しないならば片方がn）
また次に1,2,3,,,,,n-1から１つ選んでaとの和をbとする。b (mod n)(bは1,2,3,,,,,,nのどれかになる)はaと異なる。
このように、
最初は1,2,3,,,,,,n-1の中どれかで、その後1,2,3,,,,,,,,nのどれかに毎回異なる数字にn-1回変化するので、１回はnの倍数になる。（終了）
コメント