|
uchinyan |
|
ボーナス問題さんへ
いろいろな考察をありがとうございます。 特に後半の議論は面白そうなので後でじっくりと読み勉強させてください。 なお，私の解法に関しては．．． ＞uchinyan さんが利用された余りの数字の関係では置けないかぎ形を排除できていないと思います。 ＞なので、「タイプｔとｎ …可」というのは、 ＞「タイプｔのかぎ形 1 個と長方形 15 個を置けた場合には、ｎを最後に残る 1 マスにすることは可能」 ＞と言っているに過ぎないと理解したためです。 はい，これはおっしゃる通りで，必要条件に過ぎません。 ＞このため、実際にそのような配置が可能であるかを検証する必要があると思った次第です。 はい，これもおっしゃる通りで，この十分条件のチェックが必要です。 ただ，ここで問題への考え方に違いがあって齟齬が生まれたと認識しています。 ここらは次のように集合の手法で説明するのがいいかも知れません。 実現可能な配置の集合を A，対称性も含めた余りの条件を満たす配置の集合を B，タイプ０と 13 の配置の集合を C，とします。 もちろん，A は B に含まれ，C も B に含まれます。ここまでが必要条件です。 しかし，これだけでは A と C の関係は分かりません。ここからが問題の十分条件です。 私は残せる１マスを同定することを目指したので，A と C の共通部分が空かどうかだけを判定しました。 空でなければ 13 が残せるからです。そして空かどうかは要素＝実例が１つでもあるかを示せば十分です。 私の言う十分条件はこの意味で，分かりやすい 2 * 2 の正方形にかぎ形と 13 がある例に言及しました。 こうした論理の流れで，詰めが甘い，というご批判には抵抗がありました。 ただ，2 * 2 の正方形にかぎ形と 13 が入らない例に言及する方がよかったのかも知れません。 また，おっしゃるように，C には A に含まれないものもあるので，それらを考察せず言及すらしなかったのは， 詰めが甘い，とご批判を受けても致し方ないかな，と反省もしております。 ．．． ここで，ちょっと時間が取れたので，後半の Analytic Combinarorics というのを見てみました。 ＞N ≡2 (mod 3) であれば、得られる 2 つの合同式が、 ＞ x + y ≡1 (mod 3) ＞ 2*x + y ≡0 (mod 3) ＞となるので、残せるマスの座標は、常に x ≡y ≡2 (mod 2)。 最後は mod 3 ですね。 確かに，面白いし，すごい！，です。 ただ，同じ結果は，かーちゃんさんの#43738，でも特に道具立てなしに導けるようです。 (座標の入れ方が 1 だけズレているので要注意。) 多分，Analytic Combinarorics の方がより高度な発展があるのでしょうね。 |
|
ネコの住む家
10月8日（木） 11:14:14
43772 |