ヨーロッパ女子数学オリンピック 2018 問4

今回の記事はこちらの問題。EGMO2018本選の第4問です。

1×2または2×1のタイルをドミノとよぶ。
nを3以上の整数とする。n×nのマス目にそれぞれのドミノがちょうど2つのマスを覆い、互いに重ならないようにドミノを配置する。
それぞれの行および列に対してその価値を、その行や列のマスを少なくとも1つ覆っているドミノの個数とする。ある正の整数kが存在して、どの行および列の価値もkであるとき、この配置は均等である、という。
任意のnに対して均等な配置が存在することを示し、均等な配置で用いられるドミノの個数としてありうる最小の値を求めよ。

前半は小さい物を地道に作って議論を進めましょう。
後半は「逆から考える」とうまくいくかも。

まずは小さい値で考えます。結論からいうと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に対して均等な配置が存在する事が示せる。

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の最小値をさがし、実際にその配置が存在することを示せばよい。

これで最小値を検証する準備ができました。倍数があるので場合分けをしましょう。

nが3の倍数のときk=1とできるのでm=(2/3)nが考えられる。
実際、P3を対角線上に並べていくと(2/3)n枚で価値1の均等な配置ができる。

ここからはnが3の倍数でないときです。

nが3の倍数でないとき2nkが3の倍数でなければならないのでk=3のときを考えることになる。
このような配置は前半で実際に作成しているので、k=3となる場合は可能で、しかも最小であることが分かる。
このときのmを計算すると、m=2n

ということで、両方の結果が示せました。

したがって、最小値は、
nが3の倍数のとき(2/3)n,nが3の倍数でないとき2n
スポンサーリンク

シェアする

  • このエントリーをはてなブックマークに追加

フォローする

スポンサーリンク