2020 年日本数学オリンピック予選 問題 1，3，4，5

1.　2020 年日本数学オリンピック予選　問題 1，3，4，5

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

Q1.

千の位と十の位が 2 であるような 4 桁の正の整数のうち，7 の倍数はいくつあるか。

  count = 0
  for i = 0:100:900, j = 0:9
      (2020 + i + j) % 7 == 0 && (count += 1)
  end
  println(count) # 14

  14

Q3.

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

要素数 6 個のベクトルを 2 × 3 行列に対応づける。
1 3 5
2 4 6

  g(x, i, j) = gcd(x[i], x[j]) == 1
  
  using Combinatorics
  count = 0
  a = 1:6
  for i in 1:factorial(length(a))
      x = nthperm(a, i)
      (g(x, 1, 2) && g(x, 3, 4) && g(x, 5, 6) && g(x, 1, 3) && g(x, 3, 5) && g(x, 2, 4) && g(x, 4, 6)) && (count += 1)
  end
  println(count) # 16

  16

Q4.

正の整数 n であって，n^2 と n^3 の桁数の和が 8 であり，n^2 と n^3 の各桁合わせて 1 以上 8 以下の整数がちょうど 1 個ずつ現れるようなものを全て求めよ。

  for n in 1:floor(Int, (10^8)^(1/3))
      n2n3 = string(n^2) * string(n^3)
      length(n2n3) == 8 && length(Set(n2n3)) == 8 && println(n) # 24
  end

  24

Q5.

正の整数 n は 10 個の整数 x1, x2, ..., x10 を用いて (x1^2-1)(x2^2-2)…(x10^2-10) と書ける。このような n としてありうる最小の値を求めよ。

ブルートフォースでやっつける。

  using Combinatorics
  all_perm(x, n) = Iterators.product([x for i = 1:n]...)
  function q5()
      c = 1:10
      n = typemax(Int64)
      amin = []
      for i in all_perm(0:4, 10)
          i[1] != 0 && continue
          a = [x for x in i]
          b = prod(a .^ 2 .- c)
          0 < b < n && (n = b; amin = a)
      end
      println(n)
      println(amin)
  end
  @time q5() # 84

  84
  [0, 1, 2, 1, 2, 2, 3, 3, 4, 3]
    7.724304 seconds (49.21 M allocations: 5.958 GiB, 5.45% gc time, 3.39% compilation time)