mapleの自由帳

数学と音楽に生きています。

EGMO2020一次選抜を解いてみた

数オリ

　多くの人にとって数オリシーズンの到来を感じるのは年明けとかかなと思いますが、実は一部の戦いは既に始まっています。EGMO系の問題は教育的なものも多く、その点では今年のセットは(少し簡単ではありましたが)比較的良質だと思います。
　この記事では問題を解き進めるうえでの「お気持ち」を中心にかなり丁寧に書いたつもりです。EGMO一次選抜は公式に解答を得ることが出来ないので(受験者にのみ配布されるようですが)、そういう意味でも参考になれば良いかなと思います。
　※この記事は盛大なネタバレを含みます。問題は以下のリンクに公開されているので、一度チャレンジしてから読むことをオススメします。
https://www.imojp.org/archive/mo2020/jegmo2020/problems/jegmo9q.jpg

問1

　素直な見た目のNです。これは極論なのですが、「分数式が整数である」という形の問題ではとりあえず以下の不等式評価を連想しましょう。

整数 x, y について \displaystyle \frac{x}{y} が整数であるとき、x=0 または |x|\geq|y|

　与式は a と b について対称なので、一般性を失わず a\geq b として考えます(こういう限定の付け方も大事です)。現時点では基本的に分子の方がずっと大きそうなので、まずは適当に整数を括り出してくる発想には多くの人が至るでしょう。
　しかし、例えば以下のような変形をしても(解けるとは思いますが)見通しは良くないです。分子を十分に小さく出来ていないからです。

\displaystyle\frac{2^{a+b}+1}{2^{a}+2^{b}+1}=2^{b}-\frac{2^{2b}+2^{b}-1}{2^{a}+2^{b}+1}

　ポイントは分母が奇数であることです。つまり分子は 2 で完全に割り切って考えられるので、以下は好手です。
\displaystyle\frac{2^{a+b}+1}{2^{a}+2^{b}+1}=1+\frac{2^{a+b}-2^{a}-2^{b}}{2^{a}+2^{b}+1}

　したがって分子から 2^{b} を括り出すことで、題意は\displaystyle\frac{2^{a}-2^{a-b}-1}{2^{a}+2^{b}+1}が整数であることと同値とわかります。ここまで来れば上で述べた不等式評価が使えます。すなわち分母・分子ともに非負で明らかに分子の方が小さいので、 2^{a}-2^{a-b}-1=0 が必要十分条件になるとわかります。これが成立するのは a=1 かつ b=1 の場合のみです。
　ちなみに与式の 2 を一般に n\geq2 に置き換えても同様に解くことが出来ます。

問2

　個人的にEGMO系のCは全体的にクセが強い印象があります。特に(ドミノ含む)マス目の問題が大好きなように見えますが気のせいでしょうか？
　問題文が少しわかりにくいですが、落ち着いて読解しましょう(誤読は悲惨です)。要するに、以下のような配置を要求されています。それぞれ k=1,2 の一例です。

f:id:fuma_maple:20191127162031p:plainf:id:fuma_maple:20191127162424p:plain
　以降ではピースを置くマスを青で、特に中心を赤で塗るとして考えることにします。

解法1

　上の図を見る限り k=2 の時点で白マスがかなり少なくなっており、これよりサイズを大きくすることは明らかに厳しそうです。まずはこの方針で k=3 が不可能なことを示しましょう。これが示されれば当然 k\geq4 でも不可能となります。
　9\times 9 のマス目からはみ出す青マスがいくつかあります。これは少し観察すれば具体的に計算出来て、各辺について 3+2+1 マスですから全体では 24 マスです。また各ピースは 13 マスから成るので、9\times 9 のマス目のうち 13\times9-24=93 マスが重複無く塗られる必要があります。これは明らかに不適ですね。

解法2

　しかし k=2 での構成がそこまですんなり思い付けるとは限りません。そもそも実際に 9\times9 のマス目を書いて実験するのは、やや手間がかかって非効率です(もちろん実際の試験ではこの程度やるに越したことは無いですが)。ここでは条件を式の形に言い換えましょう。
　マス目を (x, y) の形で表現します。いま (x, y) を赤で塗ったとき、対応する青マスは (x\pm i, y), (x, y\pm i)\ (i=1,\cdots,k) と表されます。したがって (x_{1}, y_{1}), (x_{2}, y_{2}) をそれぞれ中心とするピースが重なる条件は、問題の条件より x_{1}\neq x_{2} および y_{1}\neq y_{2} であることに留意すると、

|x_{1}-x_{2}|\leq k かつ |y_{1}-y_{2}|\leq k
と表現できます。k=2 のときこれを回避するように(例えば左側から)赤マスを決めていくと、以下が見つかります。
(1,7),(2,4),(3,1),(4,8),(5,5),(6,2),(7,9),(8,6),(9,3)
これは上の図に対応しています。こちらの方が、実際にマス目を使うよりかは手を動かしやすいのではないかと思います。
　同様にして k=3 で不可能なことも示せます。例えば y 座標が 3 の赤マスに注目し、その x 座標が X であるとします。X\leq5であるとき、赤マスとしては (X+1, 6), (X+2, 9) または (X+1, 9), (X+2, 6) しかあり得ませんが、このとき x 座標が X+3 の赤マスが存在できません。X\geq5 のときも同様です。
　Cのこのタイプの証明は「感覚的にやりたいことはわかるがどう書いて良いかわからない」という人も多いと思います。ふんわりした記述は大幅な失点の元です。厳密に数学的に表現できるような定量を頑張って発見しましょう。

問3

　フリーハンドでも普通に描けるレベルの図ですね。Gに強い人なら別に良いんですが、僕のように残念ながらそうではないなら、常に一度は定規・コンパスを使って作図してみることをお勧めします。正確な図なら見えているかもしれない事実に、どうしても気付けなかったりします。
f:id:fuma_maple:20191127190829p:plain

初等解

　とりあえず角度計算をしてみましょう。\angle BAD=2\theta とおくと、 BC=BE より \angle BEC=\angle ABC/2=90^{\circ}-\theta で \angle BAX=90^{\circ}-\angle BEC=\theta です。さらに AX=EX より \angle AXE=180^{\circ}-2\angle BAX=180^{\circ}-2\theta です。
　ところで示すべき条件は \angle BXD=180^{\circ}-2\theta と同値なので、\angle AXE=\angle BXD が成立すれば良いことになります。この辺りからなんとなく点 X まわりの回転相似の気配を感じてきませんか...？
　ここで長さの条件が効いてきます。幸いにして AD=BE かつ AX=EX が条件として与えられているので、これらの挟む角がわかれば良いですが、既にありますね。 \angle BEX=\angle BAX = \theta = \angle BAD-\angle BAX=\angle DAX なので、結局のところ三角形 ADX と EBX の合同が従います。よって \angle AXD=\angle BXE で、直ちに \angle AXE=\angle BXD が示されました。あるいは \angle ADX=\angle EBX からでも良いですね。
　勘の良い人なら同じ点まわりの等辺条件を見た瞬間に回転合同だと察せるのかもしれないですね。とはいえ今回は角度が簡単にたくさん計算できるので、すぐにブレイクスルーに至らなくてもとりあえず地道にやってみると良いと思います。

複素解

　しかしながら、もし初等で考察しても何も見えてこなかったとき、複素計算は我々の強い味方です(基礎は獲得など参照)。特に今回は基本的な計算のみで処理できますが、問題は「座標の設定」です。ここで工夫するだけでも(本質的に同じ計算をしていても)作業量が劇的に変わってきます。
　見るからに長さの条件がネックになりそうなので、直線 ABE を実軸に設定するとスムーズです。t を実数として A(0), B(t), D(\alpha) とおくと C は \alpha+t と表せます。さらに今回はスケール変換が許されるので |\alpha|=1 とすれば E は t+1と表せ、AE の中点 M は (t+1)/2 です。\overline{\alpha}=1/\alpha に留意してください。
　X の座標を z としましょう。まず AX\perp CEより

\displaystyle\frac{z-0}{(\alpha+t)-(t+1)}\in \mathbb{R}i \Longleftrightarrow \frac{z}{\alpha-1}+\frac{\alpha\overline{z}}{1-\alpha}=0 \Longleftrightarrow z=\alpha\overline{z}

また MX\perp ABより
\displaystyle\frac{z-\frac{t+1}{2}}{t-0}\in\mathbb{R}i \Longleftrightarrow \frac{z-\frac{t+1}{2}}{t}+\frac{\overline{z}-\frac{t+1}{2}}{t}=0 \Longleftrightarrow z+\overline{z}=t+1

　これらを連立させることで \displaystyle z=\frac{\alpha(t+1)}{\alpha+1} がわかります。いま示すべき事実は A,B,D,X の共円で、これは以下と同値です。
\displaystyle\frac{\alpha-t}{\alpha-0}\cdot\frac{z-0}{z-t}\in\mathbb{R}
これを計算するとめでたく実数 t+1 となり、証明終了です。かなりシンプルな計算でしたが、適当に座標を設定してしまうと爆発しかねないと思います。図の自由度を慎重に見極めましょう。

問4

　EGMO自体へのFE(関数方程式)の出題は珍しくないですが、一次選抜では6年目にして初の出題となりました。あまり対策出来ず少し面食らってしまった人も多いのではないでしょうか(僕も普通に驚きました)。しかし今回はFEらしい議論は実はほぼ必要ありません。根本的に考えるべきことは問1と同じです。
　最初に解の予想を立ててみることは大切です。f(n)=n+1 をすぐに発見できるのでは無いでしょうか。実際のところ解はこれだけなのでそれを示しに行きましょう。

解法1

　とりあえず具体的代入を色々試みても上手く行かないでしょう。分子の f(f(n)) が明らかに邪魔だからです。これを無理やり作りに行きたいので、m に f(n) を代入してみます。すると以下が整数とわかります。

\displaystyle\frac{f(n)+f(f(n))}{f(f(n))+n+1}=1+\frac{f(n)-n-1}{f(f(n))+n+1}

　特に左辺より f(n)\geq n+1 がわかります。n を f(n) に置き換えて考えることで f(f(n))\geq f(n)+1 でもあるので、これらを右辺に適用すれば 0\leq f(n)-n-1\lt f(n)+n+2\leq f(f(n))+n+1 がわかります。よって問1と同様にして、任意の n について f(n)-n-1=0 が成立することがわかりました。
　十分性の確認を答案に添えるのを忘れないようにしましょう(あくまでここまで確かめたのは必要性です)。自明だと失念されがちなのですが、思わぬ失点に繋がります。防げる失点は防ぎましょう。

解法2

　実際には離散型のFEが上の解法ほど何事もなく解けてしまうことは少ないです。ここではより応用の効きそうな別解を紹介します。
　N要素の絡むFEを解く上で、特に重要なポイントの一つが「素数」です。例えば今回のように「分数式が整数である」タイプの問題だと、分子を素数 p に出来てしまえば分母は \pm p,\pm1に限定できるわけです。
　そこで無理やりではありますが分子を素数にしてしまいましょう。十分大きい素数 p について m=p-f(f(n)) を代入すると、分母は明らかに 1 より大きいですから f(p-f(f(n)))+n+1=p がわかります。
　なんとか具体的な等式が得られたので、これを利用できるような代入を考えましょう。いくつか方法はありますが、ここでは m=p-k-1, n=p-f(f(k)) としてみます。このとき以下が整数となります。

\displaystyle\frac{p-k-1+f(p-k-1)}{f(p-k-1)+p-f(f(k))+1}=1+\frac{f(f(k))-k-2}{f(p-k-1)+p-f(f(k))+1}

　ここで p は十分大きく取っているので、右辺の分母のみをいくらでも大きく出来ます。したがって f(f(k))-k-2=0 が必要です。
　かなりの前進ですが、うっかりこの式だけから f(n)=n+1 としないように気を付けてください。反例があります(良ければ構成してみてください)。ここは丁寧に元の与式に代入してあげましょう。
\displaystyle\frac{m+n+2}{f(m)+n+1}=1+\frac{m+1-f(m)}{f(m)+n+1}

　右辺において分子が m のみの式であることがポイントで、再び同じテクニックが使えます。すなわち n を動かすことで分母をいくらでも大きく出来るので、m+1-f(m)=0 がわかりました。
　まとめるとこの解法で重要なのは「素数の利用」と「変数分離」でした。離散型のFEはなかなか対策しづらく苦手意識を持つ人も多いかもしれませんが、基本的に考えるべきいくつかのポイントは共通しています。それらを確実に抑えるだけでも違うと思います。

概観

　以前より全体としての難易度は多少下がっていますが、地力が諸に見えるセットだと感じました。ボーダーは例年通り1完～2完というところでしょうが、差はしっかり付いたのではないでしょうか。

　お読み頂きありがとうございました。感想・質問などあれば気軽にどうぞ。