RELSMO2024 問7を解読する！

180

　お久しぶりです　ぴーです

　以前AoPSを漁っていたらこんなものを見つけまして...
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・

RELSMO2024 問7

Prove that
$\begin{aligned} &\forall n\in\mathbb{Z}^+_0:(\exists b\in\mathbb{Z}^+_0:(\forall m\in\mathbb{Z}^+_0:((\exists x\in\mathbb{Z}^+_0:(x+m = b))\lor(\exists s\in\mathbb{Z}^+_0:(\exists p\in\mathbb{Z}^+_0:((\neg(\exists x\in\mathbb{Z}^+_0:(p+x = 1)))\\ &\land(\neg(\exists x\in\mathbb{Z}^+_0:(\exists y\in\mathbb{Z}^+_0:(p = (x+2) \cdot (y+2)))))\land(\exists x\in\mathbb{Z}^+_0:(p = m+x+1))\land(\exists r\in\mathbb{Z}^+_0:((\forall x\in\mathbb{Z}^+_0:\\ &(\forall y\in\mathbb{Z}^+_0:((\neg(x \cdot y = r))\lor(x = 1)\lor(\exists z\in\mathbb{Z}^+_0:(x = z \cdot p)))))\land(\exists x\in\mathbb{Z}^+_0:(\exists y\in\mathbb{Z}^+_0:((\exists z\in\mathbb{Z}^+_0:(r = y+z+1))\\ &\land(s = r \cdot (p \cdot x + m) + y))))))\land(\forall u\in\mathbb{Z}^+_0:((\exists x\in\mathbb{Z}^+_0:(u = p+x))\lor(u = 0)\lor(u = n+1)\lor(\neg(\exists r\in\mathbb{Z}^+_0:\\ &((\forall x\in\mathbb{Z}^+_0:(\forall y\in\mathbb{Z}^+_0:((\neg(x \cdot y = r))\lor(x = 1)\lor(\exists z\in\mathbb{Z}^+_0:(x = z \cdot p)))))\land(\exists x\in\mathbb{Z}^+_0:(\exists y\in\mathbb{Z}^+_0:((\exists z\in\mathbb{Z}^+_0:\\ &(r = y+z+1))\land(s = r \cdot (p \cdot x + u) + y)))))))\lor(\exists v\in\mathbb{Z}^+_0:(\exists k\in\mathbb{Z}^+_0:((\neg(v = 0))\land((u = v \cdot (k+2))\\ &\lor(u = v \cdot (k+2) + 1))\land(\exists r\in\mathbb{Z}^+_0:((\forall x\in\mathbb{Z}^+_0:(\forall y\in\mathbb{Z}^+_0:((\neg(x \cdot y = r))\lor(x = 1)\lor(\exists z\in\mathbb{Z}^+_0:(x = z \cdot p)))))\\ &\land(\exists x\in\mathbb{Z}^+_0:(\exists y\in\mathbb{Z}^+_0:((\exists z\in\mathbb{Z}^+_0:(r = y+z+1))\land(s = r \cdot (p \cdot x + v) + y))))))))))))))))) \end{aligned}$

AoPSにLatexコード表示機能があってまじで良かったなと思ってます　感謝

それはそうとして、まぁ見るからにやばいですね　難問とかいう次元じゃないですそもそもなんの分野なんでしょうか

ということで、これを解読していきたいと思います

そもそもRELSMOって？

　の前に、ほとんどの人はRELSMOを知らないと思うので(僕もこれを見つけて初めて知った)説明します

　まず ELMO (Experimental Lincoln Math Olympiad)というアメリカの数オリがあります
　問題はAoPS→USA Contests→MOP Contestsから見れるので、もしかしたら見かけたことある人もいるかもしれません
　この大会は1チーム約6~7人のチーム戦であり、毎年AoPSで募集がかけられています　非公式(?)だけど問題はちゃんとしてる
　正直情報源が少なくて真偽も微妙なので詳しくは上のリンクから見てください

　まぁそんな感じのELMOですが、こんな説明が書いてあります DeepLに突っ込んだ

　簡単にまとめると、ELSMOとRELMO(RELSMO)はおふざけ数学コンです
　実際に見てみると、ELSMOは問題用紙がふざけてます
　問題自体はELMOと同じです(例外有) 2017年　これでもまだ優しい方
　2012年から開催されていて、解読難易度は
(2012)<2014<2013<2016<2021<2023<2020<2017<2019<2018<2022
　です　これを解読するのも面白いかも？

　一方、RELMO(RELSMO)は大学数学を使ったり、知識一発ゲーだったり、普段なら出題されないような問題が出題されています
　比較的新しく、2022年から始まっています

RELMO 2024 P7

不等辺三角形$ABC$が描かれており，エルモはその内心$I$，フォイエルバッハ点$X$，ナーゲル点$N$に印をつけた。悲しいことに，abcdEfghijkLMnOpqrstuvwxyzを取った後、エルモは三角形$ABC$を失ってしまった。エルモは定規とコンパスだけで三角形を復元できるか？

　問題文おかしいですがそのまま書いてあったので...
　この問題も深く考えないほうがいいです
　解説はAoPSから見れます

解読その１

　前置きはこれくらいにして、いよいよ解読に入りましょう

　文字列をよく見てみると、$\cdots\exists x\in\mathbb{Z}^+_0:(\exists y\in\mathbb{Z}^+_0:((\exists z\in\mathbb{Z}^+_0:\cdots$のようなものは
$\cdots\exists x,y,z\in\mathbb{Z}^+_0\cdots$とまとめられるので、こうなります

$\begin{aligned} &\forall n\in\mathbb{Z}^+_0:(\exists b\in\mathbb{Z}^+_0:(\forall m\in\mathbb{Z}^+_0:((\exists x\in\mathbb{Z}^+_0:(x+m = b))\lor(\exists s,p\in\mathbb{Z}^+_0:((\neg(\exists x\in\mathbb{Z}^+_0:(p+x = 1)))\\\\ &\land(\neg(\exists x,y\in\mathbb{Z}^+_0:(p = (x+2) \cdot (y+2))))\land(\exists x\in\mathbb{Z}^+_0:(p = m+x+1))\land(\exists r\in\mathbb{Z}^+_0:((\forall x,y\in\mathbb{Z}^+_0:\\\\ &((\neg(x \cdot y = r))\lor(x = 1)\lor(\exists z\in\mathbb{Z}^+_0:(x = z \cdot p))))\land(\exists x,y\in\mathbb{Z}^+_0:((\exists z\in\mathbb{Z}^+_0:(r = y+z+1))\land\\\\ &(s = r \cdot (p \cdot x + m) + y)))))\land(\forall u\in\mathbb{Z}^+_0:((\exists x\in\mathbb{Z}^+_0:(u = p+x))\lor(u = 0)\lor(u = n+1)\lor(\neg(\exists r\in\mathbb{Z}^+_0:\\\\ &((\forall x,y\in\mathbb{Z}^+_0:((\neg(x \cdot y = r))\lor(x = 1)\lor(\exists z\in\mathbb{Z}^+_0:(x = z \cdot p))))\land(\exists x,y\in\mathbb{Z}^+_0:((\exists z\in\mathbb{Z}^+_0:\\\\ &(r = y+z+1))\land(s = r \cdot (p \cdot x + u) + y))))))\lor(\exists v,k\in\mathbb{Z}^+_0:((\neg(v = 0))\land((u = v \cdot (k+2))\lor\\\\ &(u = v \cdot (k+2) + 1))\land(\exists r\in\mathbb{Z}^+_0:((\forall x,y\in\mathbb{Z}^+_0:((\neg(x \cdot y = r))\lor(x = 1)\lor(\exists z\in\mathbb{Z}^+_0:(x = z \cdot p))))\land\\\\ &(\exists x,y\in\mathbb{Z}^+_0:((\exists z\in\mathbb{Z}^+_0:(r = y+z+1))\land(s = r \cdot (p \cdot x + v) + y)))))))))))))) \end{aligned}$

　次で解読の半分くらい進んじゃいますが、実は問題文をよくよく見てみると、2行目の終わりから
$$\begin{aligned} &(\exists r\in\mathbb{Z}^+_0:((\forall x,y\in\mathbb{Z}^+_0:((\neg(x \cdot y = r))\lor(x = 1)\lor(\exists z\in\mathbb{Z}^+_0:(x = z \cdot p))))\\\\ &\land(\exists x,y\in\mathbb{Z}^+_0:((\exists z\in\mathbb{Z}^+_0:(r = y+z+1))\land(s = r \cdot (p \cdot x + m) + y))))) \end{aligned}$$
　4行目の終わりから
$$\begin{aligned} &(\exists r\in\mathbb{Z}^+_0:((\forall x,y\in\mathbb{Z}^+_0:((\neg(x \cdot y = r))\lor(x = 1)\lor(\exists z\in\mathbb{Z}^+_0:(x = z \cdot p))))\\\\ &\land(\exists x,y\in\mathbb{Z}^+_0:((\exists z\in\mathbb{Z}^+_0:(r = y+z+1))\land(s = r \cdot (p \cdot x + u) + y))))) \end{aligned}$$
　7行目の前半から
$$\begin{aligned} &(\exists r\in\mathbb{Z}^+_0:((\forall x,y\in\mathbb{Z}^+_0:((\neg(x \cdot y = r))\lor(x = 1)\lor(\exists z\in\mathbb{Z}^+_0:(x = z \cdot p))))\\\\ &\land(\exists x,y\in\mathbb{Z}^+_0:((\exists z\in\mathbb{Z}^+_0:(r = y+z+1))\land(s = r \cdot (p \cdot x + v) + y))))) \end{aligned}$$

　と、ほとんど同じ文字列が繰り返されています(最後が$m,u,v$かの違いのみ)
　これをそれぞれ$\mathrm{P_m}$、$\mathrm{P_u}$、$\mathrm{P_v}$と置いちゃいましょう
　さらに$\forall n\in\mathbb{Z}^+_0:(\exists b\in\mathbb{Z}^+_0:(\forall m\in\mathbb{Z}^+_0:$は問題文全体に掛かっているので以下のように書き直せます。

　$n$を非負整数とする．ある非負整数$b$が存在して，任意の非負整数$m$に対して以下を満たすことを示せ．
$\begin{aligned} &(\exists x\in\mathbb{Z}^+_0:(x+m = b))\lor(\exists s,p\in\mathbb{Z}^+_0:((\neg(\exists x\in\mathbb{Z}^+_0:(p+x = 1)))\\\\ &\land(\neg(\exists x,y\in\mathbb{Z}^+_0:(p = (x+2) \cdot (y+2))))\land(\exists x\in\mathbb{Z}^+_0:(p = m+x+1))\land\mathrm{P_m} \land(\forall u\in\mathbb{Z}^+_0:\\\\ &((\exists x\in\mathbb{Z}^+_0:(u = p+x))\lor(u = 0)\lor(u = n+1)\lor(\neg\mathrm{P_u})\lor(\exists v,k\in\mathbb{Z}^+_0:((\neg(v = 0))\land((u = v \cdot (k+2))\lor\\\\ &(u = v \cdot (k+2) + 1))\land\mathrm{P_v})))))) \end{aligned}$
　ただし$\mathrm{P_\alpha}$は
$$\begin{aligned} &(\exists r\in\mathbb{Z}^+_0:((\forall x,y\in\mathbb{Z}^+_0:((\neg(x \cdot y = r))\lor(x = 1)\lor(\exists z\in\mathbb{Z}^+_0:(x = z \cdot p))))\\\\ &\land(\exists x,y\in\mathbb{Z}^+_0:((\exists z\in\mathbb{Z}^+_0:(r = y+z+1))\land(s = r \cdot (p \cdot x + \alpha) + y))))) \end{aligned}$$
　とする．

　かなりスッキリしました(?)ね

解読その２

　ここからは数学的考察を含んだ解読をしていきます

　まず
$\exists x\in\mathbb{Z}^+_0:(x+m = b)$(一行目)
$\neg(\exists x\in\mathbb{Z}^+_0:(p+x = 1))$(一行目)
$\neg(\exists x,y\in\mathbb{Z}^+_0:(p = (x+2) \cdot (y+2)))$(一行目)
$\exists x\in\mathbb{Z}^+_0:(p = m+x+1)$(二行目)
$\exists x\in\mathbb{Z}^+_0:(u = p+x)$(三行目)
$\neg(v = 0)$(三行目)
$\exists z\in\mathbb{Z}^+_0:(r = y+z+1)$($\mathrm{P_\alpha}$二行目)

　はそれぞれ
$m\leq b$
$p\gt 1$
$p$は素数
$p\gt m$
$u\geq p$
$v\not= 0$
$r\gt y$
　と同値です。言われてみれば問題文に$\not=$と不等号は出てきてなかったので、これが諸悪の根源ですね

　また括弧を頑張って追っていくと、問題文の構造は
「$(\exists x\in\mathbb{Z}^+_0:(x+m = b))$または(以下すべて)」すなわち
「$m\leq b$または(以下すべて)」だとわかるので、以下に書き換えられます

問題名（任意）

　$n$を非負整数とする．ある$b\in\mathbb{Z}^+_0$が存在して，$b$より大きい任意の$m\in\mathbb{Z}^+_0$に対して以下を満たすことを示せ．
$\begin{aligned} &\exists s,p\in\mathbb{Z}^+_0:((p\gt 1)\land(p:prime)\land(p\gt m)\land\mathrm{P}\land(\forall u\in\mathbb{Z}^+_0:\\\\ &((u\geq p)\lor(u = 0)\lor(u = n+1)\lor(\neg\mathrm{P})\lor(\exists v,k\in\mathbb{Z}^+_0:((v\not=0)\land((u = v \cdot (k+2))\lor\\\\ &(u = v \cdot (k+2) + 1))\land\mathrm{P}))))) \end{aligned}$
　ただし$\mathrm{P_\alpha}$は
$$\begin{aligned} &(\exists r\in\mathbb{Z}^+_0:((\forall x,y\in\mathbb{Z}^+_0:((\neg(x \cdot y = r))\lor(x = 1)\lor(\exists z\in\mathbb{Z}^+_0:(x = z \cdot p))))\\\\ &\land(\exists x,y\in\mathbb{Z}^+_0:((r\gt y)\land(s = r \cdot (p \cdot x + v) + y))))) \end{aligned}$$
　とする．

解読その３

　ここまで解読できてもまだややこしいのは中括弧や大括弧が使われていないからだと思うんですが、何重にも重なっているので使っても意味ないんですよね...　

　次に、問題文の後半
$\begin{aligned} &\forall u\in\mathbb{Z}^+_0:((u\geq p)\lor(u = 0)\lor(u = n+1)\lor(\neg\mathrm{P})\\ &\lor(\exists v,k\in\mathbb{Z}^+_0:((v\not=0)\land((u = v \cdot (k+2))\lor(u = v \cdot (k+2) + 1))\land\mathrm{P}))) \end{aligned}$
　を考えます。

　まず、構造としては
$\forall u\in\mathbb{Z}^+_0:((u\geq p)\lor(u = 0)\lor(u = n+1)\lor(\neg\mathrm{P})$または(ほげほげ)
　となり、これは
「$p$未満の正整数$n$で$u\not=n+1$かつ$P_n$を満たすものすべてに対して、(ほげほげ)が成り立つ」
　と同値です。
　ここで、$n\in\mathbb{Z}^+_0$だったのを$n\in\mathbb{N}$とし、$u\not=n$に変えればスッキリします。

　次に、$\mathrm{P_\alpha}$について考えます。

$\begin{aligned} \mathrm{P_\alpha}:&(\exists r\in\mathbb{Z}^+_0:((\forall x,y\in\mathbb{Z}^+_0:((\neg(x \cdot y = r))\lor(x = 1)\lor(\exists z\in\mathbb{Z}^+_0:(x = z \cdot p))))\\\\ &\land(\exists x,y\in\mathbb{Z}^+_0:((r\gt y)\land(s = r \cdot (p \cdot x + \alpha) + y))))) \end{aligned}$

　まず、$\forall x,y\in\mathbb{Z}^+_0:((\neg(x \cdot y = r))\lor(x = 1)\lor(\exists z\in\mathbb{Z}^+_0:(x = z \cdot p)))$の部分は
「$xy=r$を満たす任意の非負整数$x,y$に対して、$x=1$もしくは$x$は$p$の倍数である」
となります。これはずばり$r$が$p$の累乗であることと同値ですね

　次に、$\exists x,y\in\mathbb{Z}^+_0:((r\gt y)\land(s = r \cdot (p \cdot x + \alpha) + y))$の部分は、$r=p^k$としたとき$s$を$p$進数で表した時の$p^k$の位が$\alpha$ということなので、全体としては
「$s$を$p$進数表示した時、$\alpha$が現れる」
となります。

　またこれは$\alpha=0$のとき必ず真ですが、$m,u,v\not=0$が保証されているので大丈夫です。
　以上を踏まえると

　$n$を正整数とする．ある$b\in\mathbb{Z}^+_0$が存在して，$b$より大きい任意の$m\in\mathbb{Z}^+_0$に対して以下を満たすことを示せ．

・$s$を$p$進数表示したときに$m$が現れるよう非負整数$s$と素数$p\gt m$が存在して、$s$の$p$進数表示に現れる正整数$u\not=n$を任意にとると、以下を満たす．
$\begin{aligned} \exists v,k\in\mathbb{Z}^+_0:((v\not=0)\land((u = v \cdot (k+2))\lor(u = v \cdot (k+2) + 1))\land\mathrm{P_v}) \end{aligned}$

　最後に、$\exists v,k\in\mathbb{Z}^+_0:((v\not=0)\land((u = v \cdot (k+2))\lor(u = v \cdot (k+2) + 1))\land\mathrm{P_v})$は
「$s$の$p$進数表示に現れる正整数$v$であって、$u=vk$または$u=vk+1$($k$は$2$以上の整数)を満たすものが存在する」
となります。

　以上より

$s$を$p(\gt\alpha)$進数表示したときに数$\alpha$が現れるとき，$\alpha$は良い数であるとする．

$n$を正整数とする．ある非負整数$b$が存在して，$b$より大きい任意の整数$m$に対して以下を満たすことを示せ．
・$m$が良い数となるような非負整数$s$と$p$が存在して，「$n$と異なる良い数$u$を任意にとった時，$2$以上の整数$k$が存在して$u=vk$または$u=vk+1$を満たす良い数$v$が存在する