今回の記事はEGMO2018本選の第４問です。問題は公式サイトで確認してください。
前半は小さい物を地道に作って議論を進めましょう。
後半は「逆から考える」とうまくいくかも。
まずは小さい値で考えます。結論からいうとn=3,4,5,7は地道に作ります。
n=3,4,5,7における均等な配置は、以下のものが考えられる。
| n=3 | n=4 | n=5 | n=7 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
以降、この配置をそれぞれP3、P4、P5、P7とおく。
残りの数はこの配置を並べていくと作ることができます。
n=8のときは左上と右下にP4、n=10のときは左上と右下にP5を並べ、
n=11のときは左上にP4、右下にP7を並べるといずれも価値3の均等な配置となる。
また、nが13以上のときは非負整数a,bを用いてn=4a+5bと表せるので対角線上にP4をa枚とP5をb枚並べると均等な配置ができる。
n=6,9,12のときは対角線上にP3を並べることで均等な配置ができる。
したがって、3以上の全ての整数nに対して均等な配置が存在する事が示せる。
n=11のときは左上にP4、右下にP7を並べるといずれも価値3の均等な配置となる。
また、nが13以上のときは非負整数a,bを用いてn=4a+5bと表せるので対角線上にP4をa枚とP5をb枚並べると均等な配置ができる。
n=6,9,12のときは対角線上にP3を並べることで均等な配置ができる。
したがって、3以上の全ての整数nに対して均等な配置が存在する事が示せる。
P7はn=11のときにどうしても必要になってしまったのでした。
ここからは、最小の配置数を考えます。
「逆に考える」とは、ドミノを配置したときに価値がどうなるか、を考えることになります。
ドミノを1枚配置すると、その大きさは1×2もしくは2×1であるので
2行と1列もしくは1行と2列の価値が1だけ上がり、したがって総和は3だけ上がる。
すなわちドミノをm枚配置したときの価値の総和は3mであるとわかる。
また、n×nの盤面で価値kの均等な配置が成立しているとき、価値の総和は2nkとなる。
したがって整数m,n,kで3m=2nkが成立するkの最小値をさがし、実際にその配置が存在することを示せばよい。
2行と1列もしくは1行と2列の価値が1だけ上がり、したがって総和は3だけ上がる。
すなわちドミノをm枚配置したときの価値の総和は3mであるとわかる。
また、n×nの盤面で価値kの均等な配置が成立しているとき、価値の総和は2nkとなる。
したがって整数m,n,kで3m=2nkが成立するkの最小値をさがし、実際にその配置が存在することを示せばよい。
これで最小値を検証する準備ができました。倍数があるので場合分けをしましょう。
nが3の倍数のときk=1とできるのでm=(2/3)nが考えられる。
実際、P3を対角線上に並べていくと(2/3)n枚で価値1の均等な配置ができる。
実際、P3を対角線上に並べていくと(2/3)n枚で価値1の均等な配置ができる。
ここからはnが3の倍数でないときです。
nが3の倍数でないとき2nkが3の倍数でなければならないのでk=3のときを考えることになる。
このような配置は前半で実際に作成しているので、k=3となる場合は可能で、しかも最小であることが分かる。
このときのmを計算すると、m=2n
このような配置は前半で実際に作成しているので、k=3となる場合は可能で、しかも最小であることが分かる。
このときのmを計算すると、m=2n
ということで、両方の結果が示せました。
したがって、最小値は、
nが3の倍数のとき(2/3)n,nが3の倍数でないとき2n
nが3の倍数のとき(2/3)n,nが3の倍数でないとき2n