MathLabs

第4問

32×3232\times32 の盤を考える。左下のマスに、上向きのねずみを置き、他のいくつかのマスにチーズを置く。ねずみは動き始め、チーズに到達しない限り直進するが、チーズに到達するとその一部を食べて右に曲がり、その後も直進する。この過程でねずみが各チーズをちょうど1回ずつ味わってから盤の外へ落ちるとき、チーズのあるマスの集合を良い集合と呼ぶ。(a) 888888 個のマスからなる良い集合は存在しないこと、(b) 少なくとも 666666 個のマスからなる良い集合が存在することを示せ。
ステップ 4/4: 5回反復してサイズ32にする
前のステップ次のステップ
∣L1∣=3, ∣L2∣=11, ∣L3∣=43, ∣L4∣=171, ∣L5∣=683≥666|L_1|=3,\ |L_2|=11,\ |L_3|=43,\ |L_4|=171,\ |L_5|=683\ge666
詳しい解説

32=2532=2^5 なので、∣L1∣=3|L_1|=3 から漸化式を4回適用すると ∣L2∣=4⋅3−1=11|L_2|=4\cdot3-1=11、∣L3∣=4⋅11−1=43|L_3|=4\cdot11-1=43、∣L4∣=4⋅43−1=171|L_4|=4\cdot43-1=171、∣L5∣=4⋅171−1=683|L_5|=4\cdot171-1=683 となる。タイル L5L_5 は、ねずみが左下のマスに上向きで入る 32×3232\times32 の配置であり、そのチーズマスは 683≥666683\ge666 個からなる良い部分集合をなす。