MathLabs

第4問

32×3232\times32 の盤を考える。左下のマスに、上向きのねずみを置き、他のいくつかのマスにチーズを置く。ねずみは動き始め、チーズに到達しない限り直進するが、チーズに到達するとその一部を食べて右に曲がり、その後も直進する。この過程でねずみが各チーズをちょうど1回ずつ味わってから盤の外へ落ちるとき、チーズのあるマスの集合を良い集合と呼ぶ。(a) 888888 個のマスからなる良い集合は存在しないこと、(b) 少なくとも 666666 個のマスからなる良い集合が存在することを示せ。
ステップ 2/4: (a): 数え上げが多すぎるマスを強制する
前のステップ次のステップ
888=3⋅296 ⇒ ≥296 blocks, ≥295 separators, ≥148 gap-cells;888+148>322888=3\cdot296\ \Rightarrow\ \ge296\text{ blocks},\ \ge295\text{ separators},\ \ge148\text{ gap-cells};\quad 888+148>32^2
詳しい解説

良い部分集合にチーズのマスが 888888 個あるとする。前段より、連続するチーズ訪問のブロックの長さは多くとも 33 なので、少なくとも ⌈888/3⌉=296\lceil888/3\rceil=296 ブロックが必要であり、それらの間に少なくとも 295295 回の区切りとなる空マス訪問が必要になる。各空マスは多くとも2回訪問されるので、少なくとも ⌈295/2⌉=148\lceil295/2\rceil=148 個の相異なる空マスが必要である。よって盤面には少なくとも 888+148=1036>322=1024888+148=1036>32^2=1024 マスが必要となり、矛盾する。したがって 888888 マスからなる良い部分集合は存在しない。