おまけ六だけ 。

おまけ九も解ったかも 。

おまけ二 。

おまけ三 。

Σ

Wikipediaさんに相談した八 。

おまけの９
これしか思いつきません

練習問題のヒントとして、
3行9列の盤が塗り分け不可能なことを示しておきます。

1列3マスの塗り分け方は2^3=8通りしかないので、
9列中には塗り分け方が全く同じ2列が存在します。
1列3マス中には同じ色のマスが2マス以上ありますので、
4隅がその色の長方形が存在します。

最大かどうかはわかりません
見つけた中で，一番大きなやつです．

本日正解発表の予定でしたが、2週間ほど延期します。
おまけ問題の「来年」は2023年(うさぎ年)のことですので、
お間違えのないように。

正解発表の延期，ありがとうございます

最大かどうかわかりませんが，前より増えています．
年越しの時季にぴったりの答えだと思いますが，いかがでしょうか？

あっ、なるほど、確かに年越しの音が。

私は、これが最大である証明を得られないでいます。

２色の練習問題ではギリギリなんとかでしたが、３色では………

自信はありません

これは，いかがでしょうか

自作のではありません。

知人に問題を紹介したら、
綺麗なのを教えてくれました。

自作のはアグリーなので恥ずかしく。

３色の場合の最大性の証明は、
申し訳ないことですが、
力不足ゆえ、撤退させてください。

正解発表を楽しみにお待ちしています。

正解発表を開始します。
まずは練習問題。

盤が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列)

塗り分けの一例。

■■■□□□
■□□□■■
□■□■■□
□□■■□■

本題の答えです。

n行m列の盤を白、黒、抹茶の三色で塗り分けることにします。
i列目に含まれる白マス2個の組み合わせの個数をa(i)、
i列目に含まれる黒マス2個の組み合わせの個数をb(i)、
i列目に含まれる抹茶マス2個の組み合わせの個数をc(i)とします。

A=Σa(i),B=Σb(i),C=Σc(i)とすると、
A≦nC2,B≦nC2,C≦nC2なので、A+B+C≦3*nC2です。
a(i)+b(i)+c(i)が最小になるのは、
i列のnマスを[(n+2)/3]個、[(n+1)/3}個、[n/3]個に塗り分けた場合です。
([]はガウス記号。小数部切り捨てと同じ)
その最小値をMとします。
m*M≦A+B+C≦3*nC2なので、m≦[(3*nC2)/M]
面積=nm≦n[(3*nC2)/M]です。

n=4の場合
M=2C2+1C2+1C2=1なので、面積≦n[(3*nC2)/M]=72
面積72のときに実際に塗り分けできるかどうかはおいといて、次に進みます。

n=5の場合
M=2C2+2C2+1C2=2なので、面積≦n[(3*nC2)/M]=75

n=6の場合
M=2C2+2C2+2C2=3なので、面積≦n[(3*nC2)/M]=90

n=7の場合
M=3C2+2C2+2C2=5なので、面積≦n[(3*nC2)/M]=84

n=8の場合
M=3C2+3C2+2C2=7なので、面積≦n[(3*nC2)/M]=96

n=9の場合
M=3C2+3C2+3C2=9なので、面積≦n[(3*nC2)/M]=108

n=10の場合
M=4C2+3C2+3C2=12なので、面積≦n[(3*nC2)/M]=110

n=11の場合
M=4C2+4C2+3C2=15なので、面積≦n[(3*nC2)/M]=121

n=12の場合
12行10列が不可能なので、m≦9であり、面積≦108

n=13の場合
8行13列が不可能なので、m≦7であり、面積≦91

n=14の場合
7行14列が不可能なので、m≦6であり、面積≦84

n=15の場合
7行14列が不可能なので、m≦6であり面積≦90

n=16の場合
5行16列が不可能なので、m≦4であり面積≦64

n=17の場合
5行16列が不可能なので、m≦4であり面積≦68

n≧18の場合
4行18列が不可能なので、m≦3であり不適。

候補の大きい順に調べます。
証明は後ですることにして結果を先に書きますと、
面積121(11行11列)のときは塗り分け不可能
11行10列のときも塗り分け不可能
11行の場合は9列以下となるので面積≦99
面積110(10行11列)のときは塗り分け不可能
10行の場合は10列以下となるので面積≦100
面積108(12行9列)のときは塗り分け可能
となりますので、面積の最大値は108です。

塗り分け不可能なことの証明ですが、
10行11列が不可能であれば11行11列も不可能ですので、
10行11列が不可能であることを示せば十分です。
コンピュータですべての場合を調べた結果、
条件を満たす塗り分け方が見つかりませんでしたので、
塗り分けは不可能です！
というのは嘘です。
実は、チェックするプログラムは作ってみたのですが、
時間がかかりすぎてすべての場合を調べることはできませんでした。
残念！
灰色の脳細胞を使うしかありませんね。
コンピュータより人間の方が優れていることを証明してみましょう。

10行11列の場合、M=12でしたので、A+B+C≧M*11=132=3*44
また、A,B,C≦nC2=45ですので、A+B+C≦3*45=135
A,B,Cのどれも45ではないと仮定します。
A=B=C=44です。
このとき、すべての列でa(i)+b(i)+c(i)=12。
a(i),b(i),c(i)は4C2=6または3C2=3のどちらかなので、すべて3の倍数。
44は3の倍数ではないので、A=Σa(i)が44になることはありません。
従って仮定は誤りであり、A,B,Cのいずれかは45。

132≦A+B+C≦135なので、12≦a(i)+b(i)+c(i)≦15
a(i)+b(i)+c(i)が12以上15以下となるのは
i列を4マス、3マス、3マスに塗り分けたときの12
i列を4マス、4マス、2マスに塗り分けたときの13
i列を5マス、3マス、2マスに塗り分けたときの14
の3種類のみです。
また、a(i)+b(i)+c(i)が12でない列は高々3個しかありません。
列を並べ替えても塗り分けできるかどうかは変わらないので、
a(i)+b(i)+c(i)は降順になっているものとします。
a(i),b(i),c(i)は5C2,4C2,3C2,2C2のいずれか。
i≧4のときはa(i),b(i),c(i)は4C2または3C2です。

A=45であれば、
4C2=6,3C2=3は3の倍数であり、45も3の倍数なので、
a(1)+a(2)+a(3)も3の倍数。
5C2=10,2C2=1はどらちも3で割ると1余るので、
a(1),a(2),a(3)がすべて3の倍数であるか、
a(1),a(2),a(3)がすべて3で割ると1余るか
のどちらかが成り立ちます。
後者の場合、
a(1)+b(1)+c(1)=a(2)+b(2)+c(2)=a(3)+b(3)+c(3)=13のときしかあり得ません。
このときA+B+C=135となるので、A=B=C=45。
任意の列において、b(i),c(i)は3の倍数。
色を交換すれば、A=45,すべてのa(i)は3の倍数、とできます。

つまり、塗り分け可能な場合には、
A=45、すべてのa(i)は6または3となる塗り分け方が存在します。
a(i)は11個あって45/3=15なので、a(i)の4個が6で7個が3です。
白が4マスある列が4個、3マスある列が7個です。

A=45なので、すべての2個の組み合わせが現れます。
白マスが4個ある列4個に注目すると、白マスは合計16個あるので、
白マスが2つ以上ある行が存在します。
行を入れ替えても問題ないので1行目とします。
1行目を含む白マス2個の組み合わせは9個。
白マス4個の列内には1行目を含む組み合わせは3個または0個。
白マス3個の列内には1行目を含む組み合わせは2個または0個。
合計が9個になるためには、3個+3個+3個となるしかないです。
つまり、1行目が白マスである列は3列あり、3列とも白マスが4個あります。
この3列において、1行目以外の行に白マスが2個以上あると、
4隅が白の長方形ができてしまうので、1行目以外の行には白マスは1個以下。
1行目以外に白マスは9個あるので、1行目以外の行には白マスがちょうど1個ずつ。
行、列を並べ替えて、
1列目は1,2,3,4行目が白マス、
2列目は1,5,6,7行目が白マス、
3列目は1,8,9,10行目が白マス、
とできます。
もう1列、白マスが4マスある列が存在しますが、この列を塗り分けることは不可能です
1行目を白マスにしてしまうと、他のマスを白にすることができないので、
1行目は白マスではありません。
2,3,4行目には白マスは高々一つしか入れられません。
5,6,7行目には白マスは高々一つしか入れられません。
8,9,10行目には白マスは高々一つしか入れられません。
最大3マスしか白にすることができないのです。
よって、10行11列の盤を塗り分けることは不可能です！
証明終わり。




面積108の場合の塗り分けの一例。

□□■□■■※※※
□※□■□※■■※
□■※※■□□■※
□■■※※※■□□
※□□※■□■※■
※□■■□※※□■
■□※■■※□※□
■※□□※■■※□
※■□■※■□□※
※※※□□■□■■
■■※□※□※□■
■※■※□□※■□


おまけは来週にします。

おまけ問題の答えを発表します。
2023年うさぎ年にちなんだ問題でした。

その一:農作業
「のうさぎょう」には「うさぎ」が含まれるから。


その二:とにかく多忙
「とにかく」は「兎に角」と書けるので。

その三:テラビット
「ラビット」が含まれるから。

その四:架空料金請求詐欺
「うさぎ」が含まれるから。

その後:しばしば
「しばしばニート」には「バニー」が含まれるから。

その六:アメリカ合衆国
USA(うさ)だから。

その七:p^3-16p^2+52p-48
p=19のとき2023になるから。

その八:なか卯
卯年だから。

その九:水の塔
2023年は癸卯(みずのとう)だから。

それでは、来年も良い年でありますように(早っ！)。