だま氏の解いた問題たち

解いた問題で良問だったものを載せます

好きな問題いろいろ

やっぱり個人的に解いた問題もたまにはまとめなきゃと思うのでまとめます。
もともとこういうブログなので。

だいたいAoPSからコピーしてきたものなので和訳していません…
あとSLPなど有名どころが多いです。
文章・画像混ざっていますがごめんなさい。

A(代数)分野

数オリのAってぶっちゃけほぼ実数か有理数か整数なのですが。

2018 APMO 5

f:id:yootaamath:20190610194042p:plain

この問題は大好きです。
個人的に多項式が好きなのですが、この問題は特に好きです。

2017 ELMO 6

Find all functions $f:\mathbb{R}\to \mathbb{R}$ such that for all real numbers $a,b,$ and $c$:

  • If $a+b+c\ge 0$ then $f(a^3)+f(b^3)+f(c^3)\ge 3f(abc).$
  • If $a+b+c\le 0$ then $f(a^3)+f(b^3)+f(c^3)\le 3f(abc).$

通信添削として出題された問題です。
難しいですがFEにしては変わった方法で解けるので好きです。
若干ヒントになるかも? 京大特色のおかげで解けた気がします。

2009 IMO 3

\(s_1,s_2,\dots\)は正の整数からなる狭義単調増加数列であり, \(s_{s_1},s_{s_2},\dots\)および\(s_{s_1+1},s_{s_2+1},\dots\)はどちらも等差数列である. このとき, \(s_1,s_2,\dots\)も等差数列であることを示せ.

さなさんにおすすめされたので解きました。いいですね~
3番級の中では簡単らしいですが結構時間がかかりました…

2013 SLP A5

Let $\mathbb{Z}_{\ge 0}$ be the set of all nonnegative integers. Find all the functions $f: \mathbb{Z}_{\ge 0} \rightarrow \mathbb{Z}_{\ge 0} $ satisfying the relation
\[ f(f(f(n))) = f(n+1) +1 \]for all $n\in \mathbb{Z}_{\ge 0}$.

これはまた特徴的な問題で…
結構難しいですが、解けた時の爽快感はかなりあります。

2014 和田杯 2

f:id:yootaamath:20190611235320p:plain
これも特徴的です。和田杯であることに注意。
こういうのをたまにやると数オリに毒される(?)こともなくなるかも。

2018 和田杯 11

f:id:yootaamath:20190611233635p:plain
有限集合っていいですよね(は?)

C(組み合わせ)分野

2012 SLP C3

In a $999 \times 999$ square table some cells are white and the remaining ones are red. Let $T$ be the number of triples $(C_1,C_2,C_3)$ of cells, the first two in the same row and the last two in the same column, with $C_1,C_3$ white and $C_2$ red. Find the maximum value $T$ can attain.

これはCというか…

2016 EGMO 3

f:id:yootaamath:20190611231240p:plain

ある量を上からor下から評価する問題の教育的な例な気がします。

2014 JMO予選 11

f:id:yootaamath:20190611231418p:plain
明らかに2項演算をわざわざマス目にした問題なんですけど、抽象代数っぽいことをすれば解けます。こういうのなかなかないので。

Sperner's theorem より

\(S_0=\{1,2,\dots,n\}\)の部分集合の属\(\mathcal{S}\)において、\(\mathcal{S}\)に属する任意の2つの異なる集合についてどちらかがどちらかを含むことはないとする。\(\mathcal{S}\)の要素数の最大値を求めよ。

自然な問題で、実はまあまあ難しいです。
割と好きなのでぜひ。

Sperner's lemma (2次元)

Given a triangle $ABC$, and a triangulation $T$ of the triangle, the set $S$ of vertices of $T$ is colored with three colors in such a way that

  • $A$, $B$, and $C$ are colored red, blue, and white respectively
  • Each vertex on an edge of $ABC$ is to be colored only with one of the two colors of the ends of its edge. For example, each vertex on $AC$ must have a color either red or white.

Then there exists an odd number of triangles from $T$, whose vertices are colored with the three different colors.

またSpernerさんですか…
これも好きです。

2017 SLP C2

Let $n$ be a positive integer. Define a chameleon to be any sequence of $3n$ letters, with
exactly $n$ occurrences of each of the letters $a, b$, and $c$. Define a swap to be the transposition of two adjacent letters in a chameleon. Prove that for any chameleon $X$, there exists a chameleon $Y$ such that $X$ cannot be changed to $Y$using fewer than $3n^2/2$ swaps.

競プロやってるひと得意そう。

2018 EGMO 3

f:id:yootaamath:20190730155505p:plain

これ面白い!!

2018 SLP C3

Let $n$ be a given positive integer. Sisyphus performs a sequence of turns on a board consisting of $n + 1$ squares in a row, numbered $0$ to $n$ from left to right. Initially, $n$ stones are put into square $0$, and the other squares are empty. At every turn, Sisyphus chooses any nonempty square, say with $k$ stones, takes one of these stones and moves it to the right by at most $k$ squares (the stone should say within the board). Sisyphus' aim is to move all $n$ stones to square $n$.
Prove that Sisyphus cannot reach the aim in less than
\[ \left \lceil \frac{n}{1} \right \rceil + \left \lceil \frac{n}{2} \right \rceil + \left \lceil \frac{n}{3} \right \rceil + \dots + \left \lceil \frac{n}{n} \right \rceil \]turns. (As usual, $\lceil x \rceil$ stands for the least integer not smaller than $x$. )

簡単ですが、ハマる人はハマります。

G(幾何)分野

2013 SLP G5

Let $ABCDEF$ be a convex hexagon with $AB=DE$, $BC=EF$, $CD=FA$, and $\angle A-\angle D = \angle C -\angle F = \angle E -\angle B$. Prove that the diagonals $AD$, $BE$, and $CF$ are concurrent.

かなり主張がきれいで、証明もいい感じです。

2002 SLP G7

The incircle $\Omega$ of the acute-angled triangle $ABC$ is tangent to its side $BC$ at a point $K$. Let $AD$ be an altitude of triangle $ABC$, and let $M $ be the midpoint of the segment $AD$. If $N$ is the common point of the circle $ \Omega$ and the line $KM $ (distinct from $K$), then prove that the incircle $ \Omega$ and the circumcircle of triangle $BCN$ are tangent to each other at the point $N$.

これはかなり難しいですが、主張も面白いしややきれいでいい問題だと思います。

2011 SLP G3

Let $ABCD$ be a convex quadrilateral whose sides $AD$ and $BC$ are not parallel. Suppose that the circles with diameters $AB$ and $CD$ meet at points $E$ and $F$ inside the quadrilateral. Let $\omega_E$ be the circle through the feet of the perpendiculars from $E$ to the lines $AB,BC$ and $CD$. Let $\omega_F$ be the circle through the feet of the perpendiculars from $F$ to the lines $CD,DA$ and $AB$. Prove that the midpoint of the segment $EF$ lies on the line through the two intersections of $\omega_E$ and $\omega_F$.

G3にしては難しいです。若干知識がいるかも…?
あまりないタイプな気がします。

2004 SLP G7

For a given triangle $ABC$, let $X$ be a variable point on the line $BC$ such that $C$ lies between $B$ and $X$ and the incircles of the triangles $ABX$ and $ACX$ intersect at two distinct points $P$ and $Q$. Prove that the line $PQ$ passes through a point independent of $X$.

教育的な問題です。

2012 SLP G6

Let $ABC$ be a triangle with circumcenter $O$ and incenter $I$. The points $D,E$ and $F$ on the sides $BC,CA$ and $AB$ respectively are such that $BD+BF=CA$ and $CD+CE=AB$. The circumcircles of the triangles $BFD$ and $CDE$ intersect at $P \neq D$. Prove that $OP=OI$.

バンジーさんの解いてみた集に載っていたので解きました。
主張がなかなか面白くて、手ごたえがあって良かったです。

2014 SLP G6

Let $ABC$ be a fixed acute-angled triangle. Consider some points $E$ and $F$ lying on the sides $AC$ and $AB$, respectively, and let $M $ be the midpoint of $EF$ . Let the perpendicular bisector of $EF$ intersect the line $BC$ at $K$, and let the perpendicular bisector of $MK$ intersect the lines $AC$ and $AB$ at $S$ and $T$ , respectively. We call the pair $(E, F )$ interesting, if the quadrilateral $KSAT$ is cyclic.
Suppose that the pairs $(E_1 , F_1 )$ and $(E_2 , F_2 )$ are interesting. Prove that $\displaystyle\frac{E_1 E_2}{AB}=\frac{F_1 F_2}{AC}$.

これもバンジーさんにおすすめされたので解きました。
点をどんどん言い換える感じ?で面白かったと思います。

2018 RMM 6

Fix a circle $\Gamma$, a line $\ell$ to tangent $\Gamma$, and another circle $\Omega$ disjoint from $\ell$ such that $\Gamma$ and $\Omega$ lie on opposite sides of $\ell$. The tangents to $\Gamma$ from a variable point $X$ on $\Omega$ meet $\ell$ at $Y$ and $Z$. Prove that, as $X$ varies over $\Omega$, the circumcircle of $XYZ$ is tangent to two fixed circles.

3番級ほどの難易度ではないですが、主張がきれいですし、面白いです。

N(整数論)分野

1987 IMO 6

Let $n\ge2$ be an integer. Prove that if $k^2+k+n$ is prime for all integers $k$ such that $0\le k\le\sqrt{\cfrac n3}$, then $k^2+k+n$ is prime for all integers $k$ such that $0\le k\le n-2$.

IMOの中ではかなり主張がきれいで有名な問題な気がします。
意外とやればできる問題でしたが、主張がきれいでポイント高めです。

H30年度 京大理学部特色 4

f:id:yootaamath:20190610195325p:plain

本質は(2)なんですけど、たぶんこの年の特色入試の中で一番難しくて面白いです。

2017 SLP N6

Find the smallest positive integer $n$, or show that no such $n$ exists, with the following property: there are infinitely many distinct $n$-tuples of positive rational numbers $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ such that both$$a_{1}+a_{2}+\cdots+a_{n} \quad \text{and} \quad \frac{1}{a_{1}}+\frac{1}{a_{2}}+\cdots+\frac{1}{a_{n}}$$are integers.

N6にしては簡単ですが面白いと思います。

2011 SLP N3

Let $n \geq 1$ be an odd integer. Determine all functions $f$ from the set of integers to itself such that for all integers $x$ and $y$ the difference $f(x)-f(y)$ divides $x^n-y^n$.

FE多くてごめんなさい…
教育的です。

IMO 2019 参加記 ~試験編~

試験の概要

体育館の中で試験をしました。
Contestant 1のブロック、2のブロック、…というように分かれていて、同じ国の人が近くに来ないようになっています。
トイレについては外に仮設のものが来ていました。誰がいつ出て入ったか管理されます。

Day 1 の感想

自分でも驚くほど調子が良かったです。
20分で(解答を書く時間含めず)問1と問2を解けてしまいました。
さっさとその答案を書き上げ、問3を考える時間を確保しました。
時間ギリギリでしたがなんとか問3を完答できました。
解説については https://www.imo2023.org/archive/mo2019/imo2019/problems/solutions-r856.pdf に書いてあるのでそちらを参照してください。

問題1

簡単だと思います。ちょっとやれば\(f\)が線形であることがわかるのでおわります。

問題2

ここでなんかめっちゃ天才になってました。公式のSolution 1と若干似ている解答です。
こういう共円ってその円上の補助点をとるといいことがあるよねってなって、謎な角度の条件を使えるように、直線\(BB_1\)と\(\odot B_1CP_1\)の交点をとったらすべてうまく行きました。

問題3

公式の解答とは違う若干めんどくさいことをしました。イベントを繰り返してどの頂点も次数が高々1にできるグラフは「良い」と言うことにするとき、橋のある連結なグラフは良いことをまず示し、次に最初の問題のグラフはイベントを繰り返して橋のある連結なグラフにできることを示しました。
橋のある連結なグラフが良いことの証明は、辺の本数の帰納法で、いい感じにイベントを起こすと帰納法が回ることを示す感じです。
最初の問題のグラフがイベントを繰り返して橋のある連結なグラフにできることの証明は若干大変ですが、適切にアルゴリズムに従ってイベントを起こすと、良くない状態(連結でないまたは完全グラフである状態)を回避しながら最終的に橋ができることを示す感じです。

Day 2 の感想

問4と5を1時間位で解いて、解答を書こうとして書いていったら問4で嘘をついていることがわかってやや悩んで、それであと試験が2時間位になった気がします。
問6は全然わかりませんでした…
試験後坂本君が「複素で行けた、頑張った」と言っていました。

問題4

簡単ですが若干面倒くさいです。2のオーダーと大小の比較で十分なのですが、自分は2のオーダーと3のオーダーを比べるという面倒くさいことをしてしまいました。LTE補題とか出てきて大変です。
最終的に1点引かれていました。細かい部分で添え字を-1してしまったらしく、悲しいです。細かいミスにも注意しましょう。

問題5

簡単です。(b)で帰納的にできることは割とすぐに見えると思います。

問題6

本当に手がつけられませんでした。初等だとかなりきついと思います。
わからないですけど、解けている人はだいたい複素座標でしょうか…?
バンジーさんによる複素座標での解答です。

IMO 2019 参加記 ~試験以外編~

7月13日

羽田まで

まだ学校はあるのですが、イギリスに行く準備をするために先に実家に帰省してから、羽田空港に行きました。父親もいました。
本当にドキドキです。

羽田空港

結構早くに付きました。JPN2と合流しました。
一緒にバンドリとかしてました。JPN2うまい…

結団式・直前学習会

通信添削というものがあって、代表6人は4回に渡ってIMO形式の問題を配られ、解答をチューターに送付し、添削してもらいます。(昔は代表候補全員やってたらしいんですけど…もうやらないのかな…)
第4回の添削の返却・解説がありました。
やはり「この部分は非自明だから説明したほうがいい」などいろいろ指摘されます。
第3回の添削でJPN6のしていた解法がヤバすぎてヤベえ(褒め言葉)ってなりました。組み合わせの問題を(マス目全然ないのに)マス目の問題に言い換えてそれを図形としてパップスギュルダンの公式を使う(は???????)らしいです。

飛行機

深夜のフライトになるため、飛行機に乗る前にラウンジに行けました。ご飯を食べました。
フライトは12時間位です。日本とイギリス(サマータイム)は時差が8時間あるため、ほとんど寝ていようと思っていましたが、そうはうまくいきませんでした。結局寝たのは6時間位でした。
翔んで埼玉を見ました。めちゃめちゃ面白かったです。

7月14日

ヒースロー空港

着いたー!!! 初ヨーロッパ、初イギリスです。
空港にIMOの受付会場がありました。
そこでミャンマーの代表と一緒に写真を取りました。
そこからバスでバース大学へと向かうのですが、あれ?? バスが見当たらない…?
しばらくしてスタッフの方が呼んでくれて助かりました。
バスで2時間位です。結構長い…
窓から眺める景色がとても綺麗でした。

バース大学

IMOの旗が立っていていよいよだなってなりました。
まずは宿泊施設に行きました。大学内の寮で、治安も環境も安心でした。
f:id:yootaamath:20190728085522j:plain
いくつか面白かったこと

  • 自動ドアの開き方が開き戸
  • エレベーターの音がうるさい
  • カモメが多い

f:id:yootaamath:20190728084420j:plain

洗礼(昼食)

イギリス、前々からご飯が不味いって噂だったので心配でした…
からの
† JUST HAM †
f:id:yootaamath:20190728084442j:plain
衝撃的でした…
まじでハムしか挟まってません…
味はJUST HAMって味でした。
他の人は† JUST CHEEZE †とか食べてました。

その後

かなり暇でした。数学の問題を出し合って解いてました。
日没がめっちゃ遅いですね…時間感覚が狂います。

夕食

初めての食堂での食事でした。じゃがいも多くね?ってなりました。
やっぱびみょいですね。
WiFiが遅い…

7月15日

朝食

初めての朝食です。
食パンとクロワッサンとオレンジくらいです。
ココア(?)を飲みました…スイッチを押すと出てくるやつです…
f:id:yootaamath:20190728084823j:plain
※JPN5のツイートより
(`0言0́*)<ヴェアアアアアアアア
クッッッッッソ不味い

ココアの香りのするお湯って感じでした。砂糖を入れてなんとかしましたがひどかったです。
これが本場の味なの?とかなり疑問でした。

午前中

午前中もかなり暇でした。数学の問題を出し合って解いてました。
一発で解けるような問題を出し合ってました。

開会式

f:id:yootaamath:20190728085843j:plain
ホールで開会式がありました。
始まる前にDJがいろいろ曲をかけていました。
各国の入場がありました。
前々からトリニダード・トバゴをネタにしてきたので(代表選考でトリニダード・トバゴの問題にJPN5とJPN4がハマったので)トリニダード・トバゴを盛り上げました。
終わったあとにいろいろな国の選手と交流しました。インドの選手にけん玉を披露して鯉のぼりをプレゼントしました。

夕食

トマトソースのパスタを食べてみたけど…味付けが下手ですか???
f:id:yootaamath:20190728084840j:plain
※JPN5のツイートより
見た目よりもおいしくなくて、塩コショウをかけるとましになります。

桐間紗路生誕祭

おめでとうございます!!
7月15日はこの命が生まれた奇跡を全人類で祝うべきである(「ごちうさ」シャロ誕生祭をAbemaTVが実施 7月15日はこの命が生まれた奇跡を全人類で祝うべきである - ねとらぼ より)
Abemaのアニメ、イギリスから見れないようでした…悲しみ

7月16日

コンテスト

コンテスト1日目でした。コンテストの様子は別の記事で書こうと思っています。

午後

とりあえず頭がつかれました。タイムボムというカードゲームをやっていました。

7月17日

コンテスト

コンテスト2日目でした。コンテストの様子は別の記事で書こうと思っています。

午後

とりあえず頭がつかれました。

イギリスのスタッフである町野さんと会いました。高1らしいですが、日本語も英語も話せるし(通訳など大変お世話になりました)、すごい!
後で調べてみて知ったのですが、2019年EGMOで(イギリス代表として)金メダルをとっています。

町野さんに紹介されて、オーストラリアやイギリスの選手とカードゲームをしました。
Hanabiやmaoをしました。
Hanabiは競うのではなく皆である状態を目指す協力ゲームでした。なかなか難しい…
maoはかなり凶悪なゲームです。
en.wikipedia.org
まずルールを教えてもらえなくて、ルールを破ると指摘されてペナルティーカードをもらいルールを体得するという感じです。トランプを使うゲームで、原理的にはUNOと同じ(同じ数字またはスートの場合カードを出せ、カードを無くした人の勝ち)ですが、最初はめちゃくちゃカードを引かされます。
ゲーム外の内容を話すとペナルティというルールもあります(は??)
怒りとの勝負なゲームな気がします。
SETもしました。さすがIMO代表、ちょっと説明しただけですぐルールを分かってくれます…

そして近くの城?に行きました。丘の上にあったので景色が綺麗でした。
皆さんで集合写真を取りました。

JPN5が高熱を出し始めました。大丈夫でしょうか…

7月18日

京アニのニュースを知り悲しい気持ちになりました。
カナダの選手に京アニを心配されました。

Roman Bath

f:id:yootaamath:20190728085250j:plain
バースの有名な温泉の遺跡に行きました。イギリスには本当に温泉がないらしく、この温泉は貴重で、古代ローマ時代から文化的にも宗教的にも大切だったらしいです。
昔から建築技術がこんなに高かったのかと驚きました。
温泉の水を飲めるコーナーが有りました。

Comedy Walk

Comedy Walkというものに参加しました。ガイドさんがわかりやすく面白い解説をしながらバースの街を散歩するものでした。なかなか楽しかったです。

Fish and Chips

f:id:yootaamath:20190728085311j:plain
イギリスに来たということでFish and Chipsを食べました。
思ったよりはまずくなかったです。Fishはたしかに美味しかったです。
しかしなんでFish and Chipsなんでしょうか…FishとChipsがあって相乗効果もなにもないです。
とにかくじゃがいも好きですね。食堂でもずっとじゃがいもが出てきている気がします。

フリスビー

外国の選手などとしました。めっちゃうまいおじさんがいました。

7月19日

漫画(ごちうさのアンソロジー)を読んでいたら観光のバスで外国の選手に「なんの漫画を読んでるの?」って言われ、表紙を見せたら"Oh!! GOCHIUSA!!!"って言われました。ごちうさは世界を繋ぐ。
ごちうさは好き?って聞いたら、自分はそれほどではないけど好きな友人がいるとのことでした。

ストーンヘンジ

f:id:yootaamath:20190728085331j:plain
かの有名なストーンヘンジに行きました。
巨石が並んでいます。
現代でも何のために作られたかよくわかってないらしいです。しかし太陽の登る方角に関係があることから、天文学の知識があることは確からしいです。また石はかなり遠くから運んできたらしいです。
セルビアのガイドさんにお世話になりました。結構面白い人で、結構ムキムキでした。
また、ボスニアの日本語が話せる選手に会えました。5つくらい言語が話せるらしい。すごい…!
雨が降っていてとても寒かったです。

ソールズベリー

f:id:yootaamath:20190728085344j:plain
ソールズベリー大聖堂に行きました。非常に美しい教会でした。とても疲れていたので協会の中で寝てしまいました。ぐっすり寝られました。
マグナカルタを見ました。
CDとか買いました。

コンテストの得点

あるスプレッドシートに現在の自分の点数がリアルタイムで書かれているらしく、本当に心臓に悪いなと思いました。どの人も1つの問題の得点を非表示にされます。なので余計に心臓に悪いです。
Day 1 で満点を取れていると知り嬉しく思いました(特に問題3の満点は嬉しかったです)。

夜はmaoを外国の選手としました。結構な国の人がいました。しかしmaoなのでほとんどゲームの内容しか口にしません。楽ですね。

結果発表

maoをしていたら途中でIMOの結果が出ていると報告を受けました。まっさきに結果を確認しました。
金メダルでした。本当に嬉しかったです。また他の日本の代表5人が全員メダルを取れていて嬉しかったです。JPN4も金メダルで嬉しかったです。
オブザーバーの方々も来ました。皆さんで集合写真を取りました。

7月20日

最も虚無な日です…
代表5人で「今日はJPN5が勝ち組だった」って言ってました。

Fermi Questions

ここはScience Olympiadではないですが、なんか企業主催のイベントでフェルミ推定をするものがありました。結果は普通でした。特にいい順位ではありませんでした。しかしみんなでワイワイ問題について話し合えて楽しかったと思います。

ハイキング(?)

虚無!虚無!虚無!虚無!虚無!
どこかの国のガイドさんのうるさいおばさんがいました。うるさいおばさんが「水がないとお前らのハイキングの保証ができない」というので急いで水を買ってきましたが、水が支給されました。クソ
そこからハイキング?が始まりました。どこに行くか全然知らないのでただただ従って歩いていくのですがなにか景色がいいわけでもなく何があるんだろう??っていう気持ちでした。うるさいおばさんが「時間がない、これはウォーキングではなくハイキングだ」ってうるさかったです。で気がつくと大学に戻っていた??ので本当に虚無でした。

講演会

バスに乗る前、うるさいおばさんが「バスが来たらみんな奥へ奥へ行け」ってうるさかったです。バスに乗ってからも「みんなは数学はできるかもしれないけどバスに乗ることすらできない、ただバスに乗るだけなのにできない」ってうるさかったです。

ベン・グリーンさんの講演会がありました。自分の目が悪かったのと、スライドの文字が小さかったのと、公園が英語だったのと、内容が難しかったことから、自分にはあまり理解ができませんでした…

カラオケ

僕とJPN1の2人で行きました。
これは楽しかったです。みんなで大合唱という感じでした。
DespacitoやLet it Goといった有名な曲は歌えたのですが、知らない曲も多かったです。歌えなくてもとりあえず乗るのが良いです。
ここで"I am a parallelogram"という曲に出会いました。中毒性がとても高く日本選手の中で話題になりました。
www.youtube.com

ココアリベンジ

JPN4がまずココアを恐る恐る注いでみると、とても濃いココアで、JPN4が「これマジで美味い」って言いました。次に僕が注いでみると、確かに濃いココアで、甘くてよく知っているようなココアでとても美味しかったです。次にJPN2が注ぎました。まだ美味しいものの味はそこまででした(もう?)。次に注いだJPN1は、もっと美味しいココアを知っていると、やや不評でした。次のJPN6となるともう今までのココアと同じでした。
美味しいココア、数杯でなくなっちゃうの?????
とはいえ機械の問題で安心しました。
このころからじゃがバターをすればいいことに気づきました。なんと気づくのが遅かったことか…!

7月21日

午前中

市街地に行ってお土産を買っていました。

表彰式

f:id:yootaamath:20190728085430j:plain
テントの下で行われました。移動遊園地が来ていました。なぜ?
映像でオブザーバーの村上さんと藏田さんがガッツリ写っていました。
表彰式では、1列ずつ呼ばれたあと(名前は呼ばれず、画面に映る)、メダルを各国のオブザーバーからもらい、自国の旗を胸の前で広げるといったことをしました。
そのあといくつか写真を取りました。
移動遊園地、結構絶叫アトラクションでびっくりしました。めっちゃ回ってました。

夕食はテント内に屋台やバンドが来ていました。昔のロックとかポップスを演奏していました。オブザーバーの先生に昔のロックに詳しい人がいて、色々とその話を聞いていました。
曲に合わせて踊っている人もいました。

その後

帰国のためのバスが深夜2時になるらしく、田崎さんに寝るなって言われました。なのでバスに乗ってからはめちゃ眠かったです。
もういよいよ帰国かあ~~
空港には極度乾燥(しなさい)のショップやYO!活があって面白かったです。

7月22日

7月21日と地続きみたいな感じなんですけどね(寝てないため)。
空港でみんな寝てました。

飛行機

giftedを見ました。リアルな内容だと思いました。
Hidden Figuresを見ました。かなり感動しました。
tedを見ました。かなりのくだらなさに笑いました。
小学生並みの感想…

7月23日

誕生日

JPN5の誕生日でした。前からこっそり書いていた誕生日カードをプレゼントしました。

日本

久しぶりの日本!!!!
暑い!!!!!!

表敬訪問

何も言うことを考えてなかったため、はじめまともなことをすべて言ってしまい、あとの人をかなり困らせました。本当にすいません。

その後

JPN1と一緒に神保町のエチオピアでカレーを食べたあと、書泉グランデご注文はうさぎですか??の謎解きをやりました。難易度はやや簡単で、初心者に教育的な謎解きだったと思います。←今まで1回しかやったことがないくせに何言ってんだ

まとめ

ごちうさはいいぞ

いいぞ

真面目に

今回始めてのIMOで金メダルをとることができ、本当に嬉しく思っています。
このIMOの体験すべてを将来の糧にしていきたいです。

数学徘徊記のほうで書いた競技数学の記事

なぜまとめたか?

数学徘徊記は競技数学以外の数学、本ブログは競技数学という感じで棲み分けしたくなったのでしました。
記事自体は移すつもりはありませんがリンクをまとめます。

競技数学に入るか入らないか微妙なものもあるんですが、ちょっとかすりそうだったら入れています。

思ったこと

昔の記事を見ると恥ずかしくて初々しい気持ちになります。

LTEの補題(2)

su-hai.hatenablog.com
昔書いた記事ですが、何度か「これよりも簡単に証明できる」と言及されたので、(実質同じなんですけど)書きます。

\(x-y=kp^d\)とするとき、二項定理より
\[\begin{eqnarray}
x^n-y^n&=&(y+kp^d)^n-y^n\\
&=&ny^{n-1}kp^d+\frac{n(n-1)}2y^{n-2}k^2p^{2d}+Cp^{3d}\\
&=&p^d\left(ny^{n-1}k+\frac{n(n-1)}2y^{n-2}k^2p^d+Cp^{2d} \right)\cdots ☆
\end{eqnarray}\](\(C\)は整数)である。

  • \(\mathrm{ord}_p n=0\)のとき

☆より、\(p\mid \hspace{-.67em}/n,y,k\)であることに注意すると、\(\mathrm{ord}_p(x^n-y^n)=d\)を得る。

  • \(n=p\)のとき

☆より、\[x^p-y^p=p^{d+1}\left(y^{n-1}k+\frac{p-1}2y^{n-2}k^2p^d+Cp^{2d-1} \right)\]であるので、\(\mathrm{ord}_p(x^p-y^p)=d+1\).

  • 一般のとき

\(\mathrm{ord}_p n\)についての数学的帰納法。\(\mathrm{ord}_p n=0\)のときについてはもう示した。\(\mathrm{ord}_p n=k\)のときに成り立つとし、\(\mathrm{ord}_p n=k+1\)のときについて考える。\(x\equiv y \pmod p\)より\(x^p\equiv y^p \pmod p\)であるので、
\[\begin{eqnarray}
\mathrm{ord}_p (x^n-y^n)&=&\mathrm{ord}_p ((x^p)^{n/p}-(y^p)^{n/p})\\
&=& \mathrm{ord}_p (x^p-y^p)+\mathrm{ord}_p (n/p)\\
&=&d+k+1
\end{eqnarray}\]であるので\(\mathrm{ord}_p n=k+1\)の場合も成り立つ。
以上より、LTE補題が示された。

P.S. LTE補題の証明は数オリでは必要なさそうです。
P.S. やはり必要らしいです、代表選考とかでは時間がない場合はいいけどあるのなら書くべきと先輩に言われました

2019JMO代表選考合宿参加記

代表選考合宿について

春休みごろ行われる、数学オリンピックの日本代表を選考するための合宿です。
6人が日本代表に選ばれます。

JMOで優秀賞以上、JJMOで銀メダル以上を獲得すると参加することが出来ます。
ただし、新高3、つまり高2までがこの選考に参加することが出来ます。つまり私にとってこれが最後です。

そのほかにも、過去の日本代表が主であるチューターさんたちが参加します。

試験の形式は、IMOと同じ形式・ほぼ同じ難易度の試験を4日間行います。
1日3問4時間半です。

試験の問題については公開を固く禁じられているため(他国での代表選考にも使われるので)ここでは言えません。
感想とか手ごたえとかも危なそうなので言いません。

場所はオリンピックセンターでした。花見の名所です。
到着時は桜はまだ咲いていませんでしたが、合宿の終わりごろはかなり咲いていてとてもきれいでした。
f:id:yootaamath:20190328130630p:plain

1日目

表彰式がありました。そのあと開講式や自己紹介がありました。
去年も参加していたので、知っている人がまあまあいました。
今日は早く寝ました。午後8時。

2日目

ここからが本番です。
午前中は演習でした。チューターさんが問題やよく使われる考え方などを紹介するという形です。
今日は幾何と整数論でした。
幾何はMiquel点や回転相似についてでした。
整数論はいろいろな問題を扱う感じでした。最初の問題が mod 19 を用いる一発芸の問題だったので mod 19 が合宿のトレンドになりました。

試験 Day 1 でした。(さっき書きましたが感想は言いません)

夜はちょっと遊びました。数オリ界隈、SETがかなり流行ってます。
ja.wikipedia.org
みんなめっちゃ速くて怖いです。

でも試験があるので10時には寝る感じです。

3日目

午前中は今日も演習でした。
今日は代数と組み合わせでした。
代数もいろいろな問題を扱う感じでした。きおな君がとてもきれいな解法を発見してすげえってなりました。
組み合わせはかなり競プロでした(担当のチューターがyutaka氏だったので)。

試験 Day 2 でした。

4日目

午前中は講義でした。講義もチューターさんが行います。
グラフの隣接行列と固有値という内容でした。
普通はめっちゃ難しい内容をやって生徒がかなりおいていかれるという感じなのですが、今回は講義が親切で最後までついていけました。
グラフの問題を隣接行列の固有値に注目することで不定方程式をつくって頂点の数とかを絞るという内容で、とても興味を持ちました。

試験 Day 3 でした。

試験で疲れてゲームをする気力も起きなくなってしまったので、ずっと雑談などしてました。
あとJMOやAPMOの解答の見せあいもしました。
かなり楽しかったです。あと高1どうしのつながりが多くてすごいなあってなりました。
自分は算数オリンピックとか全く入賞したことがないのでね…

5日目

午前中は演習でした。
今日は特に内容は決まっておらず、チューターが何問かおすすめの問題を紹介して解説するという形でした。

試験 Day 4 でした。

立食会がありました。ビンゴ大会などがありました。
景品で「タイムボム」というカードゲームをもらいました。

試験がすべて終わったので夜更かししてみんなで遊びました。
もらったタイムボムを早速遊びました。
爆弾を爆発させたい陣営とさせたくない陣営がいて、誰がどの陣営か分かっておらず、心理戦をしながらさぐって自分の陣営の勝利を目指すという感じのゲームです。
人狼みたいな感じですが、ルールがとてもシンプルで、かつ奥深く、脱落者も最後まで出てこないので、とっても面白かったです。

6日目

今日は閉講式を手早くやってすぐ解散という感じでした。
まあ夜更かししていたのでぐったりとしてました。

せっかく東京に来たので初めての二郎に行きました。
とても美味しかったです。
f:id:yootaamath:20190327224908p:plain

また書泉グランデと明倫館に行きました。数学書をいくつか買いました。

全体を通しての感想

やはりメインは代表選考試験なので疲れます。
でも趣味の合う人たちと沢山話せるので楽しいです。
あとは結果を祈るだけですね…

2019 JMO 本選 問1~4 解説 (追記:問5)

全体の感想

難易度は1<2<3<4<5だと思いました.
問5はまだ解けていません…
(追記: 解答を載せました(自力ではないですが))

問1

感想

やればできる不定方程式の問題です.
なんでJMOは5年連続問1に整数を置くんですか?????

略解

\(b\)と\(c\)の大小で場合分け.
・\(b=c\)のとき
\(a^2+b+3>0\)より解なし.
・\(b>c\)のとき
\(a^2=(b^2-c^2)^2-b-3<(b^2-c^2)^2\)
\(b>c\geq 1\)より\(b^2-c^2\geq 1\)であり, \(a^2,(b^2-c^2)^2\)はともに平方数なので
\[\begin{eqnarray}
(b^2-c^2)^2-b-3&\leq&(b^2-c^2-1)^2\\
- b-3&\leq&-2(b^2-c^2)+1\\
b^2-\frac b2-2&\leq&c^2
\end{eqnarray}\]ここで\(b>2\)のときは\[(b-1)^2< b^2-\frac b2-2\leq c^2\]が成り立つが, これは\(b>c\)という仮定に矛盾. よって\(b\leq 2\)である. この場合は\((a,b,c)=(2,2,1)\)のみ.
・\(b< c\)のとき
さっきと同じような感じで解くと解がないことがわかる(やってみてください).

問2

感想

1回1回得点が入るのが面倒臭いですね…
これもやればできる問題だったと思います.
記述がちょっと大変そう?

略解

\(\pmod n\)のみが本質のため1を\(n\)個, 2を\(n\)個, ... , \(n\)を\(n\)個書くとしてよい.
各行・列に注目したときの, 「その行・列で総和が変更されてそれが\(n\)の倍数となる回数」をその行・列のスコアと呼ぶことにする.
最終的な得点は, 各行・列のスコアの総和に等しい.
ある行に注目するとき, 最終的にその行にかかれる数の総和が\(S\)ならば, 書かれる数がすべて正であるため, その行が\(n\)の倍数になる回数=スコアは\([S/n]\)以下である.
\(i\)行目に書かれる数の総和を\(S_i\)とするとき, 行全体におけるスコアの総和は
\[\begin{eqnarray}
\Big[\frac{S_1}{n}\Big]+\Big[\frac{S_2}{n}\Big]+\cdots+\Big[\frac{S_n}{n}\Big] &\leq&\Big[\frac{S_1+S_2+\cdots+S_n}{n}\Big]\\
&=&\Big[\frac{n(1+2+\cdots+n)}{n}\Big]\\
&=&\frac{n(n+1)}{2}
\end{eqnarray}\]以下である. 列についても同様なので, 結局最終的な得点は\(n(n+1)\)以下.
得点を\(n(n+1)\)にすることが可能なことを示す. \(i\)行目, \(j\)列目のマスを\((i,j)\)と表すこととする. また, 任意の整数\((i,j)\)について\((i+n,j)=(i,j+n)=(i,j)\)とする.
以下の操作を\(k=n,1,n-1,2,\dots,\frac{n-1}{2},\frac{n+1}{2}\)の順に繰り返す:
マス\((0,k),(1,k+1),\dots,(n-1,k+n-1)\)に\(k\)を書き込む.
これで得点\(n(n+1)\)とれることの証明は略す(やればできるので…).

問3

感想

ちょっと簡単目の関数方程式だったと思います.
感覚でいろいろやれば解ける感じだったので個人的に楽でした.

略解

このサイトの解が結構きれいです.
JMO2019本選問3 | 凸レンズの部屋(仮)

問4

感想

解けませんでした…後輩から解説を聞きましたが解けるべきでした…

略解

図のように点を取る. \(DM=ME\)となるのは有名な構図.
f:id:yootaamath:20190215172623p:plain
すると\(\angle DGE=90^\circ\)より\(MD=MG\). よって\(MG\)は\(\omega\)に接し, \(\angle IG M=90^\circ\)である. すると四角形\(AHJM\), 四角形\(AHDG\), 五角形\(IDJMG\)はそれぞれ円に内接する. この3つの円の根心は\(K\)となるため, \(G,D,K\)は共線. \(AK//FD\)より\(GF:GA=GD:GK\)で, \(\odot AGK\)は\(\omega\)と点\(G\)で接する.

問5

感想

本番では何もできそうになかったので白紙でした(よくない)

略解

2019 JJMO 本選 解説

全体の感想

難易度は1=2<4=5<3な気がしました(あくまでも個人の感想です).
例年よりちょっと難しいくらいな気がします.
問題→第17回(2019年)JJMO 本選 の問題
解答で略している部分があります, すみません

問1

感想

ちょっと(1分くらい)悩みましたが, 30°なので外心をとってみるとなんかできました.

解説

f:id:yootaamath:20190215203918p:plain
\(\triangle ABD\)の外心を\(O\)とするとき
\(\angle AOD=2\angle ABD=60^\circ\)より\(\triangle AOD\)は正三角形.
よって\(AD=OD\).
また\(\angle BOD=2\angle BAD=\angle BAC, OB:OD=AB:AC=1:1\)より\(\triangle BOD\sim \triangle BAC\).
すると\(AC:BC=BD:OD=BD:AD\).
よって角の二等分線定理より示された.

問2

感想

やればできるという感じです.

解説

自分で書くのは面倒くさいので…(すみません)
JJMO本選2019問2 | 凸レンズの部屋(仮)

問3

感想

たぶん今回のJJMOの中で一番難しいと思います.

解説

(1) \(a+b+1=x\)とおくとき
\(\gcd(a,b+1)=\gcd(x,a)\)
\(\gcd(a+1,b)=\gcd(x,a+1)\).
背理法で示す.
\[\gcd(x,a),\gcd(x,a+1)>\frac{\sqrt{4x+1}-1}{2}\]と仮定して矛盾を導く.
\(a\)と\(a+1\)は互いに素より
\[\gcd(x,a)\neq \gcd(x,a+1)\]\[\gcd(x,a(a+1))=\gcd(x,a)\cdot \gcd(x,a+1)\]よって\(\gcd(x,a),\gcd(x,a+1)\)のどちらかは\(\cfrac{\sqrt{4x+1}+1}{2}\)より大きく
\[\begin{eqnarray}
\gcd(x,a(a+1))&=&\gcd(x,a)\cdot \gcd(x,a+1)\\
&>&\frac{\sqrt{4x+1}+1}{2}\cdot \frac{\sqrt{4x+1}-1}{2}\\
&=&x
\end{eqnarray}\]となるが矛盾.

(2)\(\min(\gcd(x,a),\gcd(x,a+1))=\cfrac{\sqrt{4x+1}-1}{2}\)は整数なので\(4x+1\)は平方数.
よって\(x=n^2+n\)(\(n\)は正の整数)とおける.
このとき\(\cfrac{\sqrt{4x+1}-1}{2}=n\).
\(\gcd(x,A)=n\)(ただし\(A=a\)または\(A=a+1\))なる\(A\)がある. \(B=2a+1-A\)とする.
\(\gcd(x,A)\neq\gcd(x,B)\)かつ\(\min(\gcd(x,A),\gcd(x,B))=n\)より\(\gcd(x,B)\geq n+1\)であるが\(\gcd(x,A)\cdot \gcd(x,B)=\gcd(x,a(a+1))\leq x\)より\(\gcd(x,B)\leq n+1\). よって\(\gcd(x,B)=n+1\).

\(\gcd(x,a)=n,\gcd(x,a+1)=n+1\)のとき, \(a=kn,a+1=l(n+1)(1\leq k\leq n, 1\leq l\leq n-1)\)とおける.
すると\(a=kn=ln+l -1\)だが, \(0\leq l -1< n\)より\(k=l\). すると\(k=l=1\)より\(a=n\)がわかる.
\(\gcd(x,a)=n+1,\gcd(x,a+1)=n\)のときも同様にすると\(a=n^2-1\)がわかる.

よって\((a,b)=(n,n^2-1),(n^2-1,n)\).

問4

感想

難しいような簡単なような…
いろいろな方法がありますが思いつかないと難しいでしょう(無難なコメント).
構成も意外と出てこなかったりしそうです.

解説

図のような感じで塗り分ける.
f:id:yootaamath:20190215172616p:plain
駒が通った道筋を辺とするとき
●から出た斜めの辺の本数=○から出た斜めの辺の本数
●から出た斜めの辺の本数\(\leq 2\times\)(●の数)=\(\cfrac{(n-1)^2}{2}\)
○から出た辺の本数\(\geq 2\times\)(○の数)\(-2\)=\(\cfrac{(n+1)^2}{2}-2\)
○から出た斜めでない辺の本数
=○から出た辺の本数-○から出た斜めの辺の本数
\(\geq\cfrac{(n+1)^2}{2}-2-\cfrac{(n-1)^2}{2}\)
\(=2n-2\)
構成は略します.

別解

こちらのサイトに別解と構成があります.
こちらのほうがきれいな感じがします.
JJMO本選2019問4 | 凸レンズの部屋(仮)

問5

感想

5番の割にはそんな難しくない気がします.
JJMO, なんで3年連続で5番にGをおくのでしょうか???

解説

学校の後輩が天才的な解法を見つけてくれたので書きます.
f:id:yootaamath:20190215172619p:plain
\(\odot AMC\)と直線\(AN\)の交点を\(P\)とおくと, 簡単な角度計算で
\(\triangle NHA\sim \triangle NMC\)
\(\triangle KAN\sim \triangle PCN\)
がわかるので
\(四角形KAHN\sim 四角形PCMN\).
すると対応する角度が等しいので
\(\angle AKH=\angle CPM\)
すると円周角の定理より
\(\angle AKH=\angle CAM\).

JMO2019本選参加記

感想

4完する意気込みで行きましたが、4完できませんでした。
くやしい。
1, 2, 3をたぶん解きました。
(致命的なミスをしている可能性が0ではないので、敢えてこう書きます)
4が幾何だったのでときたかったのですが方針を見誤って解けませんでした。
幾何できなくなってますね。精進しないと。

流れ

とりあえず問題をざっくりよむ。
JMO、1番に整数論を置きすぎでは(5年連続???)
2がCで3がAで4がGで5は知らん。セットとしてはうれしい。
なぜか4問めに手をつけ始める。解けん。
さすがに数分であきらめて、1~3をそれぞれ5分くらい考えることにした。
1は平方数で挟みまくれば何とかなる感じ。難しくなさそう。
2はちょっと大変そう。1手ごとに得点が加算されるのなんだかなあ。
3はいろいろできた。
というわけで最初に3を考え、わりとすんなり解くことができた。(ここまで30分)
とりあえず1をちゃんと考察する。確かにしっかりとやれば解けた。(ここまで45分)
次に4。解けん。示したいことをいろいろ言い換えるなどして頑張ってみたが解けん。かなり時間を使った。
行き詰っているので2へ。小さい\(n\)で具体例を探していく。なんとなく最大がわかったし、なんで最大になるのかわかってきたので、精密に考えてみるとやっぱり解けた。
はい3完(ここまで1時間半)。やったね。今年は簡単? Gがのこっているので考えます
やっぱり解けないわ。(ここまで2時間)
答案をまだ書いていなかったので書きます。
結構時間を使ってしまった。(ここまで2時間50分)
よし4。さすがに答案を書くのに時間をかけそうなので、さすがに使うような部分と構図の証明だけ書いておく。

解けませんでした。おわり。

解説

後で書きます
すいません
あと5は解けるか知りません

2019 JMO 予選 解説・感想

これから受験記はこちらのブログで書くことにします.
2018→2018JMO受験記 - 数学徘徊記

意気込み

今年は予選免除なのですが, せっかくなので頑張ってみます.
2ケタの点数を取りたいですね.

結果

7点でした. 不甲斐ない結果…
幾何の問題(4, 8)を計算ミスして両方とも間違えたのが痛いですね…

全体の感想

今年, 去年に比べて難しくないですか??
3, 4, 6番に骨のある問題があってきつかったと思います.
幾何が得意なつもりだったので問10に特攻しましたが自分のほうが砕けました…

そういえば最高点8点なんですね, やばくないですか?

解説

思考過程を書こうかな…

問1

31が\(x\)の倍数となるので\(x=1,31\)ですが\(x=31\)はさすがにダメなので\(x=1\)です.
すると\(y(1+z)=30\)となるので\(y,z\)も容易に列挙できます.
JMO予選の割にはかなり簡単かな…?

問2

一の位で場合分けすると5にしかならないことがわかります.
また2乗して5桁になることより百の位が2になることがわかります.
あとは4つすべて試します.

問3

これ見た目つらそうだったので飛ばしてあとのほうにやりました.
意外と少ないですよね…
自分は1と9の位置で場合分けしました.
1と9は3つ以上離れてないといけないので場所が3通りに決まって, あといろいろ考えると大体の数字が決まることがわかります.
中心の数で場合分けする方針もあるようです.

問4

計算ミスしました(なんで???)
自分の実力ですね…
まあ平行をいろいろ作って比で計算するだろうなあ, という気持ちになりました.
f:id:yootaamath:20190120151425p:plain
図のようにおけば, \(x:(4-x)=5:(x-1)\)となって, あとは2次方程式を解けばよいです.

問5

3倍して1を足すとおしまいです, 問5の割に簡単?
求める数を\(n\)とおくと\(3n+1\)は97, 100, 103の倍数になるので, \(n\)が最小だということを考えると\(n=\frac{97\cdot 100\cdot 103 -1}{3}\)です.

問6

これ細かいところを詰めるのが若干大変です. ちょっと手こずりました.
問題文では正120角形ですが, 頂角18°の二等辺三角形を考えると, 正20角形が6つと考えてよいことがわかります. それらの正20角形は互いに影響しないので. このように単純なものに分解するのは重要だと思います.
ここで図のような星形を考えると, 3つの連続した頂点は同じ色であってはいけないことがわかります. もし14個以上頂点があれば, 平均\(14/20\times 3>2\)個3つの連続した頂点上に黒い点があるので, ある3つの連続した頂点上には3つ黒があることがわかりダメです.
星形に沿って白黒黒白黒黒白…と塗り分けていけば13個の構成ができます.
よって答えは13×6=78です.
f:id:yootaamath:20190123140534p:plain

問7

これ結構悩んでしまいました…最後に解きました
本番エスパー解法で解きましたが(答えはあってるものの)嘘解法なのでここでは書きません, すいません…
\(P(x)^2=(Q(x)+R(x))(Q(x)-R(x))\)という式変形が重要です.
これで十分→JMO予選2019問7 | 凸レンズの部屋(仮)

問8

これもミスしました…なぜかずっと\(BC=8\)とやってました.
f:id:yootaamath:20190120152452p:plain
ちょっと幾何的なことをした後ごり押しでやりました
もっと計算簡単にいけるかもしれません…
三角形\(ADIE\)に注目すると, \(AD>AE,ID=I E,\angle DAI=\angle EA I\)なので円に内接します. よって\(\angle BAC=120^\circ\)を満たします.
このあと, 感覚的には点\(M,I,A\)の横のずれに注目して解いていきます.
\(AB=x,AC=y\)とおきます. すると
\[\begin{eqnarray}
BP&=&\frac{x-y+9}{2}\\
BM&=&\frac{9}{2}\\
MP&=&\frac{x-y}{2}\\
MQ&=&\frac{9(x-y)}{16}\\
BQ&=&\frac 92+\frac{9(x-y)}{16}\\
C Q&=&\frac 92-\frac{9(x-y)}{16}\\
\end{eqnarray}\]がわかり, 三平方の定理より
\[\begin{eqnarray}
AB^2-BQ^2&=&AC^2-C Q^2\\
x^2-\left(\frac 92+\frac{9(x-y)}{16}\right)^2&=&y^2-\left(\frac 92-\frac{9(x-y)}{16}\right)^2\\
x^2-y^2&=&4\cdot \frac 92 \cdot \frac{9(x-y)}{16}\\
x+y&=&\frac{81}{8}
\end{eqnarray}\]がわかります.
あと余弦定理より\(x^2+xy+y^2=81\)なので連立して解けば\(x=AB\)がわかります.

問9

これ大好きです, 本番感動しました.
まず, ある行や列について, 3つ決まればもう1つも決まることに注目します.
なので左上の3×3を任意に埋めたとき, その右や下の6つは埋まります.
問題は右下の一つで, これは上から決まるものと左から決まるものが一致するかわかりません.
しかし実験してみると, いつもそれらが一致することがわかります.
予選なので証明しなくても答えは求まりますが, まあ心の安寧のために証明したい…
とりあえず色を1, 2, 3, 4と置き換えます.
ある{1, 2, 3, 4}上の交換・結合法則を満たす演算があって, 三つの色を演算したらもう一つの色が出てくればうれしいなあと考えました.
するとxorがそれを満たすことに気づきました!感動しました.
xorについては, 排他的論理和 - Wikipediaの「ビットごとの排他的論理和」を参照してください.

問10

本番で結構時間を使ったけど解けなくて, その日に夜遅くまで頑張ったのですが解けませんでした.
12問の中で最も難しいんじゃないですかね…
こーとくさんが解答をTwitterにあげていたので載せます.


反転した後の図形と元の図形が似ているので、それらを対応させながら解き進める感じでしょうか.

問11

本番で全く手を付けてませんでしたがたぶん10~12の中で一番簡単です(どれも難しいけど).
手を付ければよかった…
余りのグラフを書いてみると, だいたい\(2019^3/2\)になりそうだなあと見えてきます. しかし例外ケースみたいなものがあって, それらをしっかりと吟味しなければいけない感じです.
のいみさんが解答をTwitterにあげていたので載せます. DMで会話しながら解いたので同じ解答です:


この解答への補足です:
\( (\gcd(k -1,2019^3),\gcd(k,2019^3))=(g_1,g_2)\)(順序は考えない)として考えられる値が25種類ありますが, すべての考えられる組に対しこれを満たすような\(k\)が存在することを証明します.
\( (g_1,g_2)=(3^a,673^b)(a,b\geq 1)\)の場合, \(x\)についての方程式
\begin{eqnarray}
\begin{cases}
x-1\equiv 3^a \pmod{3^3} & \\
x\equiv 673^b \pmod{673^3} &
\end{cases}
\end{eqnarray}
について考えるとこれは中国剰余定理より\(0\leq x \leq 2019^3\)で解を持ちます. これを\(k\)とおくと, \(k -1\)が673で割り切れないこと, \(k\)が3で割り切れないこともわかるので\( (\gcd(k -1,2019^3),\gcd(k,2019^3))=(g_1,g_2)\)を満たします.
\( (g_1,g_2)=(1,3^a673^b)(a,b\geq 0, (a,b)\neq (0,0))\)のときは\(k=3^a673^b\)が満たします.

問12

これ本番でちょろっと手を付けましたができませんでした.
終わってから数時間がんばったらなんとかできました. どんな\(F\)が満たすのかわくわくしながら解くと面白いです.
とりあえず最初は全体集合とか空集合とかを代入してみます. すると\(F(\emptyset)\)が重要そうだなあとなります.
いろいろ代入してみると, \(F\)は\(F(\emptyset)\)の部分集合の中でいい性質(全単射)を満たすことがわかるので, それ以外の集合を\(F(\emptyset)\)の部分集合に帰着することを考えていきます.
帰着できたらあとは\(F\)を吟味します.
Junさんが解答をTwitterにあげていたので載せます.
解答は長いですが上のようなステップを踏めばだいたい同じ解答になると思います.

2014~2018 JMO 予選 問9~11

はじめに

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

JMO予選について

過去問→国内大会・国際大会の問題
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

こういう図形問題は丁寧に描きましょう. まずは普通サイズでフリーハンドで書いてから概要を確かめて, 大きめにコンパスや定規で正確に図を描くのが良いです.
f:id:yootaamath:20181221090258p:plain
図を描いてみると, どうやら点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)}を求めてみましょう.
このままだとわかりにくいですね.
ここで
{\displaystyle F_i(\sigma)=\begin{cases}1&(\sigma(i)=i)\\0&({\rm otherwise})\end{cases}}
と定めてみましょう. すると
{\displaystyle 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のとき, 死ぬ気で余弦定理とかいろいろ使って間違えたのが懐かしいです. 実は複雑な辺の長さの計算はほぼないです.
f:id:yootaamath:20181217165721p:plain
まず点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\}\)など).

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種類(左右逆もあり)です.
f:id:yootaamath:20181217162005p:plain
2016はちょっと大きすぎるので, 少ない場合について考えてみましょう(考えにくい問題の場合は問題を少し一般化して, 小さい場合について考えるということはしばしば有用です). 奇遇に依存しそうな感じがするので, 4, 6, 8,...について考えます.
4のときについて考えると, どのようなとり方でもおんなじ距離にすれば良さそうです.
左右対称なのが良さそうなので, 図のように置いてみましょう.
f:id:yootaamath:20181217163111p:plain
連立方程式を立てると
\[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\)はいくつか?」
図を書いてみます(矢印は確定の部分). f:id:yootaamath:20181220172503p:plain
するとすでに8つでループしちゃっているのがわかります. なので答えは8だけでしょうか?
よく考えると, ループでなくても順列であればいいので, 少しばかり矢印を壊していいことがわかります. すると7つと9つの場合にもできることがわかります. f:id:yootaamath:20181220173239p:plainしかもジョイントもすることができます. f:id:yootaamath:20181220174037p:plainこのように, どのようなときにできるかを少しずつ考えると, 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

f:id:yootaamath:20181221145044p:plain
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

f:id:yootaamath:20181221090245p:plain
図を描いてぼんやり眺めてみます. すると立体的に見えるかもしれません. ピラミッドが平面で切断されているイメージです. (以下立体で考えます)
正四角錐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)\)のみです. 全探索しちゃいましょう.

#35 (2018 IMO 6)

問題

f:id:yootaamath:20180724153313p:plain

感想

3番級G。Gをやってきてよかった。
(来年のIMOはどうなるかわからんが)
(そもそもIMOに行けるかもわからんが)
普通に手ごたえがあって大変だった
使いたいことを使っていく感じで
Lv.8 120分