だま氏の解いた問題たち

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

好きな問題いろいろ

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

だいたい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多くてごめんなさい…
教育的です。