![](https://stat.ameba.jp/user_images/20150506/12/k-nagatoshi-mathematic/88/ed/j/t02200137_0746046413298206746.jpg?caw=800)
解答作成日:2015年3月4日
テーマ:アルゴリズムの利用
履修学年:なし
(決まり事を把握・活用する力が問われる問題ですので、本題は発想次第で小学校算数の範囲で解答可能です。)
今までご紹介させていただいた問題が高校数学の定理を伴うものばかりで、しかも、テーマで「アルゴリズム」という情報学用語を用いたので、おそらく面食らった方もいると思います。
しかし、「アルゴリズム」というのは、結論に至るまでの手順の形式的表現を意味し、数学や情報学に限らず、どなたでも日常的に無意識に用いているものです。
簡単な言い方をすれば、作業のマニュアル化・効率化ですね。
本題では、「64のマス目に、1から33までの数字がそれぞれ少なくとも1個入っている」ことを考えると、「鳩の巣原理」の考え方を利用して、「少なくとも2種類の数字は、1マスにしか存在しない」ということは見抜けますね。
※ 鳩の巣原理…(n+k)羽の鳩をn個の巣箱に入れようとすると、1個の巣箱にちょうど1羽ずつ入れることは不可能で、k羽の鳩が、他の鳩と同じ巣箱に入らざるを得ないとする原理。本題では、1から33までの数字が入ったマス目を1マスずつ消去すると残りは31マス、この31マスに1から33までの数字を1マスずつ入れることは不可能で、少なくとも2種類の数字が入るマスがない、すなわち、当初消去した1マスにしか存在しないことが証明される。
この「1マスにしか存在しない数字」が存在するマス目は絶対に通ります。
また、左上の「1」は絶対通るので、他に「1」があったらそこは通りません。
![](https://stat.ameba.jp/user_images/20150505/17/k-nagatoshi-mathematic/e0/3a/p/t02200311_0769108713297326939.png?caw=800)
「同じマスを2回通らないので、行き止まりになってしまう順路は通らない」ということも意外な盲点になりそうですね。