|
uchinyan |
|
はい，こんにちは。さて，今回の問題は．．．
最初問題を見たとき，NG の場合を引いていく解法を考えたのですが，こんがらがってしまいうまくいかず， 方針を変えて，OK の場合を考えたら簡単に解けちゃった，という感じです (^^; 説明の都合上，対角線が右上がりを 0，右下がりを 1，と表すことにしておきます。 白黒の塗り分けは，一つ存在すれば，その白黒を反転させたものも存在するので， 塗り分けが可能な 0 と 1 のパターンを数えて，それを 2 倍すればいいです。 そこで，以下では塗り分け可能な 0 と 1 のパターンを数えます。 まず，1 * 1 のパターンを考えます。これは明らかに 0 と 1 の 2 通り。 次に，2 * 2 のパターンですが，1 * 1 のパターンに追加すると考えます。 a b c d a に 1 * 1 のパターンを入れると，b は 2 通り，c は 2 通り，可能です。 問題はそのときの d ですが，実際にやってみると， 00 00 01 01 10 10 11 11 00 11 01 10 01 10 00 11 となって，一意に決まることが分かります！ そこで，2 * 2 のパターンは，2 * 2 * 2 = 8 通り，になります。 さて，3 * 3 ですが，2 * 2 に追加していきます。 a b c d e f g h i a, b, d, e に 2 * 2 のパターンを入れて，c は 2 通り, g は 2 通り，で， f は b, c, e より，h は d, e, g より，i は e, f, h より，一意に決まるので， 結局，3 * 3 のパターンは，8 * 2 * 2 = 32 通り，になります。 そこで，白黒の塗り分けの 2 倍をして，32 * 2 = 64 通り，になります。 一般の m * n の場合には，2^(m+n) 通り，になりそうですね。 |
|
ネコの住む家
7月22日（木） 12:21:30
MAIL:uchi@sco.bekkoame.ne.jp 36480 |