★ 第 33 回問題 ★


座標平面において, x 座標と y 座標の両方が 整数であるような点を「格子点」という.
ab なる正の整数 a , b に対して,座標平面上の格子点を 移動する「 (a, b) -ナイト」という駒を考える. これは点 (x, y) にその駒があるときに, (x±a, y±b) または (x±b, y±a) (複号任意)の 合計 8 通りの点のどれかに移動できる駒である.
最初に (a, b) -ナイトが点 (0, 0) に置かれている. これを何回かの移動により,点 (1, 0) へ持っていきたい.
(1) (1, 0) へ持っていくことが可能であるために a , b が満たすべき必要十分条件を求めよ.
(2) (1, 0) へ持っていくためには,最低でも ab 回の移動が必要であることを証明せよ.
(3) a , b が(1)の条件を満たしているとする. 2b 回以下の移動で (1, 0) に持っていけることを証明せよ.
※(1), (2), (3) の全てが解けていなくても, 解けたものだけでも良いので是非送ってみてくださいね.

応募は締め切りました.

第 33 回問題解説・正解者発表へ/ 問題一覧へ /トップページへ ●5474
出題: 2010 年 4 月 13 日 (火) 10 時 00 分 00 秒
締切: 2010 年 5 月 10 日 (月) 23 時 30 分 00 秒
解説・正解者発表: 2010 年 6 月 7 日 (月) 19 時 30 分 00 秒
担当者: 西本 将樹