第10回和田杯解説その2

ねたばれあるぜー。

3

$x y$ 平面上においてある点が良い点であるとは，その点の $x$ 座標と $y$ 座標が共に $1$ 以上 $n$ 以下の正整数であることを指すものとする． $N$ 匹のウサギが $(1, 1)$ から $(n, n)$ まで，良い点から良い点への移動のみで移動する．また，ウサギは今いる良い点より $x$ 座標と $y$ 座標の少なくとも一方が小さい点には移動できないものとする．このとき，任意の $1 \leq i \leq j \leq n$ ， $1 \leq k \leq l \leq n$ ， $(i, k) \neq (j, l)$ をみたす整数 $i, j, k, l$ に対して， $(i, k)$ から $(j, l)$ へ移動したウサギが存在したという．ウサギの匹数としてありえる最小値を求めよ．

(雑)

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

$f (n)$ の計算がずっと合わなかった

4

$n$ を正の整数， $a$ を整数としたとき，
$\sum_{d | n} a^{d} ϕ (\frac{n}{d}) \equiv \sum_{d | n} a^{d} μ (\frac{n}{d}) (\mod n)$
が成立することを示せ．

円周上に並んでいる $n$ 個の点を $a$ 色で塗り分ける方法であって，回転させてできる $n$ 通りの塗り分け方が全て異なるものがいくつあるか考えればうまくいきます．

10

非負整数の組 $(a, b, c)$ であって，
$(a^{b} - c^{a b - a - b}) (a^{c} - b^{c}) (b^{b} - c^{a}) = 8 a b c$
をみたすものをすべて求めよ．

飛び道具を多用していきます．

a b c = 0

のとき

$c = 0$ 　 $a b - 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$

以下 $a, b, c$ は正とする．
$0$ でない整数 $n$ と $2$ 以上の整数 $x$ について $v_{x} (n)$ で $n$ が $x$ で割り切れる回数を表すとする．
両辺に $c^{a + b}$ をかけて考える． $(a^{b} c^{a + b} - c^{a b}) (a^{c} - b^{c}) (b^{b} - c^{a}) = 8 a b c^{a + b + 1}$

$gcd (a, b) = d, a = a_{0} d, b = b_{0} d$ とする．
このとき $8 a_{0} b_{0} c^{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} (L H S) \geq v_{p} (a^{c} - b^{c}) > v_{p} (d^{c}) = c v_{p} (d) > 2 v_{p} (d) = v_{p} (R H S)$
となってしまうので，解無し．したがって $c \leq 2$ とわかる．

両辺を $c^{a + b}$ でかける前の状態に戻す．

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

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

したがって $c = 2$

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

$(a^{b} - 2^{a b - a - b}) (a + b) (a - b) (b^{b} - 2^{a}) = 16 a b$
$a, b$ の大きい方が $3$ なら小さい方は $2$ で， $a + b = 5$ は $16 a b = 96$ の約数でないので大きい方は $4$ 以上．
よってカタラン予想より $| a^{b} - 2^{a b - a - b} |, | b^{b} - 2^{a} |$ は共に $2$ 以上で，もし偶数ならどちらも $4$ の倍数になる( $v_{2} (ほげごげ)$ を考える)のでいずれも $3$ 以上．
そして $a + b \geq 6$

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

もし $a^{b} > 2^{a b - a - b}$ なら $b \log_{2} a > a b - a - b$ より $\log_{2} a > a - 1 - \frac{a}{b} > a - \frac{10}{3}$ であるから $10.1 a > 2^{\frac{10}{3}} a > 2^{a}$ ．
$a \geq 9$ のとき $2^{a} = (1 + 1)^{a} > 2 a + a (a - 1) + 2 = a (a + 1) + 2 > 10.1 a$ で， $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$ が $16 a b$ を割り切らないためダメ．
$a = 5$ 　 $b^{b} > 32$ より $b \geq 4$ で， $a > b$ から $b = 4$ ．しかしそうすると $a + b$ が $16 a b$ を割り切らないためダメ．

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

12(再)

正の整数の組 $(x, y, n)$ であって，
$x^{y!} + y^{x!} = 2024^{n}$
をみたすものをすべて求めよ．

対称性より $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 (\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}$ である．
二項定理を用いて展開すればすぐに矛盾が導かれるので，解無し．