JMO2015予選第6問の解説の解説

数オリの解説の解説

数オリの解説が分かりにくすぎる!!!

ということで解説の解説と題して, 問題を解く思考過程なども加えた解説を書いていこうと思います.

JMO予選 2015 第6問

正の整数$a,b,c$が次の$4$つの条件を満たすとする:

• $a,b,c$の最大公約数は$1$である.
• $a,b+c$の最大公約数は$1$より大きい.
• $b,c+a$の最大公約数は$1$より大きい.
• $c,a+b$の最大公約数は$1$より大きい.

このとき, $a,b,c$のとりうる最小の値を求めよ.

解説
$\downarrow$
$\downarrow$
$\downarrow$
$\downarrow$
$\downarrow$
$\downarrow$
$\downarrow$
$\downarrow$
$\downarrow$
$\downarrow$
$\downarrow$
$\downarrow$
$\downarrow$
$\downarrow$
$\downarrow$
$\downarrow$
$\downarrow$
$\downarrow$

解説

[解答: 30]
$g_1=\gcd(a,b+c)$
$g_2=\gcd(b,c+a)$
$g_3=\gcd(c,a+b)$
とおく.
$g_1$と$g_2$をともに割り切る素数$p$が存在したとすると, $a,b$はともに$p$で割りきれる. さらに$b+c$は$p$で割り切れるので, $c$も$p$で割りきれて, $a,b,c$の最大公約数が$1$であることに反する.
よって$g_1$と$g_2$は互いに素である. 同様に$g_2$と$g_3$, $g_3$と$g_1$も互いに素であることがわかる.
以上と$g_1,g_2,g_3$が$1$より大きいことより, $g_1g_2g_3\geqq2\cdot3\cdot5=30$となる. さらに$g_1$は$a,b+c$をともに割りきるので, $a+b+c$を割りきる. 同様に$g_2,g_3$も$a+b+c$を割りきるので, $g_1g_2g_3$は$a+b+c$を割りきる.
よって$a+b+c\geqq g_1g_2g_3\geqq30$.
一方, たとえば$(a,b,c)=(2,3,25)$のとき問題の条件が成り立ち, $a+b+c=30$がみたされるので, 求める最小値は$30$である.

解説の解説

1. とりあえず、わからないものを文字でおく.
   $g_1=\gcd(a,b+c)$
   $g_2=\gcd(b,c+a)$
   $g_3=\gcd(c,a+b)$

• 互いに素っぽい!!
  $\rightarrow$互いに素でないことを仮定して背理法
  $g_1$と$g_2$をともに割り切る素数$p$が存在したとすると, $a,b$はともに$p$で割りきれる. さらに$b+c$は$p$で割り切れるので, $c$も$p$で割りきれて, $a,b,c$の最大公約数が$1$であることに反する.
  よって$g_1$と$g_2$は互いに素である. 同様に$g_2$と$g_3$, $g_3$と$g_1$も互いに素であることがわかる.

• 最終目標の$a+b+c$の方向へもっていきたい
  $g_1|(a+b+c),\ g_2|(a+b+c),\ g_3|(a+b+c)$が成り立つ.
  $g_1$と$g_2$, $g_2$と$g_3$, $g_3$と$g_1$が互いに素であったから, $g_1g_2g_3|(a+b+c)$である.

• 最小値を求める問題で「割りきる」, 「積」が出てきたら不等式で下からおさえてみる.
  $2\cdot3\cdot5 = 30\leqq g_1g_2g_3\leqq a+b+c$

• $2,3,5$を使っていろいろ試す.
  たぶん, 最小のときは$a$と$b$, $b$と$c$, $c$と$a$は互いに素になりそう.
  $(a,b,c)=(2,3,5)$のときダメ.
  $(a,b,c)=(4,3,5)$もダメ.
  $(a,b,c)=(2,9,5)$もダメ.
  $(a,b,c)=(4,9,5)$もダメ.
  $(a,b,c)=(2,3,25)$のとき成り立つ.

したがって答えは$30$

重要なポイント

• 互いに素は重要!
  $\rightarrow$割りきる素数$p$を仮定して背理法
• $a$が$X$を割りきる$\Rightarrow$ $a\leqq X$と評価
• $1$より大きい整数の積は素数の積(小さい順)で評価してみる