2014~2018 JMO 予選問9~11 - だま氏の解いた問題たち

はじめに
JMO予選について
2018
- 9
- 10
- 11
2017
- 9
- 10
- 11
2016
- 9
- 10
- 11
2015
- 9
- 10
- 11
2014
- 9
- 10
- 11

はじめに

Math Advent Calendar 2018 - Adventarの21日目の記事です.
当初9~12までにするつもりでしたが全然解けず…ごめんなさい.
完全な解法は書いていないのが多いですが, 解法の筋道や解法にたどり着くまではできるだけ書いたつもりです.

JMO予選について

過去問→http://www.imojp.org/challenge/index.html
JMO予選は3時間12問短答式で1問1点の12点満点です(無慈悲…).
6点→「受かるかもだけどややきつそう…」, 7点→「ちょい心配だけどまあ受かりそう」, 8点→「だいたい受かる」, 9点以上→「かなり安心」といったところです.
3時間と時間が長いので, 書き出せるやつは無理やり書き出すのも全然ありみたいな感じです.
難易度としては(個人の感想), $(1, 2)<(3,4)\ll (5,6,7)<(8,9)<(10,11)<(12)$くらいかと思います.
最後の30~45分位は, 無理に新しい問題に取り組まなくても見直しに取り組むのがいいかもしれません. また簡単な順に並んでるとは限らないので, 詰まったら飛ばしてみても良いと思います.
コンパスと定規は必ず持っていきましょう. 分度器は持ち込んではいけないので注意です.
今回解説する9~12の問題ですが, ぶっちゃけこれが解けなくてもそれまでの問題で全完すれば予選は通ります. 入賞には予選の結果は反映されないので通りさえすればよいです(ちなみにJJMOは別で, おそらくですが予選の結果も反映されます). なので趣味の部分が強いですが, 上位を目指したいとか, 数問ミスしても安心したいという人のためにも解説(概説)します.

2018

9

こういう図形問題は丁寧に描きましょう. まずは普通サイズでフリーハンドで書いてから概要を確かめて, 大きめにコンパスや定規で正確に図を描くのが良いです.

図を描いてみると, どうやら点A, I, D, Eが同一直線上にあるようです. これは実際に成り立ちます. ∠RDU=∠QDT=90°, ∠REU=∠QET=90°(対称的な形)なので, 点D, Eは, RUを直径とする円とQTを直径とする円の交点と言い換えられ, 対称性から直線AI上にあることが分かります. これでちょっとDEにとっつきやすくなった気がします.
また点D, P, E, Sは同一円周上にあり, PSは直径になります. (ここで少し悩んだ)ここで正弦定理をこの円に使うことを考えます. sin∠DSEが分かれば直径が分かっているのでDEが分かります. すると角度を追っていけば∠DSE=∠AIRが分かります. これは分かっているので解けました.

10

本番解けたやつです. これ好きです.
「優勝候補が2人いる」とはどういうことかを突き詰めていけばわかる感じです. 問題を解く手がかりとして, 「優勝候補が2人いる」という条件はよくわからないので, それをよくわかる形にしたいです.
まず全勝touristみたいな人がいる場合は明らかにだめです.
人Xが事前試合で人Yに勝っているのをX->Yと書くことにします.
優勝候補をAとBとし, A->Bとします.
Aは誰かに負けています. そのうちの1人をCとします.
まずBはめちゃくちゃ強いです, なぜならAが予選敗退したら勝ち確定だからです. 実際, 4人のトーナメントで左からC, A, B, X(XはA, B, C以外の任意の人)となっているときを考えるとB->Xがわかります. そしてこのトーナメントで準決勝はCとBが戦ってCが勝つことになります. つまりBはA以外の人全員に勝っています.
次に, 4人のトーナメントで左からA, B, C, X(XはA, B, C以外の任意の人)となっているときを考えてみましょう. もしここでCがXに勝ってしまったら, AもBも敗退してしまうのでよくないです. よってCはA以外全員に負けてることが分かります. またこのトーナメントで次の試合はA vs XでAが勝つので, AはC以外全員に勝っています.
実はこれらの条件

A->B, A->X
B->C, B->X
C->A, X->C

さえ満たせば, 優勝候補が2人になることが分かります. これで条件を分かりやすくすることができました.

11

7進法での覆面算みたいな感じです.
見た感じ, 初手でmodとか整数論っぽいことをするのは厳しそうです($i$桁目を取り除くとかヤバそう). ちょっと考えると, 大小評価である程度桁数が絞れそうなので, その方針で行きます.
$n_i$は上から$k-i$桁の数が$n$と同じということで不等式評価すると, $6\leq k\leq 8$が分かります. しかし$k=6,8$のときは$n\leq 11\cdots 1(1がk個)$となります. この場合はもっと不等式評価することで, ダメだということが分かります.
$k=7$のときは, 実は下一桁を決めると, 7が素数であることからどんどんと数字が決まっていき(やっと整数論っぽいこと), 最後に上の桁を自由に選べばいいことが分かります.

2017

9

これ教育的で良いです. あるものの個数が別の角度から数えることでわかるというよくあるパターンです.
簡単な方の問題として, ${\displaystyle\sum_\sigma F(\sigma)}$ を求めてみましょう.
このままだとわかりにくいですね.
ここで
$F_i(\sigma)=\begin{cases}1&(\sigma(i)=i)\\0&({\rm otherwise})\end{cases}$
と定めてみましょう. すると
$F(\sigma)=\sum_i F_i(\sigma)$
なので,
${\displaystyle\sum_\sigma F(\sigma)=\sum_\sigma \sum_i F_i(\sigma)=\sum_i \sum_\sigma F_i(\sigma)}$
です.
ここで ${\displaystyle\sum_\sigma F_i(\sigma)=2016!}$ であることは明らかなので
${\displaystyle\sum_\sigma F(\sigma)=2017!}$
です.
${\displaystyle\sum_\sigma F(\sigma)^2}$ についても考えると, これは
${\displaystyle\begin{eqnarray}&&\sum_\sigma \left( \sum_i F_i(\sigma)\right) ^2\\&=&\sum_\sigma \left( \sum_i F_i(\sigma)^2+\sum_{i,j}F_i(\sigma)F_j(\sigma)\right)\\ &=&\sum_i \sum_\sigma F_i(\sigma)^2+\sum_{i,j} \sum_\sigma F_i(\sigma)F_j(\sigma)\\&=&\sum_i 2016!+\sum_{i,j} 2015!=2\cdot 2017!\end{eqnarray}}$
と式変形できます.
4乗の場合も同様です. 係数の間違いに注意してください.

10

中3のとき, 死ぬ気で余弦定理とかいろいろ使って間違えたのが懐かしいです. 実は複雑な辺の長さの計算はほぼないです.

まず点Cが三角形PQRの傍心となることがわかります.
QをBCで折り返した点をQ'とすると, RQ'+RQ=12です.
すると, Cから直線RQ'におろした垂線の足をHとするとき, RH=6であり, ∠CRH=∠CBAより, CH=9/4であることがわかります.
CからPQへおろした垂線の足をH'とするとCH'=9/4です. また△CH'Q∽△CBRよりCQ:QR=9/4:3=3:4です. するとCQ:CA=9:16とわかってこの問題が解けました.

辺の長さと角度を対応させるのは相似がかなり強い印象があるので, 相似なものを探す感じで解いていくといいかもしれません. 図を丁寧に書くと気づきやすいので, 何度も言いますが図は丁寧に描きましょう.

11

これ意外と難しくないですがミスしやすいです. とりあえず$U=\{1,2,\dots,30\},A=\{2,4,\dots,30\},B=\{3,6,\dots,30\},C=\{5,10,\dots,30\}$としましょう. どんな問題が必要になってくるのかを考えます.
$S=U-\{30\}$とすると, これは(2)を満たさないので, (1)も満たしません. すると出席番号30番の人だけが解いた問題があることがわかります. こんな感じで, (2)を満たさない割と大きな集合を考えると良さそうです.
例えば$S=U-\{2,15\}$とすると, 出席番号2番と出席番号15番の人だけが解いた問題があることがわかります. 両方解いていることは, $U-\{2\}$も$U-\{15\}$も(2)を満たすことからわかります.
$S=U-\{2,3,5\}$というふうに3つバージョンもあります. というわけで, 「$A,B,C$のどれも含まないけど一つ増えるとどれかを含むようになる集合$S$」を数えればよいです. これらの集合が相異なることや, これだけの問題で十分なことは, (1)と(2)の条件を睨めば割と簡単に示せると思います.
なので,
\[\begin{eqnarray}
\{30\},\{30未満の2の倍数,30未満の15の倍数\},\\
\{30未満の3の倍数,30未満の10の倍数\},\{30未満の5の倍数,30未満の6の倍数\},\\
\{15と互いに素な2の倍数,10と互いに素な2の倍数,6と互いに素な5の倍数\}
\end{eqnarray}\]の個数を数えます. ここで同じものを2回数えないように注意してください($\{6,15\}$など).

追記(2023/04/02)

これについて質問されたので，改めて解説を書きました．
かなり昔に書いたので，今見るとわかりにくい解説だなあと思います．

$Q_k$で出席番号$k$の生徒が解いた問題の集合，$P$で問題全体の集合を表すとします．
また解説の通り，
\begin{align}
U&=\{1,2,3,\dots,30\}\\
A&=\{2,4,6,\dots,30\}\\
B&=\{3,6,9,\dots,30\}\\
C&=\{5,10,15,\dots,30\}
\end{align}とします．

問題の条件は，$f(S)=\bigcup_{k\in S}Q_k$と表すとき
\[f(S) = P \quad\Longleftrightarrow\quad (A\subset S~\text{または}~B\subset S~\text{または}~C\subset S)\]と表されます．ここで重要なのが，$f$は包含を保つこと，すなわち
\[S\subset S' \quad\implies\quad f(S)\subset f(S')\]が成り立つことです．

すると，$P,Q_1,\dots,Q_{30}$が上の性質をみたすことを確かめるのに試すべきことは以下だけでいいことがわかります．

$f(A)=f(B)=f(C)=S$．

$A$, $B$, $C$いずれも含まないような集合のうち極大なもの（それより少しでも大きい集合は$A$, $B$, $C$のいずれかを含んでしまうもの）$S$について，$f(S)\neq P$．

なぜか？それは「右ならば左」と「右でないならば左でない」を示そうとしてみれば，$f$が包含を保つことからわかると思います．

ここから$P,Q_1,\dots,Q_{30}$の構成をしていきます．上の条件はそこまで制約にはならなさそうなので，下の方から考えます．$A$, $B$, $C$いずれも含まないような集合のうち極大なものとは何でしょうか？例えば$U\setminus \{30\}$や$U\setminus \{6,25\}$などがみたします．$f(U\setminus \{30\})\neq P$かつ$f(U)=P$ということは，$Q_{30}$にしか属さない問題が存在するということです．また$f(U\setminus \{6,25\})\neq P$かつ$f(U\setminus \{6\})= P$かつ$f(U\setminus \{25\})= P$ということは，$Q_{6}$と$Q_{25}$にしか属さない問題が存在するということです．このような感じで，$A$, $B$, $C$いずれも含まないような集合のうち極大なものに対し，相異なる問題が定まります．$A$, $B$, $C$いずれも含まないような集合のうち極大なものは$103$個あることがわかるので，問題は少なくとも$103$個あることがわかります．

ではその$103$問だけで上の条件はみたすのでしょうか？例えば$A$は，$A$, $B$, $C$いずれも含まないような任意の集合の補集合と共通部分を持つので，問題の定め方から，$f(A)=P$であることがわかります．$B$, $C$についても同様であるので，これで構成になっていることがわかりました．

2016

9

9問目にしては簡単…？
条件を整理してけば解けます, 楽です
$(b+1)|a, b|(2016-a)$より$a=k(b+1),2016-a=lb$とおけます.
$2016-k(b+1)=lb$より$(k+l)b+k=2016$です.
$k,l$は1以上2016以下であることを考えると, $b$は2016の約数でないもののとき$k,l$が一意に決まっていい感じです. いろいろ考えるとそれを数えればいいことがわかります.

10

Static Sushi
旗のとり方は図の2種類(左右逆もあり)です.

2016はちょっと大きすぎるので, 少ない場合について考えてみましょう(考えにくい問題の場合は問題を少し一般化して, 小さい場合について考えるということはしばしば有用です). 奇遇に依存しそうな感じがするので, 4, 6, 8,...について考えます.
4のときについて考えると, どのようなとり方でもおんなじ距離にすれば良さそうです.
左右対称なのが良さそうなので, 図のように置いてみましょう.

連立方程式を立てると
\[1-a=1-a+b=3(a+b)\]で$a=1/10, b=2/10$です. この場合, A君の動く必要のある距離は9/10です. これが最も良いのは鳩ノ巣を使えばできます. 旗とA君で5つの区間に分かれています. この区間を固定して, 別の4本の旗がたてられるとしましよう. すると少なくとも1つの区間には旗がありません. それ以外の区間を舐めるように旗を回収すれば大丈夫です.
6, 8, ...においても同様に連立方程式を立てられます. すると区間の長さが近い方から1:2:4:…になっているのが観察できると思います. 2016の場合も同様です.

11

これ難しいです…
1000の方から攻めるのはつらそうなので, $+a$と$-b$でなんの順列ができるか考えるという方針で行きましょう.
とっつきにくいので, 簡単な方の問題としてこういうのを考えてみましょう：
「+3と-5だけで$1,2,\dots,n$の順列を作れるとき, $n$はいくつか?」
図を書いてみます(矢印は確定の部分).
するとすでに8つでループしちゃっているのがわかります. なので答えは8だけでしょうか?
よく考えると, ループでなくても順列であればいいので, 少しばかり矢印を壊していいことがわかります. すると7つと9つの場合にもできることがわかります. しかもジョイントもすることができます. このように, どのようなときにできるかを少しずつ考えると, 8で割ってあまりが0, 1, 7のいずれかのときにできるということが(頑張ると)わかります. 全部見つけるのは辛いですね…
これだけだということは$\pmod 8$を見ればわかります(まあまあ難しい).
この場合は+3と-5でしたが, 任意の$a,b$でも, $a$と$b$が互いに素であれば同じことが言えます.
なので, 「$a+b$が999,1000,1001のいずれかの約数であるような, 互いに素な2以上の整数$a,b$の組」の数を数えれば良いことがわかります.

2015

9

$_{4030}{\rm C}_{2015}-(かぶってるやつ)$になるので, かぶってる数を少なくしたいです.
この数列を$a_1,a_2,\dots,a_{4030}$とします. また, $a_k$と$a_l$は$|k-l|$離れているということにします.
ここで, 同じ数が2015離れているとき, かぶる半列が一つできます. $a_k=a_{k+2015}$だとして, $a_1,\dots,a_k,a_{k+2016},\dots,a_{4030}$と$a_1,\dots,a_{k- 1},a_{k+2015},\dots,a_{4030}$が被ります.
また同じ数が2014以下離れているとき, かぶる半列が2015個以上できます.
$a_k$と$a_{k+d}$($1\leq d \leq 2014$)が同じだとして, $a_1,\dots,a_{k- 1},a_{k+d+1},\dots,a_{4030}$のなかから2014個選ぶので, $_{4030-d}{\rm C}_{2014}\geq 2015$もかぶります.
そう考えると$1,2,\dots,2015,1,2,\dots,2015$が良さそうだと思えます. この場合, 相異なる半列の個数は$_{4030}{\rm C}_{2015}-2015$です.
これよりいいものがないことを大雑把に示してみます. すべての1以上2015以下の整数$n$において, 2つの$n$が2015以上離れているとき, すべてちょうど2015離れていることが示せます(数列の真ん中の方から順々に決まっていくイメージです).
ある$n$について離れているのが2014以下だとしましょう. するとその部分でかぶるものが2015個できちゃっているのでさっきよりは良くなりません. なので$_{4030}{\rm C}_{2015}-2015$が最良です.

10

結構好きです
「一桁の数」という大小関係みたいなやつがうざいので, それが影響されないmodを考えてみます
$10x+y\mapsto x+4y$ですが$10(x-k)+(y+10k)\mapsto x+4y+39k$とも同じになってほしいです, なのでmod39が思いつきます
そうするとずっと4倍にするのと同じになります, なのでmod39での値がわかりました
あとは大小評価を使います, まあだいたい1/10になるのでそんな感じで頑張ります

11

Iが△A'B'C'の垂心になるのは構図です.
またA'B=A'Iとなることや$A'D\times A'A=AI^2$になることも構図です.
IとAが直線B'C'で対称なことも構図です(B, Cについても同様).
これらの構図は容易に証明できるので, 知らなかった場合は示してみてください.
AI:IA'が面積比ですぐにわかるので, AD:DA'もわかります. すると△A'BCの面積が△ABCの定数倍として明示できます. △B'CAや△C'ABにおいても同様です. すると六角形AC'BA'CB'が△ABCの定数倍で書けますが, その六角形の面積はわかってる(2×(2+3+4)=18)ので解けました.
構図を知っていると便利な問題ですね.

2014

9

図を描いてぼんやり眺めてみます. すると立体的に見えるかもしれません. ピラミッドが平面で切断されているイメージです. (以下立体で考えます)
正四角錐O-ABCDを平面PQRで切断したときのODと切り口の交点を求めればよいことが分かります(その正当性を示すのはメネラウスとかで殴る必要がありそうですが良しとしましょう). 点Oから平面ABCDにおろした垂線をℓとおきます. PR, QS, ℓが一点で交わればよいです. ∠POR, ∠QOSは何でもよいですが, 計算が楽なように120°にしておきましょう. するとℓとPRの交点の場所が計算できて, QSについても考えればOSも分かります.
予選なのでこのようなアレな解答ができますね！！うれしい！！

10

これも10にしては簡単だと思います…「長方形の角に注目する」という発想を思いつけばすぐです.
どのマス目の頂点においても, その頂点は選択した長方形の角として1回選ばれないといけません. これはすこし試してみるとわかると思います.
すると少なくとも$56^2/4$回は操作しないといけません. またこの例の構成は割と容易です.

11

今見るとめっちゃ(抽象)代数です. 代数っぽい感じで解いていきましょう. 集合は$S=\{1,2,3,4,5,6\}$で演算は$\diamondsuit$です.
$i\diamondsuit j$と書くのは面倒くさいので$ij$と略記します.
まずモノイドになってほしい(結合法則が成り立ってほしい)です. これは\[a(bc)=(aa)(bc)=ac=(ab)(cc)=(ab)c\]と証明できます.
結合法則が成り立つのでもうわざわざかっこをつける必要がなくなります.
しかし$abc=ac$ってヤバいです. 真ん中($b$)の情報がなくなってるってヤバくないですか? この演算の性質についてもう少し考えてみます.
$ab=c$のとき, $\forall x, abx=cx$より$\forall x,ax=cx$です. また同様にして$\forall x,xb=xc$が分かります.
ここで同値関係を定めて分かりやすくしましょう. $a\sim_1 b\Leftrightarrow \forall x,ax=bx$, $a\sim_2 b\Leftrightarrow \forall x,xa=xb$と定義しましょう(これが同値関係になることは明らかです). 少し考えると$a\sim_1 b\Leftrightarrow \exists y, ay=b$, $a\sim_2 b\Leftrightarrow \exists y, ya=b$も分かります.
この問題では$|S|=6$なので同値類を全探索してもよさそうです. $\sim _1$で同値類に分けることを考えてみます. ちょっと試してみると, 同値関係が強すぎてめっちゃ決まってくることが分かります.
大きさが1の同値類があるとヤバくて, $\sim _2$の方では全部同じ同値類に入っていないといけません. この場合は1通りです.
大きさ1の同値類が入らない分割の仕方は$(2,2,2),(2,4),(3,3),(6)$のみです. 全探索しちゃいましょう.