Problem 01

Real numbers $a_1, a_2, \dots , a_n$ are given. For each $i$ ( $1\le i\le n$ ) define

$d_i=\max\{a_j:1\le j\le i\}-\min\{a_j:i\le j\le n\}$

and let

$d=\max\{d_i:1\le i\le n\}$ .

(a) Prove that, for any real numbers $x_1\le x_2\le \cdots\le x_n$ ,

$\max\{|x_i-a_i|:1\le i\le n\}\ge \dfrac{d}{2} (*)$

(b) Show that there are real numbers $x_1\le x_2\le x_n$ such that equality holds in (*)

Solution

Since $d_i=\max\{a_j:1\le j\le i\}-\min\{a_j:i\le j\le n\}$ , all $d_i$ can be expressed as $a_p-a_q$ , where $1\le p\le i\le q \le n$ .

Thus, $d$ can be expressed as $a_p-a_q$ for some $p$ and $q$ , $1\le p\le q\le n$

Lemma) $d\ge 0$

Assume for contradiction that $d<0$ , then for all $i$ , $a_i \le \max\{a_j:1\le j\le i\}\le \min\{a_j:i\le j\le n\}\le a_{i+1}$

$a_i\le a_{i+1}$

Then, ${a_i}$ is a non-decreasing function, which means, $\max\{a_j:1\le j\le i\}=a_i$ , and $\min\{a_j:i\le j\le n\}\le a_{i+1}=a_i$ , which means, ${d_i}={0}$ .

Then, $d=0$ and contradiction.

Case 1) $d=0$

If $d=0$ , $\max\{|x_i-a_i|:1\le i\le n\}$ is the maximum of a set of non-negative number, which must be at least $0$ .

Case 2) $d>0$ (We can ignore $d<0$ because of lemma)

Using the fact that $d$ can be expressed as $a_p-a_q$ for some $p$ and $q$ , $1\le p\le q\le n$ . $x_p\le x_q$

Assume for contradiction that $\max\{|x_i-a_i|:1\le i\le n\}<\dfrac{d}{2}$ .

Then, $\forall x_i$ , $|x_i-a_i|<\dfrac{d}{2}$ .

$|x_p-a_p|<\dfrac{d}{2}$ , and $|x_q-a_q|<\dfrac{d}{2}$

Thus, $x_p>a_p-\dfrac{d}{2}$ and $x_q<a_q+\dfrac{d}{2}$ .

Subtracting the two inequality, we will obtain:

$x_p-x_q>a_p-a_q-d=a_p-a_q-a_p+a_q=0$

$x_p>x_q$ --- contradiction ( $p\le q \rightarrow x_p\le x_q$ ).

Thus, $\max\{|x_i-a_i|:1\le i\le n\}\ge\dfrac{d}{2}$

(b)

A set of ${x_i}$ where the equality in (*) holds is:

$x_i=\max\{a_j:1\le j\le i\}-\frac{d}{2}$

Since $\max\{a_j:1\le j\le i\}$ is a non-decreasing function, $x_i$ is non-decreasing.

$\forall x_i$ :

Let $a_m=\max\{a_j:1\le j\le i\}$ , $a_m-a_i<a_m-\min\{a_j:i\le j\le n\}=d_i$ .

Thus, $0\le a_m-a_i \le d$ ( $0\le a_m-a_i$ because $a_m$ is the max of a set including $a_i$ )

$|x_i-a_i|=\left|a_m-\dfrac{d}{2}-a_i\right|=\left|(a_m-a_i)\dfrac{d}{2}\right|$

$0\le a_m-a_i\le d$

$-\dfrac{d}{2} \le (a_m-a_i)\dfrac{d}{2} \le \dfrac{d}{2}$

$\left|(a_m-a_i)-\dfrac{d}{2}\right|=|x_i-a_i|\le \frac{d}{2}$

Since $\max\{|x_i-a_i|:1\le i\le n\}\ge\dfrac{d}{2}$ and $|x_i-a_i|\le \frac{d}{2}$ $\forall x_i$ , $\max\{|x_i-a_i|:1\le i\le n\}=\dfrac{d}{2}$

Problem 02

Consider five points $A,B,C,D$ , and $E$ such that $ABCD$ is a parallelogram and $BCED$ is a cyclic quadrilateral. Let $\ell$ be a line passing through $A$ . Suppose that $\ell$ intersects the interior of the segment $DC$ at $F$ and intersects line $BC$ at $G$ . Suppose also that $EF=EG=EC$ . Prove that $\ell$ is the bisector of $\angle DAB$ .

Solution

$[asy] import cse5; import graph; import olympiad; dotfactor = 3; unitsize(1.5inch); path circle = Circle(origin, 1); draw(circle); pair D = (-sqrt(3)/2, -0.5), C = (sqrt(3)/2, -0.5); //G = bisectorpoint(C, B, D); pair Ee = rotate(38,C)*D; pair E = IP(C--Ee, circle,1); pair Gg = rotate(76,C)*D; path circle2 = Circle(E, length(C-E)); pair G = IP(C--Gg, circle2, 1); pair F = IP(C--D, circle2, 1); pair Bb = rotate(-104,C)*D; pair B = IP(C--Bb, circle, 1); pair A = extension((-1,B.y),(1,B.y),G,F); draw(circle2, dashed); draw(A--G); draw(C--D--A--B); draw(G--B); draw(E--F); draw(E--C); draw(E--G); dot("$C$", C, dir(30)); dot("$D$", D, SW); dot("$G$", G, SE); dot("$E$", E, SW); dot("$F$", F, SW); dot("$A$", A, SW); dot("$B$", B, SE); draw(D--E,dashed); draw(B--E,dashed); [/asy]$

Since $\angle{DAF}=\angle{CGF}$ , $\angle{BAF}=\angle{CFG}$ , it suffices to prove $CF=CG$ .

Let $\angle{FCE}=\alpha$ , $\angle{GCE}=\beta$ , $\angle{CDE}=\gamma$ . We have: $CF=2CE\cos{\alpha}, CG=2CE\cos{\beta}$ so, $\dfrac{CF}{CG}=\dfrac{\cos{\alpha}}{\cos{\beta}}$ Meantime, using Law of Sines on $\triangle{DEC}$ , we have, $\dfrac{CE}{\sin{\gamma}}=\dfrac{DC}{\sin{(180-\alpha-\gamma)}}=\dfrac{DC}{\sin{(\alpha+\gamma)}}$ Using Law of Sines on $\triangle{BEG}$ , and notice that $\angle{CBE}=\angle{CDE}=\gamma$ , we have, $\dfrac{CE}{\sin{\gamma}}=\dfrac{BG}{\sin{(180-\beta-\gamma)}}=\dfrac{BG}{\sin{(\beta+\gamma)}}$ so, $\dfrac{DC}{BG}=\dfrac{\sin{(\alpha+\gamma)}}{\sin{(\beta+\gamma)}}$ Since $\triangle{GFC} \sim \triangle{GAB}$ , and $DC=AB$ , we have, $\dfrac{DC}{BG}=\dfrac{AB}{BG}=\dfrac{CF}{CG}$ . Hence, $\dfrac{\sin{(\alpha+\gamma)}}{\sin{(\beta+\gamma)}}=\dfrac{\cos{\alpha}}{\cos{\beta}}$ or, $\sin{(\alpha+\gamma)}\cos{\beta}=\sin{(\beta+\gamma)}\cos{\alpha}$ $\dfrac{1}{2}(\sin{(\alpha+\gamma+\beta)}-\sin{(\alpha+\gamma-\beta)})=\dfrac{1}{2}(\sin{(\alpha+\gamma+\beta)}-\sin{(\beta+\gamma-\alpha)})$ $\sin{(\alpha+\gamma-\beta)}=\sin{(\beta+\gamma-\alpha)}$ There are two possibilities: (1) $\alpha+\gamma-\beta = \beta+\gamma-\alpha$ , or (2) $\alpha+\gamma-\beta = 180 - (\beta+\gamma-\alpha)$ . However, (2) would mean $\gamma=90$ , then $EC$ would be a diameter, and $EF < EC$ because $F$ is inside the circle, so (2) is not valid. From condition (1), we have $\alpha=\beta$ , therefore $CF=CG$ .

Problem 03

In a mathematical competition some competitors are friends. Friendship is always mutual. Call a group of competitors a clique if each two of them are friends. (In particular, any group of fewer than two competitors is a clique.) The number of members of a clique is called its size. Given that, in this competition, the largest size of a clique is even, prove that the competitors can be arranged in two rooms such that the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room.

Problem 04

In $\triangle ABC$ the bisector of $\angle{BCA}$ intersects the circumcircle again at $R$ , the perpendicular bisector of $BC$ at $P$ , and the perpendicular bisector of $AC$ at $Q$ . The midpoint of $BC$ is $K$ and the midpoint of $AC$ is $L$ . Prove that the triangles $RPK$ and $RQL$ have the same area.

Solution

The area of $\triangle{RQL}$ is given by $\dfrac{1}{2}QL*RQ\sin{\angle{RQL}}$ and the area of $\triangle{RPK}$ is $\dfrac{1}{2}RP*PK\sin{\angle{RPK}}$ . Let $\angle{BCA}=C$ , $\angle{BAC}=A$ , and $\angle{ABC}=B$ . Now $\angle{KCP}=\angle{QCL}=\dfrac{C}{2}$ and $\angle{PKC}=\angle{QLC}=90$ , thus $\angle{RPK}=\angle{RQL}=90+\dfrac{C}{2}$ . $\triangle{PKC} \sim \triangle{QLC}$ , so $\dfrac{PK}{QL}=\dfrac{KC}{LC}$ , or $\dfrac{PK}{QL}=\dfrac{BC}{AB}$ . The ratio of the areas is $\dfrac{[RPK]}{[RQL]}=\dfrac{BC*RP}{AC*RQ}$ . The two areas are only equal when the ratio is 1, therefore it suffices to show $\dfrac{RP}{RQ}=\dfrac{AC}{BC}$ . Let $O$ be the center of the circle. Then $\angle{ROK}=A+C$ , and $\angle{ROP}=180-(A+C)=B$ . Using law of sines on $\triangle{RPO}$ we have: $\dfrac{RP}{\sin{B}}=\dfrac{OR}{\sin{(90+\dfrac{C}{2})}}$ so $RP*\sin{(90+\dfrac{C}{2})}=OR*\sin{B}$ . $OR*\sin{B}=\dfrac{1}{2}AC$ by law of sines, and $\sin{(90+\dfrac{C}{2})}=\cos{\dfrac{C}{2}}$ , thus 1) $2RP\cos{\dfrac{C}{2}}=AC$ . Similarly, law of sines on $\triangle{ROQ}$ results in $\dfrac{RQ}{\sin{(180-A)}}=\dfrac{OR}{\sin{(90-\dfrac{C}{2})}}$ or $\dfrac{RQ}{\sin{A}}=\dfrac{OR}{\cos{\dfrac{C}{2}}}$ . Cross multiplying we have $RQ\cos{\dfrac{C}{2}}=OR*\sin{A}$ or 2) $2RQ\cos{\dfrac{C}{2}}=BC$ . Dividing 1) by 2) we have $\dfrac{RP}{RQ}=\dfrac{AC}{BC}$

Problem 05

Let $n$ and $k$ be positive integers with $k \geq n$ and $k - n$ an even number. Let $2n$ lamps labelled $1$ , $2$ , ..., $2n$ be given, each of which can be either on or off. Initially all the lamps are off. We consider sequences of steps: at each step one of the lamps is switched (from on to off or from off to on).

Let $N$ be the number of such sequences consisting of $k$ steps and resulting in the state where lamps $1$ through $n$ are all on, and lamps $n + 1$ through $2n$ are all off.

Let $M$ be number of such sequences consisting of $k$ steps, resulting in the state where lamps $1$ through $n$ are all on, and lamps $n + 1$ through $2n$ are all off, but where none of the lamps $n + 1$ through $2n$ is ever switched on.

Determine $\frac {N}{M}$ .

Solution

For convenience, let $A$ denote the set $(1,2,\ldots n)$ and $B$ the set $(n+1,n+2,\ldots,2n)$ .

We can describe each sequences of switching the lamps as a $k$ -dimensional vector $(a_1, a_2, \ldots, a_k)$ , where $a_i \in A \cup B$ signifies which lamp was switched on the $i$ -th move for $i=1,2,\ldots k$ .

Let $\cal{N}$ consist of those sequences that contain each of the numbers in $A$ an odd number of times and each of the numbers in $B$ an even number of times. Similarly, let $\cal{M}$ denote the set of those sequences that contain no numbers from $B$ and each of the numbers in $A$ an odd number of times. By definition, $M=|\cal{M}|$ and $N=|\cal{N}|$ .

Define the mapping $f:\cal{N} \rightarrow \cal{M}$ as $f(a_1, a_2, \ldots, a_k) = (b_1,b_2,\ldots b_k) : b_i = \begin{cases} a_i, & \mbox{ if } a_i \in A \\ a_i-n, & \mbox{ if } a_i \in B \end{cases}$

What we want to show now is that each element of $\cal{M}$ is an image of exactly $2^{k-n}$ elements from $\cal{N}$ , which would imply $N = 2^{k-n}M$ and solve the problem.

Consider an arbitrary element $y$ of $\cal{M}$ and let $l_i$ be the number of appearances of the number $i$ in $y$ for $i=1,2,\ldots n$ . Now consider the set of pre-images of $y$ , that is $X_y = \{ x | f(x) = y \}$ .

It is easy to see that each element $x\in X_y$ is derived from $y$ by flipping an even number of its $1$ -s, $2$ -s, and so on, where flipping means changing the number $j\in A$ to $j+n\in B$ . Since each such set of flippings results in a unique $x$ , all we want to count is the number of flippings. We can flip exactly $0, 2, 4,\ldots$ of the $1$ -s, so that results in $\binom{l_1}{0} + \binom{l_1}{2}+\binom{l_1}{4}+\cdots = 2^{l_1-1}$ flippings. Combine each of them with the $2^{l_2-1}$ , $2^{l_3-1}$ , etc. ways of flipping the $2$ -s, $3$ -s etc. respectively to get the total number of flippings: $2^{l_1-1}2^{l_2-1}\cdots2^{l_n-1} = 2^{l_1+l_2+\cdots+l_n-n} = 2^{k-n}.$ This shows that $|X_y| = 2^{k-n}$ and the proof is complete.

Problem 06

Let $n$ be a positive integer. Consider $S=\{(x,y,z)~:~x,y,z\in \{0,1,\ldots,n \},~x+y+z>0\}$ as a set of $(n+1)^3-1$ points in three-dimensional space. Determine the smallest possible number of planes, the union of which contain $S$ but does not include $(0,0,0)$ .

Solution

We will prove the result using the following Lemma, which has an easy proof by induction.

Lemma Let $S_1 = \{0, 1, \ldots, n_1\}$ , $S_2 = \{0, 1, \ldots, n_2\}$ and $S_3 = \{0, 1, \ldots, n_3\}$ . If $P$ is a polynomial in $\mathbb{R}[x, y, z]$ that vanishes on all points of the grid $S = S_1 \times S_2 \times S_3$ except at the origin, then $\deg P \geq n_1 + n_2 + n_3.$

Proof. We will prove this by induction on $n = n_1 + n_2 + n_3$ . If $n = 0$ , then the result follows trivially. Say $n > 0$ . WLOG, we can assume that $n_1 > 0$ . By polynomial division over $\mathbb{R}[y, z][x]$ we can write $P = (x - n_1)Q + R.$ Since $x-n_1$ is a monomial, the remainder $R$ must be a constant in $\mathbb{R}[y, z]$ , i.e., $R$ is a polynomial in two variables $y$ , $z$ . Pick an element of $S$ of the form $(n_1, y, z)$ and substitute it in the equation. Since $P$ vanishes on all such points, we get that $R(y, z) = 0$ for all $(y, z) \in S_2 \times S_3$ . Let $S_1' = \{0, 1, \ldots, n_1 - 1\}$ and $S' = S_1' \times S_2 \times S_3$ . For every point $(x, y, z)$ in $S'$ we have $P(x, y, z) = (x - n_1)Q(x, y, z) + R(y, z) = (x-n_1)Q(x, y, z),$ where $x - n_1 \neq 0$ . Therefore, the polynomial $Q$ vanishes on all points of $S'$ except the origin. By induction hypothesis, we must have $\deg Q \geq n_1 - 1 + n_2 + n_3$ . But, $\deg P \geq \deg Q + 1$ and hence we have $\deg P \geq n_1 + n_2 + n_3$ .

Now, to solve the problem let $H_1, \ldots, H_m$ be $m$ planes that cover all points of $S$ except the origin. Since these planes don't pass through origin, each $H_i$ can be written as $a_i x + b_i y + c_i z = 1$ . Define $P$ to be the polynomial $\prod (a_ix + b_iy + c_iz - 1)$ . Then $P$ vanishes at all points of $S$ except at the origin, and hence $\deg P = m \geq 3n$ .