2020 年日本数学オリンピック予選 問題7

2020 年日本数学オリンピック予選　問題7

https://www.imojp.org/archive/mo2020/jmo2020/problems/jmo30yq.html

Q7. 2×1010 のマス目の各マスに 1 以上 5 以下の整数を 1 つずつ書き込む。辺を共有して隣りあうどの 2 マスについても書き込まれた数の差が 2 または 3 となるように書き込む方法は何通りあるか。ただし，回転や裏返しによる一致する書き込みも異なるものとして数える。

　常套手段としては，場合分けを考えて...ということになるのだろうが，どうせコンピュータを使って解を求めようとしているんだから，ブルートフォースで解のとっかかりを調べよう。

　まず最も簡単な場合の 2 × 2 列の場合に，そのような書き込み法が何通りあるか見てみよう。

  pairs = []
  for i = 1:5
      for j = 1:5
          2 <= abs(i-j) <= 3 && append!(pairs, [[i, j]])
      end
  end
  println(pairs)
  n = length(pairs)
  for i = 1:n
      for j = 1:n
          if i != j
              (2 <= abs(pairs[i][1] - pairs[j][1]) <= 3 &&
               2 <= abs(pairs[i][2] - pairs[j][2]) <= 3) && print(" $(pairs[i]):$(pairs[j])")
          end
      end
      println()
  end

  Any[[1, 3], [1, 4], [2, 4], [2, 5], [3, 1], [3, 5], [4, 1], [4, 2], [5, 2], [5, 3]]
   [1, 3]:[3, 1] [1, 3]:[3, 5] [1, 3]:[4, 1]
   [1, 4]:[3, 1] [1, 4]:[4, 1] [1, 4]:[4, 2]
   [2, 4]:[4, 1] [2, 4]:[4, 2] [2, 4]:[5, 2]
   [2, 5]:[4, 2] [2, 5]:[5, 2] [2, 5]:[5, 3]
   [3, 1]:[1, 3] [3, 1]:[1, 4] [3, 1]:[5, 3]
   [3, 5]:[1, 3] [3, 5]:[5, 2] [3, 5]:[5, 3]
   [4, 1]:[1, 3] [4, 1]:[1, 4] [4, 1]:[2, 4]
   [4, 2]:[1, 4] [4, 2]:[2, 4] [4, 2]:[2, 5]
   [5, 2]:[2, 4] [5, 2]:[2, 5] [5, 2]:[3, 5]
   [5, 3]:[2, 5] [5, 3]:[3, 1] [5, 3]:[3, 5]

　1 列目の配置は 10 通り，それぞれに対して 2 列目は 3 通りあることがわかった。

　この手のコンピュータプログラミングにおける定石は，簡単な場合について計算し，結果に規則性があるかどうか見るということだ。

　そこで，2 × ncol 行列で条件を満たす個数を勘定するプログラムを書く。

  using Combinatorics
  
  all_perm(x, n) = Iterators.product([x for i = 1:n]...)
  
  isng(x, y) = !(2 <= abs(x - y) <= 3)
  
  function checkcol(a, ncol)
      for j = 1:ncol
          isng(a[1, j], a[2, j]) && return false
      end
      true
  end
  
  function checkrow(a, ncol)
      for j = 1:ncol-1
          (isng(a[1, j], a[1, j+1]) || isng(a[2, j], a[2, j+1])) && return false
      end
      true
  end
  
  function q7(ncol)
      count = 0
      for i in all_perm(1:5, 2ncol)
          a = reshape([j for j in i], 2, :)
          checkcol(a, ncol) && checkrow(a, ncol) && (count += 1)
      end
      count
  end

  q7 (generic function with 1 method)

実際に，i = 1〜5 列まで増やしながら解を求めてみよう。

  for i in 1:5
      println("i = $i,  q7 = $(q7(i))")
  end

  i = 1,  q7 = 10
  i = 2,  q7 = 30
  i = 3,  q7 = 90
  i = 4,  q7 = 270
  i = 5,  q7 = 810

この結果を見れば，10 * 3 ^ (i -1) であることが推理できるというものだろう。

  for i in 1:5
      println("i = $i,  q7 = $(q7(i)), estimate = $(10 * 3 ^ (i-1))")
  end

  i = 1,  q7 = 10, estimate = 10
  i = 2,  q7 = 30, estimate = 30
  i = 3,  q7 = 90, estimate = 90
  i = 4,  q7 = 270, estimate = 270
  i = 5,  q7 = 810, estimate = 810

従って，i = 1010 ならば，10 * 3 ^ 1009 通りある。