MathLabs

第4問

32×3232\times32 の盤を考える。左下のマスに、上向きのねずみを置き、他のいくつかのマスにチーズを置く。ねずみは動き始め、チーズに到達しない限り直進するが、チーズに到達するとその一部を食べて右に曲がり、その後も直進する。この過程でねずみが各チーズをちょうど1回ずつ味わってから盤の外へ落ちるとき、チーズのあるマスの集合を良い集合と呼ぶ。(a) 888888 個のマスからなる良い集合は存在しないこと、(b) 少なくとも 666666 個のマスからなる良い集合が存在することを示せ。
ステップ 1/4: 4回連続の方向転換はループを閉じてしまう
no 4 consecutive cheese-visits in the move sequence\text{no 4 consecutive cheese-visits in the move sequence}
詳しい解説

ねずみが踏んだマスを訪問したマスと呼ぶ(チーズのマスか空のマスのいずれか)。もしねずみが4回連続の歩みでチーズのマス4つを訪れたなら、単位移動の後に4回連続で右折し、閉じた単位正方形を描いてこの連続が始まったマスに戻ってしまう——しかし各チーズのマスは1回しか訪れないので矛盾する。よって訪問したマスの列は4回連続でチーズを訪れることはない。