No. 17≫ No.18 ≫No. 19
ほにょこ
2023/01/13 12:56
本題の答えです。
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の場合の塗り分けの一例。
<tt>
□□■□■■※※※
□※□■□※■■※
□■※※■□□■※
□■■※※※■□□
※□□※■□■※■
※□■■□※※□■
■□※■■※□※□
■※□□※■■※□
※■□■※■□□※
※※※□□■□■■
■■※□※□※□■
■※■※□□※■□
</tt>
おまけは来週にします。
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の場合の塗り分けの一例。
<tt>
□□■□■■※※※
□※□■□※■■※
□■※※■□□■※
□■■※※※■□□
※□□※■□■※■
※□■■□※※□■
■□※■■※□※□
■※□□※■■※□
※■□■※■□□※
※※※□□■□■■
■■※□※□※□■
■※■※□□※■□
</tt>
おまけは来週にします。