 コメント ( No.17 ) |
- 日時： 2023/01/12 12:55
- 名前： ほにょこ
- 正解発表を開始します。
まずは練習問題。
盤がn行m列だとします。
i列目に含まれる白マス2個の組み合わせの個数をa(i)、
i列目に含まれる黒マス2個の組み合わせの個数をb(i)とします。
例えばi列目に白マスがk個ある場合、
2個の組み合わせはkC2個なので、a(i)=kC2です。
Σa(i)>nC2だと同じ白マス2個の組み合わせができてしまいますので、Σa(i)≦nC2
同様にΣb(i)≦nC2であり、Σ(a(i)+b(i))≦2*nC2です。
i列に白マスがk1個、黒マスがk2個あり、k1>k2+1だとすると、
白マス1個を黒に塗り替えた場合、
a(i)はk1-1減り、b(i)はk2増えますので、a(i)+b(i)はk2+1-k1増えます。
k2+1-k1<0ですので、a(i)+b(i)の値は小さくなります。
白マス、黒マスの個数に2以上の差があればa(i)+b(i)を小さくすることができるのです。
a(i)+b(i)が最小になるのは、黒マスの個数と白マスの個数の差が1以下のときです。
最小値をとる場合は(色の入れ替えを除けば)一通りしかありません。
nが偶数の場合は黒マスと白マスを同数に塗り分けたもの。
nが奇数の場合、1マスは任意の色で残りの偶数個を同数に塗り分けたもの。
n=3の場合
a(i)+b(i)≧2C2+1C2=1なので、m*1≦Σ(a(i)+b(i))≦2*3C2=6
m=6の場合には塗り分け可能なので、最大6列。このときの面積は18。
n=4の場合
a(i)+b(i)≧2C2+2C2=2
2m≦Σ(a(i)+b(i))≦2*4C2=12より、m≦6
m=6の場合には塗り分け可能なので、最大6列。面積24。
n=5の場合
a(i)+b(i)≧3C2+2C2=4
4m≦Σ(a(i)+b(i))≦2*5C2=20より、m≦5
m=5とすると、
Σ(a(i)+b(i))=20であり、最小値をとるので
すべてのiについてa(i)+b(i)=4
a(i),b(i)は3C2=3または2C2=1であり、すべて奇数。
Σa(i)=10であるが、奇数を5個足して偶数になることはないので不適。
よってm≦4であり面積は20以下。
n=6の場合
m≧5の場合に可能だとすると、
5行5列の場合にも可能なことになり矛盾する。
m=4のときは4行6列の場合と同じ。
n≧7の場合に可能だとすると、
3行7列の場合にも可能なことになり矛盾する。
以上より、面積の最大値は24です。
(4行6列または6行4列)
塗り分けの一例。
■■■□□□
■□□□■■
□■□■■□
□□■■□■
|
|
FAQ
RSS