PILAME杯2025決勝　自分の問題(Day1-1,2,3,6)の解説

解答

$a_n=b_1$ となるような正の整数 $n$ のうち最小のものを $k$ とする．
　$k=1$ であるとき，$a_1=b_1$ が成り立ち，条件をみたす．
　$k>1$であるとき，$a_s=b_s$ となるような正の整数 $s$ が存在しないと仮定する．このとき，
$$a_{k-1}+b_{k-1}< a_k+b_k=b_1+b_k\leq b_{k-1}+b_k$$
より，$a_{k-1}< b_k$ である．また仮定より，$a_{k-1}\neq b_{k-1}$ でもあるので，$a_{k-1}< b_{k-1}$ である．同様に，任意の正の整数 $n$ に対して，$a_n< b_n$ ならば $a_{n-1}+b_{n-1}< a_n+b_n\leq b_{n-1}+b_n$ より $a_{n-1}< b_{n-1}$ が分かるので，帰納的に $a_1< b_1$ が従うが，$b_1$ は数列 $a_1,\,a_2,\,a_3,\,\dots$ に現れる数のうち最小のものであるので矛盾．よって，題意は示された．

解答

$p\geq q$ より，
$$a^p-1\geq a^q-1>a^q-p^b=p^a-1$$
となり，$a^p>p^a$ を得る．このとき，$(a,p)=(3,2)$ の場合を除いて $a< p$ である(以下この事実の証明.)
$p\geq 3$ であるときに $a^p>p^a$ ならば $a< p$ であることを示す．$a\geq p$ かつ$a^p\leq p^a$であることを仮定すれば，
$$(a+1)^p=a^p\left(1+\dfrac{1}{a}\right)^p\leq p^a\left(1+\dfrac{1}{p}\right)^p< p^a\left(1+\displaystyle\sum^p_{k=0}\dfrac{1}{k!}\right)< p^a×3\leq p^{a+1}$$
より，帰納的に $a\geq p$ ならば $a^p\leq p^a$ が従う．よって，$a< p$ を得る.（これはAPMO2012-3などで用いられる微分を用いない方法だが,初見で思いつく難易度は非常に高い.$a^p>p^a$ と $(\log a)/a>(\log p)/p$ が同値であることから微分を用いて示す方が無難だろう.）

$(a,p)=(3,2)$ のとき
　$p\geq q$ から $q=2$ であり，これらを与式に代入して $2^b=2$，すなわち $b=1$ である．よって，$(a,p)=(3,2)$ のとき，組 $(a,b,p,q) = (3,1,2,2)$ のみが条件をみたす．

$a< p$ のとき
　与式において $a^q+1\equiv0\pmod p$ である．ここで $a+1$ が $p$ で割り切れると仮定すると，$a< p$ より $a+1=p$ が成立するが，与式の左辺が偶数であることから $a$ は奇数であり，このことから $p$ は偶数かつ素数，すなわち $p=2$ を得る．このとき $a=1$ であり，与式の右辺は $2$ と等しいが，左辺は明らかに $2$ より大きいので矛盾．よって，$p$ は $a+1$ の約数でなくかつ $a^q+1$ の約数であるため，$a^k\equiv-1\pmod p$ が成り立つような最小の正の整数 $k$ は $1$ の約数でなく $q$ の約数であるような数，すなわち $q$ と等しい．このような $k$ は $p$ を法とした $a$ の位数の約数であり，かつ $2k$ はその倍数であるので，結局位数は $2q$ と等しい．よって $p\equiv1\pmod q$ が従い，与式の両辺の $\mathrm{mod}\ q$ を見ることで $a\equiv 1\pmod q$ がわかる．$a\neq1$ であることから $a>q$ が従うため，
$$p^q+1< p^a+1< p^a+p^b=a^q+1$$
より $p< a$ が成り立ち，$a< p$ に矛盾．よって，$a< p$ のとき，条件をみたす組はない．
　以上より，求める組は ${(a,b,p,q)=(3,1,2,2)}$ である．

解答

与式への代入を$P(a,b)$とあらわす.また,整数$N$に対して,「$N$サイクル」を,ある整数kが存在して$f^k(N)$が取りうる値全体の集合,「$N$サイクル長」を,$N$サイクルの要素数とする.(今回の文脈ではこの要素数が有限であることが証明できる.)
$P(a,0)$より$f^{f(0)}(a)=n-a$がわかる.$n-(n-a)=a$より,任意の整数$a$に対して$a$サイクル長は$2f(0)$の約数である.また,$$f(n-a)=f(f^{f(0)}(a))=f^{f(0)}(f(a))=n-f(a)$$より$f(a)+f(n-a)=n$がわかる.よって$f$は全単射より$f^{f(b)}(a)=f(n-f^{b-1}(a))=f^b(n-a)$がわかる.$f(0)\not=0$のとき,ここから任意の整数$a$に対する$a$サイクル長の最小公倍数を$l$とおけば(任意の$a$サイクル長は$2f(0)$の約数であるため,これはある$0$でない整数値であることがわかる.),$f(b)-b\equiv f(0)\pmod {l}$がわかる.また任意の$a\not=n-a$なる$a$に対して,$f^d(a)=n-a$なる最小の$d$を取ってくれば$a$サイクル長は$2d$に等しいので$l$は偶数である.$\dfrac{l}{2}$がある素数$p$で割り切れると仮定しよう.このとき,$2f(0)\equiv0\pmod l$であることから任意の$b$に対して$f(b)\equiv b\pmod p$が成立する.よって$b\equiv f(b)\equiv f(f(b))...\equiv f^{f(0)}(b)=n-b$より$p$は$n-2b$を割り切る.
$n$が奇数であるとき,$n-2b=1$なる$b$が取れ,これは素因数をもたないのでこのような$p$はとれない.よって$l=2$であり,かつ任意の$a$に対して$a\not=n-a$であるので,$f^d(a)=n-a$なる最小の$d$は$1$に等しい.よって任意の整数$a$に対して$f(a)=n-a$が成立する必要がある.逆にこのとき$b$と$n-b(=f(b))$の偶奇が異なることから$｛a,n-a｝＝｛f^b(a),f^{f(b)}(a)｝$であるので与式左辺は$a+(n-a)=n$と常に等しく,確かに条件をみたすことがわかる.
$n$が偶数のとき,$n-2b=2$なる$b$がとれるので$l$の素因数としてあり得るのは$2$のみであ,かつ$l$は$4$の約数である.$a=n-a$なる$a$が取れ,このとき$f^{f(0)}(a)=a$が成立する.またこのような$a$はただ一つだけ存在するので,$a$サイクルに整数$c(\not =a)$が含まれるならばそれと相異なる整数$n-c$も$a$サイクルに含まれ,$a$以外の$a$サイクルの要素同士でペアが作れ,$a$サイクル長が$1$より大きい奇数となるが,これは$l$が$2$以外の素数で割り切れないことに矛盾.よって$a$サイクルの要素は$a$のみであり,よって$f(a)=a$が従う.よって与式においてこのような$a$を$k$として$b$に代入すれば任意の整数$a$に対して$2f^k(a)=n$がわかるがこれは$f$が全単射であることから不合理.よってこのとき条件を
満たす全単射は存在しない.
$f(0)=0$であるとき,$b=0$として任意の整数$a$に対して$2a=n$が成立するが,これは明らかに不合理.
以上より,求めるべき全単射は$n$ が奇数のとき$f(a)=n-a$，$n$が偶数のとき存在しない.

解答

まず，以下の補題を示す．この際，$a^n+2^n+1$ やその約数を $3$ で割った余りが $2$ になるとき，$a^n+2^n+1$ は $3$ で割って $2$ 余る素因数をもつため，そのような $a$ は条件をみたさないことに注意する．
補題:条件をみたす $a$ を $18$ で割った余りは $4$ である．
証明
$a$ が奇数ならば $a^n+2^n+1$ は $2$ で割り切れるので，$a$ は偶数としてよい．
$a\equiv 0\pmod {3}$ であるとき，$a^2+2^2+1\equiv 2 \pmod 3$ となるので，条件をみたさない．また，$a\equiv 2\pmod {3}$ であるとき，$a+2+1\equiv 2 \pmod 3$ となるので，条件をみたさない．よって，$a\equiv 1\pmod {3}$ であるほかなく，$a$ が偶数であることもあわせると，$a\equiv4\pmod 6$ が必要である．
$a\equiv 10\pmod {18}$ であるとき，
$a^2+2^2+1\equiv15\ \ (\mathrm{mod}\ 18) \Rightarrow \dfrac{a^2+2^2+1}{3}\equiv5\ \ (\mathrm{mod}\ {6}) \Rightarrow \dfrac{a^2+2^2+1}{3}\equiv2\ \ (\mathrm{mod}\ {3})$
となり，条件をみたさない．$a\equiv 16\pmod {18}$ であるとき，
$a^4+2^4+1\equiv33\ \ (\mathrm{mod}\ {18}) \Rightarrow \dfrac{a^4+2^4+1}{3}\equiv 11\ \ (\mathrm{mod}\ 6) \Rightarrow \dfrac{a^4+2^4+1}{3}\equiv 2\ \ (\mathrm{mod}\ {3}$
となり，条件をみたさない．以上より，$a\equiv 4\pmod {18}$ であるほかなく，補題が示された．

　次に，$a$ が $2$ でちょうど $1$ 回割り切れるとして矛盾を導く．
このとき，奇数 $A$ を用いて $a=2A$ と表せる．補題より $a\equiv 4\pmod {18}$ なので，$A\equiv 2 \pmod 9$ である．よって，$(2A)^2+A^2+1\equiv 3\pmod 9$ が成り立ち，$A$ が奇数であることから
$(2A)^2+A^2+1\equiv2\pmod 4$ が成り立つため，$\dfrac{(2A)^2+A^2+1}{6}$ は $3$ で割って $2$ 余る奇数である．よって，$\dfrac{(2A)^2+A^2+1}{6}$ は $3$ で割って $2$ 余る奇数の素因数 $p$ をもつ．
ここで，$p$ と $a$ は互いに素であるから，Fermat の小定理より
$a^{2p-4}+2^{2p-4}+1\equiv a^{-2}\left(1+A^2+(2A)^2\right)\equiv 0\pmod p$
が成り立つため，$p$ は $a^{2p-4}+2^{2p-4}+1$ を割り切るが，これは条件に矛盾．
　したがって，補題より，$a$ が $2$ で $1$ 回以上割り切れることもあわせると，$a$ は $2$ で $2$ 回以上割り切れることが分かり，題意は示された．