% © Evan Chen
% Downloaded from https://web.evanchen.cc/
\documentclass[11pt]{scrartcl}
\usepackage[sexy]{evan}
\ihead{\footnotesize\textbf{\thetitle}}
\ohead{\footnotesize\href{http://web.evanchen.cc}{\ttfamily web.evanchen.cc},
updated \today}
\title{IMO 2014 Solution Notes}
\date{\today}
\begin{document}
\maketitle
\begin{abstract}
This is a compilation of solutions
for the 2014 IMO.
Some of the solutions are my own work,
but many are from the official solutions provided by the organizers
(for which they hold any copyrights),
and others were found by users on the Art of Problem Solving forums.
These notes will tend to be a bit more advanced and terse than the ``official''
solutions from the organizers.
In particular, if a theorem or technique is not known to beginners
but is still considered ``standard'', then I often prefer to
use this theory anyways, rather than try to work around or conceal it.
For example, in geometry problems I typically use directed angles
without further comment, rather than awkwardly work around configuration issues.
Similarly, sentences like ``let $\mathbb{R}$ denote the set of real numbers''
are typically omitted entirely.
Corrections and comments are welcome!
\end{abstract}
\tableofcontents
\newpage
\addtocounter{section}{-1}
\section{Problems}
\begin{enumerate}[\bfseries 1.]
\item %% Problem 1
Let $a_0 < a_1 < a_2 < \dotsb$ be an infinite sequence of positive integers.
Prove that there exists a unique integer $n\geq 1$ such that
\[ a_n < \frac{a_0+a_1+a_2+\dotsb+a_n}{n} \le a_{n+1}. \]
\item %% Problem 2
Let $n \ge 2$ be an integer.
Consider an $n \times n$ chessboard consisting of $n^2$ unit squares.
A configuration of $n$ rooks on this board is \emph{peaceful}
if every row and every column contains exactly one rook.
Find the greatest positive integer $k$ such that,
for each peaceful configuration of $n$ rooks,
there is a $k \times k$ square which does not
contain a rook on any of its $k^2$ unit squares.
\item %% Problem 3
Convex quadrilateral $ABCD$ has $\angle ABC = \angle CDA = 90\dg$.
Point $H$ is the foot of the perpendicular from $A$ to $\ol{BD}$.
Points $S$ and $T$ lie on sides $AB$ and $AD$,
respectively, such that $H$ lies inside triangle $SCT$ and
\[ \angle CHS - \angle CSB = 90^{\circ},
\quad \angle THC - \angle DTC = 90^{\circ}. \]
Prove that line $BD$ is tangent to the circumcircle of triangle $TSH$.
\item %% Problem 4
Let $P$ and $Q$ be on segment $BC$ of an acute triangle $ABC$
such that $\angle PAB=\angle BCA$ and $\angle CAQ=\angle ABC$.
Let $M$ and $N$ be points on $\ol{AP}$ and $\ol{AQ}$,
respectively, such that $P$ is the midpoint of $\ol{AM}$
and $Q$ is the midpoint of $\ol{AN}$.
Prove that $\ol{BM}$ and $\ol{CN}$ meet on the
circumcircle of $\triangle ABC$.
\item %% Problem 5
For every positive integer $n$,
the Bank of Cape Town issues coins of denomination $\frac 1n$.
Given a finite collection of such coins (of not necessarily different denominations)
with total value at most $99 + \frac12$, prove that it is possible to split
this collection into $100$ or fewer groups, such that each group has total value at most $1$.
\item %% Problem 6
A set of lines in the plane is in \emph{general position}
if no two are parallel and no three pass through the same point.
A set of lines in general position cuts the plane into regions,
some of which have finite area; we call these its \emph{finite regions}.
Prove that for all sufficiently large $n$,
in any set of $n$ lines in general position
it is possible to colour at least $\sqrt{n}$ lines blue
in such a way that none of its finite regions
has a completely blue boundary.
\end{enumerate}
\pagebreak
\section{Solutions to Day 1}
\subsection{IMO 2014/1, proposed by Gerhard Woeginger (AUT)}
\textsl{Available online at \url{https://aops.com/community/p3542095}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $a_0 < a_1 < a_2 < \dotsb$ be an infinite sequence of positive integers.
Prove that there exists a unique integer $n\geq 1$ such that
\[ a_n < \frac{a_0+a_1+a_2+\dotsb+a_n}{n} \le a_{n+1}. \]
\end{mdframed}
Fedor Petrov presents the following nice solution.
Let us define the sequence
\[ b_n = \left( a_n - a_{n-1} \right) + \dots
+ \left( a_n - a_1 \right). \]
Since $(a_i)_i$ is increasing,
this sequence is unbounded, and moreover $b_1 = 0$.
The problem requires an $n$ such that
\[ b_n < a_0 \le b_{n+1} \]
which obviously exists and is unique.
\pagebreak
\subsection{IMO 2014/2, proposed by Croatia}
\textsl{Available online at \url{https://aops.com/community/p3542094}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $n \ge 2$ be an integer.
Consider an $n \times n$ chessboard consisting of $n^2$ unit squares.
A configuration of $n$ rooks on this board is \emph{peaceful}
if every row and every column contains exactly one rook.
Find the greatest positive integer $k$ such that,
for each peaceful configuration of $n$ rooks,
there is a $k \times k$ square which does not
contain a rook on any of its $k^2$ unit squares.
\end{mdframed}
The answer is $k = \left\lfloor \sqrt{n-1} \right\rfloor$, sir.
First, assume $n > k^2$ for some $k$.
We will prove we can find an empty $k \times k$ square.
Indeed, let $R$ be a rook in the uppermost column,
and draw $k$ squares of size $k \times k$ directly below it, aligned.
There are at most $k-1$ rooks among these squares, as desired.
\begin{center}
\begin{asy}
unitsize(0.75cm);
usepackage("chessfss");
for (int i=1; i<=4; ++i) {
draw( (0,i)--(5,i), grey );
draw( (i,0)--(i,5), grey );
}
draw(box( (0,0),(5,5) ), black);
filldraw( box((1.1,2.1),(2.9,3.9)), opacity(0.2)+palered, red+1 );
filldraw( box((1.1,0.1),(2.9,1.9)), opacity(0.2)+lightgreen, blue+1 );
label("\WhiteRookOnBlack", (1.5,4.5));
\end{asy}
\end{center}
Now for the construction for $n=k^2$.
We draw the example for $k=3$ (with the generalization being obvious);
\begin{center}
\begin{asy}
unitsize(0.8cm);
usepackage("chessfss");
filldraw(box( (0,0), (3,3) ), opacity(0.2)+palered, black+1);
filldraw(box( (3,0), (6,3) ), opacity(0.2)+lightgreen, black+1);
filldraw(box( (6,0), (9,3) ), opacity(0.2)+lightcyan, black+1);
filldraw(box( (0,3), (3,6) ), opacity(0.2)+lightgreen, black+1);
filldraw(box( (3,3), (6,6) ), opacity(0.2)+lightcyan, black+1);
filldraw(box( (6,3), (9,6) ), opacity(0.2)+palered, black+1);
filldraw(box( (0,6), (3,9) ), opacity(0.2)+lightcyan, black+1);
filldraw(box( (3,6), (6,9) ), opacity(0.2)+palered, black+1);
filldraw(box( (6,6), (9,9) ), opacity(0.2)+lightgreen, black+1);
for (int i=1; i<=8; ++i) {
if ( (i-3)*(i-6) != 0) {
draw( (0,i)--(9,i), grey );
draw( (i,0)--(i,9), grey );
}
}
label("\BlackRookOnWhite", (0.5,0.5));
label("\BlackRookOnWhite", (3.5,1.5));
label("\BlackRookOnWhite", (6.5,2.5));
label("\BlackRookOnWhite", (1.5,3.5));
label("\BlackRookOnWhite", (4.5,4.5));
label("\BlackRookOnWhite", (7.5,5.5));
label("\BlackRookOnWhite", (2.5,6.5));
label("\BlackRookOnWhite", (5.5,7.5));
label("\BlackRookOnWhite", (8.5,8.5));
\end{asy}
\end{center}
To show that this works,
consider for each rook drawing an $k \times k$ square of $X$'s
whose bottom-right hand corner is the rook (these may go off the board).
These indicate positions where one cannot
place the upper-left hand corner of any square.
It's easy to see that these cover the entire board,
except parts of the last $k-1$ columns,
which don't matter anyways.
It remains to check that $n \le k^2$ also all work
(omitting this step is a common mistake).
For this, we can delete rows and column to get an $n \times n$ board,
and then fill in any gaps where we accidentally deleted a rook.
\pagebreak
\subsection{IMO 2014/3, proposed by Iran}
\textsl{Available online at \url{https://aops.com/community/p3542092}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Convex quadrilateral $ABCD$ has $\angle ABC = \angle CDA = 90\dg$.
Point $H$ is the foot of the perpendicular from $A$ to $\ol{BD}$.
Points $S$ and $T$ lie on sides $AB$ and $AD$,
respectively, such that $H$ lies inside triangle $SCT$ and
\[ \angle CHS - \angle CSB = 90^{\circ},
\quad \angle THC - \angle DTC = 90^{\circ}. \]
Prove that line $BD$ is tangent to the circumcircle of triangle $TSH$.
\end{mdframed}
\paragraph{First solution (mine).}
First we rewrite the angle condition in a suitable way.
\begin{claim*}
We have $\angle ATH = \angle TCH + 90\dg$.
Thus the circumcenter of $\triangle CTH$ lies on $\ol{AD}$.
Similarly the circumcenter of $\triangle CSH$ lies on $\ol{AB}$.
\end{claim*}
\begin{proof}
\begin{align*}
\dang ATH &= \dang DTH \\
&= \dang DTC + \dang CTH \\
&= \dang DTC - \dang THC - \dang HCT \\
&= 90\dg - \dang HCT = 90\dg + \dang TCH.
\end{align*}
which implies conclusion.
\end{proof}
\begin{center}
\begin{asy}
pair A = dir(110);
pair B = dir(200);
pair D = dir(-20);
pair C = -A;
pair H = foot(A, B, D);
pair Cs = -C+2*foot(origin, H, C);
pair As = -A+2*foot(origin, A, H);
filldraw(unitcircle, opacity(0.1)+lightcyan, lightblue);
draw(A--B--C--D--cycle, lightblue);
pair M = midpoint(B--As);
pair N = midpoint(D--As);
pair U = IP(Cs--N, circumcircle(D, H, As));
pair V = IP(Cs--M, circumcircle(B, H, As));
pair Ss = D+As-U;
pair Ts = B+As-V;
pair T = extension(Ts, H, A, D);
pair S = extension(Ss, H, A, B);
pair O_D = circumcenter(C, H, T);
filldraw(circumcircle(C, H, T), opacity(0.1)+yellow, red);
pair P = extension(A, H, O_D, midpoint(T--H));
draw(A--H, lightblue);
draw(B--D, lightblue);
draw(H--C--T--cycle, red);
draw(H--O_D, lightblue);
draw(P--O_D, heavygreen);
dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$D$", D, dir(D));
dot("$C$", C, dir(C));
dot("$H$", H, dir(H));
dot("$T$", T, dir(80));
dot("$S$", S, dir(S));
dot("$O_D$", O_D, dir(45));
dot("$P$", P, dir(45));
/* TSQ Source:
A = dir 110
B = dir 200
D = dir -20
C = -A
H = foot A B D
C* := -C+2*foot origin H C R80
A* := -A+2*foot origin A H
unitcircle 0.1 lightcyan / lightblue
A--B--C--D--cycle lightblue
M := midpoint B--As
N := midpoint D--As
U := IP Cs--N circumcircle D H As
V := IP Cs--M circumcircle B H As
S* := D+As-U
T* := B+As-V
T = extension Ts H A D R80
S = extension Ss H A B
O_D = circumcenter C H T R45
circumcircle C H T 0.1 yellow / red
P = extension A H O_D midpoint T--H R45
A--H lightblue
B--D lightblue
H--C--T--cycle red
H--O_D lightblue
P--O_D heavygreen
*/
\end{asy}
\end{center}
Let the perpendicular bisector of $TH$ meet $AH$ at $P$ now.
It suffices to show that $\frac{AP}{PH}$ is symmetric in $b = AD$ and $d=AB$,
because then $P$ will be the circumcenter of $\triangle TSH$.
To do this, set $AH = \frac{bd}{2R}$ and $AC=2R$.
Let $O$ denote the circumcenter of $\triangle CHT$.
Use the Law of Cosines on $\triangle ACO$ and $\triangle AHO$,
using variables $x=AO$ and $r=HO$.
We get that
\[ r^2 = x^2 + AH^2 - 2x \cdot AH \cdot \frac{d}{2R} = x^2 + (2R)^2 - 2bx. \]
By the angle bisector theorem,
$\frac{AP}{PH} = \frac{AO}{HO}$.
The rest is computation: notice that
\[ r^2 - x^2 = h^2 - 2xh \cdot \frac{d}{2R} = (2R)^2 - 2bx \]
where $h = AH = \frac{bd}{2R}$, whence
\[ x = \frac{(2R)^2-h^2}{2b - 2h \cdot \frac{d}{2R}}. \]
Moreover,
\[ \frac{1}{2} \left( \frac{r^2}{x^2}-1 \right)
= \frac{1}{x} \left( \frac 2x R^2 - b \right). \]
Now, if we plug in the $x$ in the
right-hand side of the above, we obtain
\[ \frac{2b-2h \cdot \frac{d}{2R}}{4R^2-h^2}
\left( \frac{2b-2h \cdot \frac{d}{2R}}{4R^2-h^2} \cdot 2R^2 - b\right)
= \frac{2h}{(4R^2-h^2)^2} \left( b- h \cdot \frac{d}{2R} \right)
\left( -2hdR + bh^2 \right). \]
Pulling out a factor of $-2Rh$ from the rightmost term,
we get something that is symmetric in $b$ and $d$, as required.
\paragraph{Second solution (Victor Reis).}
Here is the fabled solution using inversion at $H$.
First, we rephrase the angle conditions in the following ways:
\begin{itemize}
\ii $\ol{AD} \perp (THC)$,
which is equivalent to the claim from the first solution.
\ii $\ol{AB} \perp (SHC)$, by symmetry.
\ii $\ol{AC} \perp (ABCD)$, by definition.
\end{itemize}
Now for concreteness we will use a negative inversion at $H$
which swaps $B$ and $D$ and overlay it on the original diagram.
As usual we denote inverses with stars.
Let us describe the inverted problem.
We let $M$ and $N$ denote the midpoints of $\ol{A^\ast B^\ast}$
and $\ol{A^\ast D^\ast}$, which are the centers of
$(HA^\ast B^\ast)$ and $(HA^\ast D^\ast)$.
From $\ol{T^\ast C^\ast} \perp (HA^\ast D^\ast)$,
we know have $C^\ast$, $M$, $T^\ast$ collinear.
Similarly, $C^\ast$, $N$, $S^\ast$ are collinear.
We have that $(A^\ast H C^\ast)$ is orthogonal to $(ABCD)$ which remains fixed.
We wish to show $\ol{T^\ast S^\ast}$ and $\ol{MN}$ are parallel.
\begin{center}
\begin{asy}
pair A = dir(100);
pair B = dir(200);
pair D = dir(-20);
pair C = -A;
pair H = foot(A, B, D);
pair Cs = -C+2*foot(origin, H, C);
pair As = -A+2*foot(origin, A, H);
filldraw(unitcircle, opacity(0.1)+lightcyan, lightblue);
draw(A--B--C--D--cycle, lightblue);
filldraw(circumcircle(B, H, As), opacity(0.1)+lightgreen, dotted+heavygreen);
filldraw(circumcircle(D, H, As), opacity(0.1)+lightgreen, dotted+heavygreen);
pair M = midpoint(B--As);
pair N = midpoint(D--As);
pair U = IP(Cs--N, circumcircle(D, H, As));
pair V = IP(Cs--M, circumcircle(B, H, As));
pair Ss = D+As-U;
pair Ts = B+As-V;
pair T = extension(Ts, H, A, D);
pair S = extension(Ss, H, A, B);
draw(Ts--Cs--Ss, heavygreen);
draw(Ts--Ss, red);
draw(B--D, lightblue);
draw(A--As, lightblue);
draw(A--B--As--D--cycle, lightblue);
draw(C--Cs--A--cycle, lightblue);
draw(S--Ss, dotted+blue);
draw(T--Ts, dotted+blue);
draw(M--N, red);
filldraw(circumcircle(As, M, N), opacity(0.1)+lightred, red+dashed);
filldraw(circumcircle(As, H, Cs), opacity(0.1)+pink, purple+dashed);
clip(box((-1.4,-1.4),(2,2)));
dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$D$", D, dir(D));
dot("$C$", C, dir(C));
dot("$H$", H, dir(H));
dot("$C^\ast$", Cs, dir(80));
dot("$A^\ast$", As, dir(As));
dot("$M$", M, dir(M));
dot("$N$", N, dir(N));
dot("$S^\ast$", Ss, dir(Ss));
dot("$T^\ast$", Ts, dir(Ts));
dot("$T$", T, dir(50));
dot("$S$", S, dir(S));
/* TSQ Source:
A = dir 100
B = dir 200
D = dir -20
C = -A
H = foot A B D
C* = -C+2*foot origin H C R80
A* = -A+2*foot origin A H
unitcircle 0.1 lightcyan / lightblue
A--B--C--D--cycle lightblue
circumcircle B H As 0.1 lightgreen / dotted heavygreen
circumcircle D H As 0.1 lightgreen / dotted heavygreen
M = midpoint B--As
N = midpoint D--As
U := IP Cs--N circumcircle D H As
V := IP Cs--M circumcircle B H As
S* = D+As-U
T* = B+As-V
T = extension Ts H A D R50
S = extension Ss H A B
Ts--Cs--Ss heavygreen
Ts--Ss red
B--D lightblue
A--As lightblue
A--B--As--D--cycle lightblue
C--Cs--A--cycle lightblue
S--Ss dotted blue
T--Ts dotted blue
M--N red
circumcircle As M N 0.1 lightred / red dashed
circumcircle As H Cs 0.1 pink / purple dashed
!clip(box((-1.4,-1.4),(2,2)));
*/
\end{asy}
\end{center}
Lot $\omega$ denote the circumcircle of $\triangle A^\ast H C^\ast$,
which is orthogonal to the original circle $(ABCD)$.
It would suffices to show $(A^\ast H C^\ast)$
is an $H$-Apollonius circle with respect to $\ol{MN}$,
from which we would get $C^\ast M / H M = C^\ast N / H N$.
However, $\omega$ through $H$ and $A$,
hence it center lies on line $MN$.
Moreover $\omega$ is orthogonal to $(A^\ast MN)$
(since $(A^\ast MN)$ and $(A^\ast BD)$ are homothetic).
This is enough (for example, if we let $O$ denote the center of $\omega$,
we now have $\mathrm{r}(\omega)^2 = OH^2 = OM \cdot ON$).
(Note in this proof that the fact that $C^\ast$ lies on $(ABCD)$
is not relevant.)
\pagebreak
\section{Solutions to Day 2}
\subsection{IMO 2014/4, proposed by Giorgi Arabidze (GEO)}
\textsl{Available online at \url{https://aops.com/community/p3543136}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $P$ and $Q$ be on segment $BC$ of an acute triangle $ABC$
such that $\angle PAB=\angle BCA$ and $\angle CAQ=\angle ABC$.
Let $M$ and $N$ be points on $\ol{AP}$ and $\ol{AQ}$,
respectively, such that $P$ is the midpoint of $\ol{AM}$
and $Q$ is the midpoint of $\ol{AN}$.
Prove that $\ol{BM}$ and $\ol{CN}$ meet on the
circumcircle of $\triangle ABC$.
\end{mdframed}
We give three solutions.
\paragraph{First solution by harmonic bundles.}
Let $\ol{BM}$ intersect the circumcircle again at $X$.
\begin{center}
\begin{asy}
pair A = dir(70);
pair B = dir(190);
pair C = dir(350);
filldraw(unitcircle, opacity(0.1)+palecyan, lightblue);
filldraw(A--B--C--cycle, opacity(0.1)+heavycyan, blue);
pair T = 2*B*C/(B+C);
pair P = extension(A, B+A-T, B, C);
pair Q = extension(A, C+A-T, B, C);
pair M = 2*P-A;
pair N = 2*Q-A;
pair X = extension(B, M, C, N);
draw(B--M, lightblue);
draw(C--N, lightblue);
draw(A--M, lightred);
draw(A--N, orange);
real r = 0.4;
draw((B+r*dir(B-T))--(B+r*dir(T-B)), lightred);
draw((C+r*dir(C-T))--(C+r*dir(T-C)), orange);
dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$C$", C, dir(C));
dot("$P$", P, dir(225));
dot("$Q$", Q, dir(225));
dot("$M$", M, dir(M));
dot("$N$", N, dir(N));
dot("$X$", X, dir(280));
/* TSQ Source:
A = dir 70
B = dir 190
C = dir 350
unitcircle 0.1 palecyan / lightblue
A--B--C--cycle 0.1 heavycyan / blue
T := 2*B*C/(B+C)
P = extension A B+A-T B C R225
Q = extension A C+A-T B C R225
M = 2*P-A
N = 2*Q-A
X = extension B M C N R280
B--M lightblue
C--N lightblue
A--M lightred
A--N orange
! real r = 0.4;
(B+r*dir(B-T))--(B+r*dir(T-B)) lightred
(C+r*dir(C-T))--(C+r*dir(T-C)) orange
*/
\end{asy}
\end{center}
The angle conditions imply that the tangent to $(ABC)$ at $B$
is parallel to $\ol{AP}$.
Let $\infty$ be the point at infinity along line $AP$.
Then \[ -1 = (AM;P\infty) \overset{B}{=} (AX;BC). \]
Similarly, if $\ol{CN}$ meets the circumcircle at $Y$
then $(AY;BC) = -1$ as well.
Hence $X=Y$, which implies the problem.
\paragraph{Second solution by similar triangles.}
Once one observes $\triangle CAQ \sim \triangle CBA$,
one can construct $D$ the reflection of $B$ across $A$,
so that $\triangle CAN \sim \triangle CBD$.
Similarly, letting $E$ be the reflection of $C$ across $A$,
we get $\triangle BAP \sim \triangle BCA
\implies \triangle BAM \sim \triangle BCE$.
Now to show $\angle ABM + \angle ACN = 180\dg$
it suffices to show $\angle EBC + \angle BCD = 180\dg$,
which follows since $BCDE$ is a parallelogram.
\paragraph{Third solution by barycentric coordinates.}
Since $PB = c^2/a$ we have
\[ P = (0 : a^2-c^2 : c^2) \]
so the reflection $\vec M = 2\vec P - \vec A$ has coordinates
\[ M = (-a^2 : 2(a^2-c^2) : 2c^2). \]
Similarly $N = (-a^2 : 2b^2 : 2(b^2-a^2))$. Thus
\[ \ol{BM} \cap \ol{CN} = (-a^2 : 2b^2 : 2c^2) \]
which clearly lies on the circumcircle,
and is in fact the point identified in the first solution.
\pagebreak
\subsection{IMO 2014/5, proposed by Luxembourg}
\textsl{Available online at \url{https://aops.com/community/p3543144}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
For every positive integer $n$,
the Bank of Cape Town issues coins of denomination $\frac 1n$.
Given a finite collection of such coins (of not necessarily different denominations)
with total value at most $99 + \frac12$, prove that it is possible to split
this collection into $100$ or fewer groups, such that each group has total value at most $1$.
\end{mdframed}
We'll prove the result
for at most $k - \frac{k}{2k+1}$ with $k$ groups.
First, perform the following optimizations.
\begin{itemize}
\ii If any coin of size $\frac{1}{2m}$ appears twice,
then replace it with a single coin of size $\frac{1}{m}$.
\ii If any coin of size $\frac{1}{2m+1}$ appears $2m+1$ times,
group it into a single group and induct downwards.
\end{itemize}
Apply this operation repeatedly until it cannot be done anymore.
Now construct boxes $B_0$, $B_1$, \dots, $B_{k-1}$.
In box $B_0$ put any coins of size $\tfrac 12$
(clearly there is at most one).
In the other boxes $B_m$, put coins of size
$\frac{1}{2m+1}$ and $\frac{1}{2m+2}$
(at most $2m$ of the former and at most one of the latter).
Note that the total weight in the box is less than $1$.
Finally, place the remaining ``light'' coins of size
at most $\frac{1}{2k+1}$ in a pile.
Then just toss coins from the pile into the boxes arbitrarily,
other than the proviso that no box should have its weight exceed $1$.
We claim this uses up all coins in the pile.
Assume not, and that some coin remains in the pile
when all the boxes are saturated.
Then all the boxes must have at least $1 -\frac{1}{2k+1}$,
meaning the total amount in the boxes is strictly greater than
\[ k \left( 1 - \frac{1}{2k+1} \right) > k - \tfrac 12 \]
which is a contradiction.
\begin{remark*}
This gets a stronger bound $k - \frac{k}{2k+1}$
than the requested $k-\tfrac 12$.
\end{remark*}
\pagebreak
\subsection{IMO 2014/6, proposed by Austria}
\textsl{Available online at \url{https://aops.com/community/p3543151}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
A set of lines in the plane is in \emph{general position}
if no two are parallel and no three pass through the same point.
A set of lines in general position cuts the plane into regions,
some of which have finite area; we call these its \emph{finite regions}.
Prove that for all sufficiently large $n$,
in any set of $n$ lines in general position
it is possible to colour at least $\sqrt{n}$ lines blue
in such a way that none of its finite regions
has a completely blue boundary.
\end{mdframed}
Suppose we have colored $k$ of the lines blue, and that
it is not possible to color any additional lines.
That means any of the $n-k$ non-blue lines
is the side of some finite region with
an otherwise entirely blue perimeter.
For each such line $\ell$, select one such region,
and take the next counterclockwise vertex;
this is the intersection of two blue lines $v$.
We'll say $\ell$ is the \emph{eyelid} of $v$.
\begin{center}
\begin{asy}
size(2cm);
pair A = dir( 0); dot(A);
pair B = dir( 72); dot(B);
pair C = dir(144); dot(C);
pair D = dir(216); dot(D);
pair E = dir(288); dot(E);
draw(D--E--A--B--C, blue);
draw(C--D, red);
label("$\ell$", 0.5*C+0.5*D, dir(180));
label("$v$", E, dir(E));
\end{asy}
\end{center}
You can prove without too much difficulty that every intersection of two blue lines
has at most two eyelids.
Since there are $\binom k2$ such intersections, we see that
\[ n-k \le 2 \binom k2 = k^2 - k\]
so $n \le k^2$, as required.
\begin{remark*}
In fact, $k = \sqrt n$ is ``sharp for greedy algorithms'',
as illustrated below for $k=3$:
\begin{center}
\begin{asy}
size(2.5cm);
real R = 7;
real r = 3;
real e = 2;
pair A = R * dir(90);
pair B = R * dir(210);
pair C = R * dir(330);
draw( (A-r*dir(B-A)) -- (B-r*dir(A-B)), blue );
draw( (B-r*dir(C-B)) -- (C-r*dir(B-C)), blue );
draw( (C-r*dir(A-C)) -- (A-r*dir(C-A)), blue );
void yanpi(pair P) {
dot(P, blue);
draw( (P+e*dir(P)*dir(70)) -- (P+e*dir(P)*dir(-70)), red);
draw( (P+e*dir(P)*dir(110)) -- (P+e*dir(P)*dir(-110)), red);
}
yanpi(A);
yanpi(B);
yanpi(C);
\end{asy}
\end{center}
\end{remark*}
\pagebreak
\end{document}