昨日の解説その１(必要条件について)
よし、このブログ初の問題解説ｗ
えーっとまず、座標平面を考えます。
原点に点Pがあって、そいつが桂馬とびみたいな感じで動く、とします。
そして、Pがすべての格子点にたどり着けるための条件を考えます。
このとき、「Pが全ての格子点を通る」ことと、「Pが(1,0)を通る」ことは同値です。
Pが全ての格子点を通るならばもちろん(1,0)も含まれていますね。
また、(0,1)を通るならば90度まわせば(1,0)も通りますし、(-1,0)(0,-1)も同様に通るので、それを何度も繰り返せば結局全てのマスを通ることが分かるからです。よって、(1,0)を通るかどうかのみを調べればよいことが分かります。
さて、まずは全ての格子点を通らないa,bの条件を考えて見ましょう。
次のそれぞれの動き方で全ての格子点を通ることは果たして可能でしょうか？
(1) <3,6>
(2) <10,15>
(3) <3,5>
(4) <7,9>
まず(1)と(2)を考えて見ることします。
(1)のときはxy座標がともに3の倍数、(2)のときはともに5の倍数の点しか通らないことは明らかですね。
以上のことをさらに推し進めて考えると、全ての格子点を通るためにはaとbが互いに素であることが必要だとわかります。
a,bがともにnの倍数ならば、x座標かy座標のどちらかがnの倍数でない点を通ることは出来ないからです。
次に(3)と(4)を考えます。今度は互いに素ですが、それで十分でしょうか？
もちろんそんなことはありませんね。
どちらの場合も、aとbはともに奇数です。
つまり、一回の移動を行うと、x座標にもy座標にも奇数が足されることになります。
最初にいる点は(0,0)、つまり(偶数、偶数)ですから、Pの通る点は(偶数、偶数)または(奇数、奇数)となる点のみです。
よって、この移動では全ての点を通ることは出来ません。*1
以上から、a+bが奇数、つまりa,bの一方が偶数で他方が奇数であることも必要だとわかります。*2
さて、以上を整理してみます。
Pが全ての格子点を通るためには、
・aとbが互い素
・a+bは奇数(a,bのうち片方が偶数、もう片方が奇数)
のに条件が必要だとわかりました。*3
それでは、この二条件があれば十分なのでしょうか？
