|
ボーナス問題 |
|
まず、tsk さん (#43766) へ。
万能パターン的なもの見つけられた洞察力に敬服します。 次に uchinyan さん (#43768) へ。 > 具体的な配置までは詳細に調べる問題とは認識していませんでした 私自身も、具体的な配置を詳細に調べる問題とは認識していません。なぜなら、uchinyan さんも仰るように、全ての解を求めるのは結構大変なので。 くどいと言われるかもしれませんが、もう少々お付き合いを。 私が拘った理由をもう少し説明します。かぎ形は、長方形とは異なり、最初から置けないところが存在します。私が最初に使った以下の図を見てください。 ０１２０ １２０１ ２０１２ ０１２０ この図では、0 が 6 個、1 と 2 が 5 個ずつ。長方形は必ず 0、1、2 の 3 つの数字を覆います。このため、最初にかぎ形を 0 でない 2 つの同じ数字を覆うように置いてしまうと、長方形 4 個を配置することが不可能になります。 対称性 (図を 90 度回転) を考えると、この制約は思ったより厳しいものになることがわかるかと思います。 蛇足ですが、私が長方形だけの場合にこの図を使用したのは、かぎ形を配置できない場所があることへのヒントでもありました。 uchinyan さんが利用された余りの数字の関係では置けないかぎ形を排除できていないと思います。なので、「タイプｔとｎ …可」というのは、「タイプｔのかぎ形 1 個と長方形 15 個を置けた場合には、ｎを最後に残る 1 マスにすることは可能」と言っているに過ぎないと理解したためです。 このため、実際にそのような配置が可能であるかを検証する必要があると思った次第です。 私の解法でも同じで、置けたとしたら、あるマスが最後の 1 マスにならないことを言及しているだけなので、検証が必要です。 検証自体は、4x4 の場合から、ほぼ自明に近いので、単に割愛しただけとは思いましたが、あえて再度「詰めが甘い」と言わせて頂きました。 これも蛇足ですが、そもそもの私の誤解は uchinyan さんに非があるのではなく、私が例に示した解が「タイプ０と 12」になると勘違いしたためです (1 からではなく、0 から数えてしまった)。そのために混乱してしまい、ご迷惑をおかけしてしまったことを重ねてお詫び致します。 こちらこそ、uchinyan さん、tsk さんを始め、お付き合い頂いた皆さんありがとうございました。お陰様で楽しい時間を過ごすことができました。 ここからは算数の範囲から大きく逸脱しますが、先日触れた Analytic Combinatorics の手法を用いて、4x4 の正方形において 1x3 の長方形 5 個を敷き詰めた場合の残りの 1 マスを考えます。 まず、各マスに (0, 0) から (3, 3) の座標を振ります。ここでは、左下が (0, 0)、右下が (0, 3)、右上が (3, 3) になるようにします。 次に以下の多項式を考えます。 式 1) f(u, v) = (1 + u + u^2 + u^3) * (1 + v + v^2 + v^3) この多項式を展開して得られる u^x*v^y の数は 16 となり、この (x, y) がマスの座標を表します (1 は、u^0*v^0 として表す)。 以降、u^x*v^y を {x,y} と表すことにします。 長方形を縦に置いた場合 {x,y} + {x,y+1} + {x,y+2} = {x,y} * ({0,0} + {0,1} + {0,2}) = {x,y} * (1 + v + v^2) 横に置いた場合、同様に、 {x,y} + {x+1,y) + {x+2,y} = {x,y} * (1 + u + u^2) すると、最初の多項式は、 式 2) f(u,v) = (1 + u + u^2) * g(u,v) + (1 + v + v^2) * h(u,v) + {x,y} と表せます。 ここで、g と h は、u と v の多項式を値とする関数です。そして、最後の {x,y} が、最後に残る 1 マスの座標を表します。 次に w を、次の方程式の解とします (w は、1 の三乗根)。 1 + w + w^2 = 0 この w をそれぞれ、式 1 と式 2 に与えます f(w,w) = (w^3) * (w^3) = 1 f(w,w) = w^(x+y) なので、 x + y ≡0 (mod 3) 同様に、w^2 と w を 2 つの式に与えます f(w^2,w) = 1 f(w^2,w) = w^(2*x+y) なので 2*x + y = 0 (mod 3) この 2 つの合同式から、 x ≡0 (mod 3) が得られて、x は 0 か 3。そして、y も 0 か 3 と判ります。 なので、最後に残るマスの座標は、(0,0)、(0,3)、(3,0)、(3,3) の 4 つ。 7x7 も同様にして、やはり同じ合同式が得られるので、x は、0、3、6 のいずれか。そして、y も 0、3、6 のいずれかと判ります。 また、NxN の場合、 N ≡1 (mod 3) であれば、式 1 が変わるだけで、得られる 2 つの合同式は 4x4 と同じものなので、残せるマスの座標は、常に x ≡y ≡0 (mod 3)。 N ≡2 (mod 3) であれば、得られる 2 つの合同式が、 x + y ≡1 (mod 3) 2*x + y ≡0 (mod 3) となるので、残せるマスの座標は、常に x ≡y ≡2 (mod 2)。 これは、今年から高齢者さんが #43759 した予想とも一致します。 このように、Analytic Combinarorics のすごいところは、上の式 1 と 2 を上手に選べば、1 の羃乗根の性質を使って、すべての場合を求めることが一瞬でできてしまうことです。 トリッキーなところが多々ありますが、これをキチンと説明するには複素解析の領域に踏み込まないといけないので、ここでは割愛させて頂きます (というよりは、私自身がこの手法を完全に理解していないので、説明する自信がないのです)。単に、このような解法もあるのだと理解して下さい。 |
|
10月7日（水） 7:17:20
43769 |