第10回和田杯解説その2

ある良い点の組が良い組であるとは，一方の点からもう一方の点にウサギが移動できることをいう．
直線$l:x+y=n+\frac{1}{2}$について，ウサギは一度この直線を超えると戻ってくることはできない．したがってこの直線をまたぐような良い組の数を考えるとそれはウサギの匹数以下である．
(ここの計算をしたくないので読者の課題とし，その組数を$f(n)$とする．)
任意の$l$より下の点について，一方がその点であるような良い組のうち，「その点の方が右上側にあるものの数」は「$l$をまたぐ物の数」以下であるため，($l$より上の点についても同様に行えば，)$f(n)$が最小値であることが従う．

• $c=0$　$ab-a-b\geq 0$でさえあれば$a^0-b^0=0$より式を満たす．よって$a,b$はどちらも$0$またはどちらも$2$以上．
• $c\neq 0,b=0$　$(1-c^{-a})a^c(1-c^a)=0$より$a=0$または$c=1$．
• $b,c\neq 0,a=0$　$b^b-1=0$より$b=1$

$\gcd (a,b)=d,a=a_0d,b=b_0d$とする．
このとき$8a_0b_0c^{a+b+1}d^2$は$(a_0^c-b_0^c)$の倍数．
$c\geq 3$とするとジグモンディーの定理より例外($\{a_0,b_0\}=\{1,2\}$,$c=6$)を含めて$a_0^c-b_0^c$は$a_0,b_0,c$のいずれとも互いに素な奇素数$p$を持つ(例外の場合は$p=7$)ので，右辺が$p$で割り切れるために$d$が$p$の倍数となる．
$v_p(LHS)\geq v_p(a^c-b^c)>v_p(d^c)=cv_p(d)>2v_p(d)=v_p(RHS)$
となってしまうので，解無し．したがって$c\leq 2$とわかる．

$c=1$とすると，$(a^b-1)(a-b)(b^b-1)=8ab$．正負を考えて$a>b$．

• $b\geq 3$　$LHS\geq (a^3-1)(27-1)>13a^3>8a^2>RHS$
• $b=2$　$(a-1)(a+1)(a-2)3=16a$より$a$は$3$の倍数．
  $a=3$は代入すると違うので$a\geq 6$．
  $LHS\geq 5(a+1)4\cdot 3=60a$より解無し．

したがって$c=2$

$b=1$とすると正負から明らかに矛盾．
$a=1$とすると正負から$b^b< c$である必要があるが，$b\neq 1$より$b^b\geq 4>2=c$より矛盾．
よって$a,b$は$2$以上で，$ab-a-b$は非負．

もし$a< b$なら$b^b-2^a>b^b-b^a\geq b^{b-1}$，$16ab<16b^2$であるため$3\cdot 5\cdot b^{b-1}<16b^2$となり，これを満たすのは$b<4$のみ．
なぜなら$b\geq 4$では$15\cdot b^{b-1}\geq 15\cdot b\cdot b^2>16b^2$であるから．
しかし$a,b$の大きい方は$4$以上であるから，解無しとなる．
よって$a>b$
$3(a^2-b^2)3\leq 16ab$より$a\leq \frac{8+\sqrt{145}}{9}b<\frac{7}{3}b$である．

もし$a^b>2^{ab-a-b}$なら$b\log_2a>ab-a-b$より$\log_2a>a-1-\frac{a}{b}>a-\frac{10}{3}$であるから$10.1a>2^{\frac{10}{3}}a>2^a$．
$a\geq 9$のとき$2^a=(1+1)^a>2a+a(a-1)+2=a(a+1)+2>10.1a$で，$a=8,7,6$も満たさない(式は略)ので$a<6$．$a$は$4$以上なので$a=4,5$．
正負を考えて$b^b>2^a$である．

• $a=4$　$b^b>16$より$b\geq 3$で，$a>b$から$b=3$．しかしそうすると$a+b$が$16ab$を割り切らないためダメ．
• $a=5$　$b^b>32$より$b\geq 4$で，$a>b$から$b=4$．しかしそうすると$a+b$が$16ab$を割り切らないためダメ．

故に$a^b<2^{ab-a-b}$．したがって正負から$b^b<2^a$．
よって$b\log_2b< a<\frac{7}{3}b$より，$b<2^{\frac{7}{3}}$であるから，$b=2,3,4,5$．
$b^b<2^a,3a<7b$より$(a,b)=(3,2),(4,2),(5,3),(6,3),(9,4)$
このうち$a+b$が$16ab$を割り切るのは$(a,b)=(5,3),(6,3)$．$(a,b)=(6,3)$は$2^a-b^b=37$が$16ab$を割り切らないのでみたさない．
$a=5,b=3$は式を満たすので，$(a,b,c)=(5,3,2)$．

対称性より$x\geq y$としよう．
$y=1$なら$x=2024^n-1$だ．
$x,y$がいずれも$2$以上の場合を考える．
$x^{y!},y^{x!}$はどちらも平方数で，平方数を$11$で割った余りは$0,1,3,4,5,9$のいずれかであるため平方数の和が$11$の倍数になるためにはその平方数がいずれも$11$の倍数でなければならない．
(フェルマーの二平方和定理とか平方剰余の第一補充法則とか使うのが王道，フェルマーの小定理から示してもよい．)
したがって$x,y$はいずれも$11$の倍数なので$11$以上．
フェルマーの小定理より$x^{y!}+y^{x!}\equiv 0,1,2(\mathrm{mod}\ 5)$であるため，$n$は偶数である．
したがって$x^{y!}=(2024^{n/2}-y^{x!/2})(2024^{n/2}+y^{x!/2})\geq 2024^{n/2}+y^{x!/2}>y^{x!/2}$
ここで$x=y$なら左辺の$2$で割れる回数が$3$の倍数でないことから矛盾するため$x>y$．よって
$x>y^{\frac{x!}{2\cdot y!}}\geq y^{x/2}\geq 11^{x/2}$，$x^2>11^x$である．
二項定理を用いて展開すればすぐに矛盾が導かれるので，解無し．