|
ボーナス問題 |
|
uchinyan さん (#43762)、わざわざ丁寧な説明ありがとうございます。tsk さん (#43761) の指摘で、私の思い込み違いの誤解だったことが判ったので、申し訳ない限りです。
さて、私の #43754 についてですが、ほぼ思った通りところが指摘されているかと思います。ただ、お互い自分の主張 (誤解も含めて) があると思うので、なるべくまぎれのないように説明したいと思います。 > 例えば，０が４つで [400] ですが，１が４つでも２が４つでも [400] ですよね？ はい、表記上はそうです。が、残りの 4 マスを考えた時には、4 個となるのは○だけに限られます。この事実から、{400} で 0 が 4 個と、誤解されてしまうのは、私の表現のまずさだと痛感しています。 > [310] のパターンはあるような気がします。例えば，２が３つで０が１つ。 これも、 その通りで、「{310}、{211}、{220} を含めて」と書くべきでした。そして、uchinyan さんも指摘されているように、ここが大きく説明を端折ったところです。 > 「0 の列が除外」の理由がよく分かりません。先ほどの例， もう少しまぎれのない方法で、説明をしてみます。 最終的に残る 1 マスを、4x4 の正方形で考えます。その正方形の各マスに、記号○、△、□のいずれかを以下のパターンで書き入れた盤面で考えます。 ○△□○ ○△□○ ○△□○ ○△□○ 記号 ○の個数は全部で 8 個。△、□の個数は、それぞれ 4 個ずつあることになります。 この盤面に 1x3 の長方形を 4 個置いた時、残るのは 4 マスです。そして、その残った 4 マスにかぎ形が置けるのなら、その 4 マスのいずれかが最後に残る 1 マスになります。 ここで、1x3 の長方形 1 個が覆う 3 マスの記号の個数を考えると、縦に置いた場合、同じ記号が 3 個。横に置いた場合、あい異なる記号が 3 個 (つまり、 ○、△、□が 1 個ずつ)。 このことから、長方形をいくつか配置した時、覆われている記号○、△、□の個数を、それぞれ a、b、c とすると、以下の関係が成り立ちます。 a ≡b ≡c (mod 3) まだ長方形が置かれていないマスにある記号○、△、□の個数を、それぞれ p、q、r とすると、上の合同式と盤面全体に書かれている記号の個数から、以下の関係が成り立つことが判ります。 p+2 ≡q ≡r (mod 3) ここで、以降の説明のため、ある記号が x 個、それ以外の 2 つの記号がそれぞれ y 個と z 個あることを示す表現 {xyz} を導入します。この表現においては、x、y、z がそれぞれどの記号の個数であるかは特定していません。 この表現を使用すると1x3 の長方形が覆う記号の個数は、{300} (縦) と {111} (横) と表現されます。 同様に、かぎ形はどのような向きに置いても、{210} となり、最後の 1 マスは {100} となります。そして、盤面全体では {844} で、8 個なのは○です。 盤面に 1x3 の長方形を 4 個置いた時、残った 4 マスは、{400}、{310}、{211}、{220} のいずれかになります。そして、上の 2 番目の合同式とかぎ形が {210} であることを考慮すると、以下のことが導かれます。 {400} の時、合同式から 4 個なのは○と特定できる。しかし、かぎ形が {210} であることから、かぎ形を置くことができない。 {310} の時、合同式から 1 個なのは○と特定できる。そして、かぎ形が {210} であることから、かぎ形を置けるなら必ず○を覆う。よって、最後の 1 マスの記号は○ではない。 {211} の時、合同式より 2 個あるのは○特定できる。そして、かぎ形は {210} であることから、かぎ形を置けるなら必ず 2 個の○を覆う。よって、最後の 1 マスの記号は○ではない。 {220} の時、合同式から 0 個なのは○と特定できる。よって、かぎ形を置けるならば、最後の 1 マスの記号は○ではない。 以上から、残った 4 マスにかぎ形を置けるすべての場合について、記号○と書かれたマスが、最後に残る 1 マスにはならないことが判ります。そして記号の書かれた盤面を 90 度回転させたもので考えると、最後に残る 1 マスは中央の 2x2 の正方形のいずれかのマスになることが判ります。 ここまで最後に残る 1 マスが存在しうる記号について可能性だけを述べてきたので、実際に長方形とかぎ形を隙間なく、敷き詰めることが実現可能であることを示す必要があります。 実際試してみると、長方形 4 個を口の字形に配置すると、中央の 2x2 の正方形を残すことができる。また、この 2x2 の正方形の中に、すべての向きのかぎ形を置くことができ、2x2 の正方形の 4 マスすべてを、最後の 1 マスにすることができます。 よって、最後の 1 マスは、中央の 2x2 の正方形に含まれる 4 マスになることになります。 7x7 の正方形の場合も、合同式も含めて上の議論が成り立ちますので、最後の 1 マスが存在する可能性があるマスは、田の字の空白部分にある 4 つの 2x2 の正方形に含まれることが判ります。 ただ、それが本当に実現可能かを、そのまま試すのは骨が折れるので、少し工夫をします。 7x7 の四隅の 1 つから、4x4 の正方形を切り出します。すると、残った図形には 11 個の長方形を隙間なく敷き詰められることが容易に判ります。一方、4x4 の正方形においては、4 個の長方形と 1 個のかぎ形を敷き詰めることができ、その中央の2x2 の正方形に含まれるすべてのマスを最後の 1 マスにすることが可能です。これを四隅のすべてで試せば、田の字の空白部分にある 4 つの 2x2 の正方形に含まれるいずれかのマスを最後の1 マスにすることができます。 2 個以上のかぎ形では、上の手法では場合分けが爆発的に増えて、実用的ではないかと思います。 比較的新しい分野なのですが、Analytic Combinatorics (該当する日本語は良くわかりません) というものがあります。爆発的に増える場合分けを、多項式と複素数を多用してスマートに処理する手法のようです。これについては、別途、書きます。 |
|
10月6日（火） 6:12:55
43767 |