JMOで役に立つ？テクニック！
マロ：数学オリンピックまで一か月切ったね！
ミケ：お、本当だ！そういえば自分も数学オリンピックの問題解いてみたくなったんだよね（笑）
マロ：おお、めっちゃいいやん！勉強なんかしてるの？
ミケ：実は最近始めたばかりなんだよね。なんか問題を解くテクニックってないの？
マロ：ん～、ある！じゃあ今回はそれを紹介していこう！
ミケ：やった！
マロ：これから使う文字は基本自然数ね。
整数問題のテクニック
整数問題のテクニックでよく知られてるのが、次の三つ！
倍数、余りに着目する
因数分解をする
文字の範囲を絞る
倍数、余りに着目する
この時によく使うのはmod！
modは余りを求める道具で、次の性質がある！
$${a\equiv b\pmod m ,c\equiv d\pmod m}$$のとき、
$${a\pm c\equiv b\pm d\pmod m}$$(複号同順)
$${ac\equiv bd\pmod m}$$
$${ka\equiv kb\pmod m, \text{gcd}(k,m)=1 \Longrightarrow a\equiv b\pmod m}$$
$${m = dk \Longrightarrow a\equiv b\pmod d}$$
$${d\not=0}$$のとき、$${ad\equiv bd\pmod m \Longleftrightarrow a\equiv b\pmod m}$$
証明は簡単だからやってみると理解が深まるかも？
因数分解をする
高校で習う因数分解の公式は簡単だけどもちろん大事だから覚えてね！
他にちょっとタイプが違う因数分解があって、
$${ab+a+b=(a+1)(b+1)-1}$$
因数分解できてないじゃないか！って思うかもしれないけど、例えば
$${ab+a+b=0}$$の解を求めよ、みたいな問題の時に
$${ab+a+b=0 \rightarrow (a+1)(b+1)=1}$$
こうすれば$${a, b}$$が簡単に求まる！
文字の範囲を絞る
これは問題ごとに見抜いて説かなきゃいけないんだけど、例えば、
$${\sqrt{X}}$$のとき、$${X\geqq0}$$
$${\text{log}_ab}$$のとき、$${(0 < a < 1}$$または$${a > 1), b > 0}$$
$${\frac{1}{X}}$$のとき、$${X\not=0}$$
みたいなのがあったらとりあえずこの範囲は確認した方がいい！
組み合わせのテクニック
漸化式
例えば次みたいな問題。
どれも3の非負整数乗であるいくつかの整数の和として100を表す方法は何通りあるか。ただし、和をとる順番のみが異なるものは同じ表し方とみなす。
どれも3の非負整数乗であるいくつかの整数の和として自然数ｎを表す方法を$${A_n}$$通りとすると、
$${A_{3n+2}=A_{3n+1} = A_{3n}}$$
これは、3の自然数乗だけだとどんな風に足しても3の倍数にしかならないから$${1(=3^0)}$$を足すしかないことからわかる！
あとは$${A_{3n}}$$を崩していけばいいね！
そして、$${A_{3n}}$$を次のように場合分けする。
(i)$${1(=3^0)}$$を含むとき
$${1+\cdots}$$っていう状態だから結局$${(1+1+1)+\cdots}$$ってことになるからこのときは$${A_{3n-3}=A_{3(n-1)}}$$通りになる。
(ii)$${1(=3^0)}$$を含まないとき
全て3の倍数っていうことだからこれは$${A_{n}}$$通りになるときの組み合わせを全部3倍すればこの場合分けの状況になる。
これより、$${A_{3n}=A_{3(n-1)}+A_{n}}$$になるから、あとは地道に計算すれば解ける！ちなみにこの問題の答えは402！
こんな感じで、１つ前の状態から分岐するときに漸化式が使えるときがある！
1つのものとみなす
例えば次みたいな問題。
11個のオセロの石が１列に黒、白、黒、白、…、白、黒のように並んでいる。
この時、次のように意思を裏返すことを何回か行う。
表の色が同じで隣り合わない2つの石であって、その間にはもう一方の色の石しかないものを選ぶ。そしてその間の石を全て同時に裏返す。
このとき、すべての石が黒になるまでの裏返し方は何通りあるか。
このとき、１列の途中にある黒、白、黒のように並んでるものを見て間にある白をひっくり返して黒にすると、この３つのオセロの石は黒、黒、黒になった。
さらに視野を広げると、この部分は白、黒、黒、黒、白になってるから間にある３つの黒をひっくり返して白にすると、この５つのオセロの石は白、白、白、白、白になる。
ここで気づくことは、白、黒、黒、黒、白の間にある３つの黒を１つの
黒ってみなしても操作に本質的な違いはないよね。
黒、白、黒を黒、黒、黒にした時点で１つの黒とみなせばこの問題は11個のオセロの石から9個のオセロの石の問題に変わった！
こんな感じで解いていくとこの問題は945通りになる！
こんな感じで問題を解く過程に影響がない範囲で単純化していけば解きやすくなることがある！
市松模様に塗る
正方形のマス目が敷き詰められた何×何の長方形領域にL字とかの形を敷き詰めるとき、最大何個入るかみたいな問題がたまにあるよね。
この時は長方形領域を市松模様に塗ると解きやすくなる！
例えば、5×7の領域にL字のブロックを敷き詰める問題だと、次の図みたいに市松模様に塗って、
L字は、
すると、長方形領域は黒が18個、白が17個あって、L字は１つあたり黒2個、白2個を使うね。
どんな敷き詰め方かは知らないけどL字を8個敷き詰めると黒16個、白16個使われて残りが黒2個、白1個になるね。
この残りの分だとL字は敷き詰めれないからこの長方形領域には多くても8個のL字が敷き詰められる！
実際、
こんな感じで敷き詰めれば8個のL字が敷き詰められたから答えは8個！
まとめ
今回紹介したのは、
整数問題のテクニック
倍数、余りに注目する
因数分解する
文字の範囲を絞る
組み合わせのテクニック
漸化式
1つのものとみなす
市松模様に塗る
だよ！これらは基本的なテクニックだから難しい問題だとどんな感じに潜んでるかを見極める必要がある！
たくさん問題を解いて自分なりの感覚をつかめるかも？！
最後に
マロ：どうだった？
ミケ：ん～、やっぱり整数問題はmodが大事なんだね！
ミケ：組み合わせの漸化式は難しい問題にこそありそうだから怖いな～
マロ：たしかに漸化式をどんな感じで設定すればいいかが難しくなるかもね！一緒に問題を解いてどんな漸化式を作ればいいか特訓しよう！
ミケ：おおぉ！
最後までお付き合いいただきありがとうございました。
感想、リクエスト、指摘などコメントしていただけるとマロが喜びます！
次回もよろしくお願いします！
byマロ
この記事が気に入ったらサポートをしてみませんか？