### Mathematics and Youth Magazine Problems - Jan 2014, Issue 439

1. Find all possible ways of inserting three distinct digits into the positions represented by a star in $\overline{155*710*4*16}$ so that the resulting number is divisible by 396.
2. The triangles $XBC$, $YCA$ and $ZAB$ are constructed externally on the sides of a triangle $ABC$ such that triangle $XBC$ is isosceles with angle $BXC$ equals $120^{0}$ and $YCA$, $ZAB$ are both equilateral. Prove that $XA$ is perpendicular to $YZ$.
3. Find all positive integer solutions $x,y$ of the equation $(x^{2}-9y^{2})^{2}=33y+16.$
4. Solve the following system of equations $\begin{cases}6(1-x)^{2} & =\frac{1}{y}\\ 6(1-y)^{2} & =\frac{1}{x} \end{cases}.$
5. Point $C$ lies on a half-circle $(O)$ with diameter $AB=2R$, $CH$ is the altitude from $C$ to $AB$ ($H$ differs from $O$). The points $E,F$ move on the half-circle such that $\widehat{CHE}=\widehat{CHF}$. Prove that the line $EF$ always passes through a fixed point.
6. Solve for $x$ $\sqrt{2+\sqrt{2+\sqrt{2+\sqrt{2+x}}}}=\sqrt[3]{6+\sqrt[3]{6+\sqrt[3]{6+\sqrt[3]{6+}x}}}.$
7. Solve the following system of equations $\begin{cases} 4x^{2} & =(\sqrt{x^{2}+1}+1)(x^{2}-y^{3}+3y-2)\\ (x^{2}+y^{2})^{2}+1 & =x^{2}+2y \end{cases}.$
8. Let $BC=a$, $CA=b$, $AB=c$ be the side lengths of a triangle $ABC$; $R$ and $r$ denote its circumradius and inradius respectively. If $S$ is the area of triangle $ABC$, prove that $\frac{R}{r}\geq\max\left\{ \frac{1}{2};\sqrt{\frac{ab^{3}+bc^{3}+ca^{3}}{3S^{2}}};\sqrt{\frac{ab^{3}+bc^{3}+ca^{3}}{3S^{2}}}\right\} .$
9. Find all odd positive integers $n$ such that $15^{n}+1$ is divisible by $n$.
10. Determine all possible pairs of functions $f:\mathbb{R}\to\mathbb{R}$; $g:\mathbb{R}\to\mathbb{R}$ such that for any $x,y\in\mathbb{R}$, the following identity holds $f(x+g(y))=xf(y)-yg(y)+g(x).$
11. $n$ students ($n\geq2$) are standing in a straigh line. Each time the teacher blow a whistle, exactly two students exchange their positions.  Can it be possible that after an odd number of such whistles, all students returned to their original positions?.
12. Let $AH$ ($H\in BC$) be the altitude of an acute triangle $ABC$. Point $P$ moves on the segment $AH$. Let $E,F$ denote the feet of the perpendicular from $P$ to $AB,AC$ respectively.
a) Prove that the points $B,R,F,C$ are concyclic.
b) Let $O'$ denote the center of the circle containing $B,E,F,C$. Prove that $PO'$ always passes through a fix point, independent of the position of point $P$ chosen on $AH$.

### Mathematics and Youth Magazine Problems - Dec 2015, Issue 462

1. Find the last digit of the following number $A=1^{2015}+2^{2015}+3^{2015}+\ldots+2014^{2015}+2015^{2015}.$
2. Given a right trapezoid $ABCD$ ($A$ and $B$ are right angles) with $AD<BC$ and $AC\perp BD$. Prove that $AC^{2}+BD^{2}=3AB^{2}+CD^{2}.$
3. Does there exist a pair of positive integers $(a,b)$ such that both the equation $x^{2}+2ax-b-2=0$ and the equation $x^{2}+bx-a=0$ have integer solutions?.
4. Given a right triangle $ABC$ with the right angle $A$ such that $BC^{2}=2BC\cdot AC+4AC^{2}.$ Find the angle $\widehat{ABC}$.
5. Solve the equation $\sqrt[5]{3x-2}-\sqrt[5]{2x+1}=\sqrt[5]{x-3}.$
6. Solve the system of equations $\begin{cases} x+\sqrt{x^{2}+9} & =\sqrt[4]{3^{y+4}}\\ y+\sqrt{y^{2}+9} & =\sqrt[4]{3^{z+4}}\\ z+\sqrt{z^{2}+9} & =\sqrt[4]{3^{x+4}} \end{cases}.$
7. Given an acute triangle $ABC$ with angles measured in radian. Prove that $\sin A+\sin B+\sin C>\frac{5}{2}-\frac{A^{2}+B^{2}+C^{2}}{\pi^{2}}.$
8. Given a tetrahedron $ABCD$ inscribed in a sphere of radius $1$. Assume that the product of the lengths of its sides is equal to $\frac{512}{27}$. Compute the lengths of its sides.
9. Let $a,b,c$ be the lengths of three sides of a triangle. Prove that $\frac{3(a^{2}+b^{2}+c^{2})}{(a+b+c)^{2}}+\frac{ab+bc+ca}{a^{2}+b^{2}+c^{2}}\leq2.$
10. Find the number of the triples $(a,b,c)$ of integers in the interval $[1,2015]$ such that $a^{3}+b^{3}+c^{3}$ is divisible by $9$?.
11. Let $a,b,c$ be real numbers such that $a^{2}+b^{2}+c^{2}=1$. Find the minimum value of the expression $P=|6a^{3}+bc|+|6b^{3}+ca|+|6c^{3}+ab|.$
12. Given a triangle $ABC$ with $(O)$ and $H$ respectively are the circumcircle and the orthocenter of the triangle. Let $P$ be an arbitrary point on $OH$. Let $A_{0},B_{0},C_{0}$ respectively be the intersections between $AH,BC,CH$ and $BC,CA,AB$. Suppose that $A_{1},B_{1},C_{1}$ respectively be the second intersections between $AP,BP,CP$ and $(O)$. Let $A_{2},B_{2},C_{2}$ respectively be the reflection points of $A_{1},B_{1},C_{1}$ through $A_{0},B_{0},C_{0}$. Prove that $H,A_{2},B_{2},C_{2}$ belong to a circle with center is on $OH$.

### Mathematics and Youth Magazine Problems - Nov 2015, Issue 461

1. Let $(2n-1)!!$ and $(2n)!!$ donote the products $1.3.5\ldots(2n-1)$ and $2.4.6\ldots(2n)$ respectively. Prove that the number $A=(2013)!!+(2014)!!$ is divisible by $2015.$
2. Given an isolates triangle $ABC$ with $AB=AC$ and $\widehat{A}=3\widehat{B}$. On the half-plane determined by $BC$ that contians $A$, draw the array $Cy$ such that $\widehat{BCy}=132^{0}$. The array $Cy$ intersects the bisector $Bx$ of the angle $B$ at $D$. Calculate $\widehat{ADB}$.
3. Solve the equation $\frac{1}{\sqrt{x^{2}+3}}+\frac{1}{\sqrt{1+3x^{2}}}=\frac{2}{x+1}.$
4. Given an equilateral triangle $ABC$ and a point $)$ inside the triangle. Let $M,N,P$ respectively be the intersections between $AO,BO,CO$ and the sides of the triangle. Prove that
a) ${\displaystyle \frac{1}{AM}+\frac{1}{BN}+\frac{1}{CP}\leq\frac{1}{3}\left(\frac{1}{OM}+\frac{1}{ON}+\frac{1}{OP}\right)}$,
b) ${\displaystyle \frac{1}{AM}+\frac{1}{BN}+\frac{1}{CP}\leq\frac{2}{3}\left(\frac{1}{OA}+\frac{1}{OB}+\frac{1}{OC}\right)}$.
5. Solve the system of equations $\begin{cases} \sqrt[3]{9(x\sqrt{x}+y^{3}+z^{3})} & =x+y+z\\ x^{2}+\sqrt{y} & =2z\\ \sqrt{y}+z^{2} & =\sqrt{1-x}+2 \end{cases}.$
6. Solve the equation $(x+1)(x+2)(x+3)=\frac{720}{(x+4)(x+5)(x+6)}.$
7. Determine the number of solutions of each following equation
a) ${\displaystyle \sin x=\frac{x}{1964}}$,
b) $\sin x=\log_{100}x$,
8. Given a triangle $ABC$ inscribed in a circle $(O)$. The bisectors of the angles $A,B,C$ respectively intersects the circle at $D,E,F$. Denote respectively by $h_{a},h_{b},h_{c},S$ the heights from $A,B,C$ and the area of $ABC$. Prove that $AD.h_{1}+BE.h_{b}+CF.h_{c}\geq4\sqrt{3}S.$
9. Given real numbers $a,b,c,d$ satisfying $a^{2}+b^{2}+c^{2}+d^{2}=1.$ Find the maximum and minimum values of the expression $P=ab+ac+ad+bc+cd+3cd.$
10. Given $k\geq1$ and positive numbers $x,y$. For any positive integer $n\geq2$, show the following inequalities $\sqrt{xy}\leq\sqrt[n]{\frac{x^{n}+y^{n}+k[(x+y)^{n}-x^{n}-y^{n}]}{2+k(2^{n}-2)}}\leq\frac{x+y}{2}.$
11. A pair of positive integers is called a good pair if their quotient if either $2$ or $3$. What is the most number of good pairs we can get among $2015^{2016}$ arbitrary different positive integers?.
12. Given a triangle $ABC$. Let $E,F$ respectively be the perpendicular projections of $B,C$ on $AC,AB$; and then let $T$ be the perpendicular projection of $A$ on $EF$. Denote the midpoints of $BE$ and $CF$ by $M$ and $N$ respectively. Suppose that $TM,TN$ intersects $AB,AC$ respectively at $P,Q$. Prove that $EF$ goes through the midpoint of $PQ$,

### Mathematics and Youth Magazine Problems - Oct 2015, Issue 460

1. Let $a$ be a natural number with all different digits and $b$ is another number obtained by using the all the digits of $a$ but in a different order. Given $a-b=\underset{n}{\underbrace{111\ldots1}}$ ($n$ digit $1$ where $n$ is a positive integer). Find the maximum value of $n$.
2. Find positive integers $x,y,z$ such that $(x-y)^{3}+(y-z)^{3}+4|z-x|=27.$
3. Let $a,b,c$ be the lengths of three sides of a triangle. Prove that $2\left(\frac{a}{b}+\frac{b}{c}+\frac{c}{a}\right)\geq\frac{a}{c}+\frac{b}{a}+\frac{c}{b}+3.$
4. Let $ABC$ be an isosceles triangle ($AB=AC$) inscribed in a given circle $(O,R)$. Draw $BH$ perpendicular to $AC$ at $H$. Find the maximum length of $BH$.
5. Solve the system of equations $\begin{cases} \frac{7}{2}+\frac{3y}{x+y} & =\sqrt{x}+4\sqrt{y}\\ (x^{2}+y^{2})(x+1) & =4+2xy(x-1) \end{cases}.$
6. For any $m>1$, prove that the following equation has a unique solution $x^{3}-3\sqrt[3]{3x+2m}=2m.$
7. Find all values of the parameters $p$ and $q$ such that the corresponding system of equations $\begin{cases} x^{2}+y^{2}+5 & =q^{2}+2x-4y\\ x^{2}+(12-2p)x+y^{2} & =2py+12p-2p^{2}-27 \end{cases}$ has two solutions $(x_{1},y_{1})$ and $(x_{2},y_{2})$ satisfying $x_{1}^{2}+y_{1}^{2}=x_{2}^{2}+y_{2}^{2}.$
8. Given a triangle $ABC$ with $BC=a$, $CA=b$ and $AB=c$. Let $R,r$ and $p$ respectively be the circumradius, the inradius, and the semiperimeter of $ABC$. Prove that $\frac{ab+bc+ca}{p^{2}+9Rr}\geq\frac{4}{5}.$ When does the equality occur?.
9. Given three positive real numbers $a,b,c$ such that $abc\geq1$. Prove that $\frac{a^{4}b^{2}c^{2}}{bc+1}+\frac{b^{4}c^{2}a^{2}}{ca+1}+\frac{c^{4}a^{2}b^{2}}{ab+1}\geq\frac{3}{2}.$
10. Find all positive integers $k$ such that there exist 2015 different positive integers whose sum is divisible by the sum of any $k$ numbers among them.
11. Find the maximum $k$ such that the inequality $\frac{1}{a}+\frac{1}{b}+\frac{1}{c}+1+2k\geq(k+2)\sqrt{a+b+c+1}$ holds for any positive real numbers $a,b,c$ satisfying $abc=1$.
12. Given a triangle $ABC$ and $D$ varies on the side $BC$. Let $(I_{1})$, $(I_{2})$ respectively be the incircles of the triangles $ABD$, $ACD$. Suppose that $(I_{1})$ is tangent to $AB$, $BD$ at $E,X$ and $(I_{2})$ is tangent to $AC$, $CD$ at $F,Y$. Assume that $AI_{1}$, $AI_{2}$ respectively intersects $EX$, $FY$ at $Z,T$. Show that
a) $X,Y,Z,T$ both belong to a circle with center $K$.
b) $K$ belongs to a fixed line.

### Mathematics and Youth Magazine Problems - Sep 2015, Issue 459

1. Let \begin{align*} A & =\frac{1}{1.2^{2}}+\frac{2}{2.3^{2}}+\frac{1}{3.4^{2}}+\ldots+\frac{1}{49.50^{2}},\\ B & =\frac{1}{2^{2}}+\frac{1}{3^{2}}+\frac{1}{4^{2}}+\ldots+\frac{1}{50^{2}}.\end{align*} Compare $A$ and $B$ with $\frac{1}{2}$.
2. For all pairs of real numbers $(a,b)$ such that the polynomial $A(x)=x^{2}-2ax+2a^{2}+b^{2}-5$ has solutions. Find the minimum value of the expression $P=(a+1)(b+1).$
3. Suppose that $a_{1},a_{2},\ldots,a_{n}$ are different positive integers such that $\frac{1}{a_{1}}+\frac{1}{a_{2}}+\ldots+\frac{1}{a_{n}}=1$ and also assume that the biggest number among them is equal to $2p$, where $p$ is some prime number. Determine $a_{i}$ ($i=\overline{1,n}$).
4. Let $ABC$ be a isosceles right triangle ($AB=BC$) and let $O$ be the midpoint of $AC$. Through $C$ draw the line $d$ perpendicular to $BC$. Let $Cx$ be the opposite ray of the ray $CB$ and $M$ be an arbitrary point on $Cx$. Assume that $E$ is the intersection between $BE$ and $OM$. Prove that when $M$ varies on $Cx$, $I$ always belongs to a fixed curve.
5. Solve the following equation $x^{2}-2x=2\sqrt{2x-1}.$
6. Solve the following inequation $\frac{2x^{3}+3x}{7-2x}>\sqrt{2-x}.$
7. Given an acute and non-isosceles triangle $ABC$ with the altitudes $AH$, $BE$, $CF$. Let $I$ be the incenter of $ABC$ (the center of the inscribed circle) and $R$ be the circumradius of $ABC$ (the radius of the circumscribed circle). Let $M,N$ and $P$ respectively be the midpoint of $BC,CA$ and $AB$. Assume that $K,J$ and $L$ respectively are the intersections between $MI$ and $AH$, $NI$ and $BE$, and $PI$ and $CF$. Prove that $\frac{1}{HK}+\frac{1}{EJ}+\frac{1}{FL}>\frac{3}{R}.$
8. Let $a,b,c$ be the lengths of three sides of a triangle whose perimeter is equal to $3$. Find the minimum value of the expression $T=a^{3}+b^{3}+c^{3}+\sqrt{5}abc.$
9. For every positive integer $n$ prove that the following numbers are perfect square $10([(4+\sqrt{15})^{n}+1])([(4+\sqrt{15})^{n+1}]+1)-60,$ $6([(4+\sqrt{15})^{n}+1])([(4+\sqrt{15})^{n+1}]+1)-60,$ $15([(4+\sqrt{15})^{n}+1])^{2}-60,$ where $[x]$ is the integerpart of $x$.
10. Let $f(x)=x^{3}-3x^{2}+1$.
a) Find the number of different real solutions of the equation $f(f(x))=0$.
b) Let $\alpha be$the maximal positive solution of $f(x)$.
Prove that $[\alpha^{2020}]$ is divisible by $17$ (notice that $[x]$ is the integer part of $x$).
11. Give the sequence $(u_{n})$ where $u_{1}=2$, $u_{2}=20$, $u_{3}=56$ and $u_{n+3}=7u_{n+2}-11u_{n+1}+5u_{n}-3.2^{n},\quad\forall n\in\mathbb{N}^{*}.$ Find the remainder of the division $u_{2011}$ by $2011$.
12. Consider any triangle $ABC$ and any line $d$. Let $A_{1},B_{1},C_{1}$ are the projections of $A,B,C$ onto $d$. It is a fact that the line through $A_{1}$ and perpendicular to $BC$, the line through $B_{1}$ and perpendicular to $AC$, and the line through $C_{1}$ and perpendicular to $AB$ are concurrent ar a point which is called the orthogonal pole of $d$ with respect to $ABC$. Prove that for any triangle and any point $P$ on its circumcircle, the Simon line corresponding to $P$ and the orthogonal pole of the Simon line with respect to the given triangle.

1. For pairwise distinct nonnegative reals $a,b,c$, prove that $$\frac{a^2}{(b-c)^2}+\frac{b^2}{(c-a)^2}+\frac{c^2}{(b-a)^2}>2.$$
2. Define a function $f(n)$ from the positive integers to the positive integers such that $f(f(n))$ is the number of positive integer divisors of $n$. Prove that if $p$ is a prime, then $f(p)$ is prime.
3. Define $S_n$ as the set ${1,2,\cdots,n}$. A non-empty subset $T_n$ of $S_n$ is called balanced if the average of the elements of $T_n$ is equal to the median of $T_n$. Prove that, for all $n$, the number of balanced subsets $T_n$ is odd.
4. Let $ABCD$ be a parallelogram. Points $P$ and $Q$ lie inside $ABCD$ such that $\bigtriangleup ABP$ and $\bigtriangleup{BCQ}$ are equilateral. Prove that the intersection of the line through $P$ perpendicular to $PD$ and the line through $Q$ perpendicular to $DQ$ lies on the altitude from $B$ in $\bigtriangleup{ABC}$.
5. There are $100$ circles of radius one in the plane. A triangle formed by the centres of any three given circles has area at most $2017$. Prove that there is a line intersecting at least three of the circles.

### William Lowell Putnam Mathematical Competition 2016 Solutions

1. Find the smallest positive integer $j$ such that for every polynomial $p(x)$ with integer coefficients and for every integer $k,$ the integer $p^{(j)}(k)=\left. \frac{d^j}{dx^j}p(x) \right|_{x=k}$(the $j$-th derivative of $p(x)$ at $k$) is divisible by $2016.$
2. Given a positive integer $n,$ let $M(n)$ be the largest integer $m$ such that $\binom{m}{n-1}>\binom{m-1}{n}.$ Evaluate $\lim_{n\to\infty}\frac{M(n)}{n}.$
3. Suppose that $f$ is a function from $\mathbb{R}$ to $\mathbb{R}$ such that $f(x)+f\left(1-\frac1x\right)=\arctan x$for all real $x\ne 0.$ (As usual, $y=\arctan x$ means $-\pi/2<y<\pi/2$ and $\tan y=x.$) Find $\int_0^1f(x)\,dx.$
4. Consider a $(2m-1)\times(2n-1)$ rectangular region, where $m$ and $n$ are integers such that $m,n\ge 4.$ The region is to be tiled using tiles of the two types shown:
$$\begin{picture}(140,40) \put(0,0){\line(0,1){40}} \put(0,0){\line(1,0){20}} \put(0,40){\line(1,0){40}} \put(20,0){\line(0,1){20}} \put(20,20){\line(1,0){20}} \put(40,20){\line(0,1){20}} \multiput(0,20)(5,0){4}{\line(1,0){3}} \multiput(20,20)(0,5){4}{\line(0,1){3}} \put(80,0){\line(1,0){40}} \put(120,0){\line(0,1){20}} \put(120,20){\line(1,0){20}} \put(140,20){\line(0,1){20}} \put(80,0){\line(0,1){20}} \put(80,20){\line(1,0){20}} \put(100,20){\line(0,1){20}} \put(100,40){\line(1,0){40}} \multiput(100,0)(0,5){4}{\line(0,1){3}} \multiput(100,20)(5,0){4}{\line(1,0){3}} \multiput(120,20)(0,5){4}{\line(0,1){3}} \end{picture}$$
(The dotted lines divide the tiles into $1\times 1$ squares.) The tiles may be rotated and reflected, as long as their sides are parallel to the sides of the rectangular region. They must all fit within the region, and they must cover it completely without overlapping. What is the minimum number of tiles required to tile the region?
5. Suppose that $G$ is a finite group generated by the two elements $g$ and $h,$ where the order of $g$ is odd. Show that every element of $G$ can be written in the form $g^{m_1}h^{n_1}g^{m_2}h^{n_2}\cdots g^{m_r}h^{n_r}$with $1\le r\le |G|$ and $m_n,n_1,m_2,n_2,\dots,m_r,n_r\in\{1,-1\}.$ (Here $|G|$ is the number of elements of $G.$)
6. Find the smallest constant $C$ such that for every real polynomial $P(x)$ of degree $3$ that has a root in the interval $[0,1],$ $\int_0^1|P(x)|\,dx\le C\max_{x\in[0,1]}|P(x)|.$
7. Let $x_0,x_1,x_2,\dots$ be the sequence such that $x_0=1$ and for $n\ge 0,$ $x_{n+1}=\ln(e^{x_n}-x_n)$(as usual, the function $\ln$ is the natural logarithm). Show that the infinite series $x_0+x_1+x_2+\cdots$converges and find its sum.
8. Define a positive integer $n$ to be squarish if either $n$ is itself a perfect square or the distance from $n$ to the nearest perfect square is a perfect square. For example, $2016$ is squarish, because the nearest perfect square to $2016$ is $45^2=2025$ and $2025-2016=9$ is a perfect square. (Of the positive integers between $1$ and $10,$ only $6$ and $7$ are not squarish.) For a positive integer $N,$ let $S(N)$ be the number of squarish integers between $1$ and $N,$ inclusive. Find positive constants $\alpha$ and $\beta$ such that $\lim_{N\to\infty}\frac{S(N)}{N^{\alpha}}=\beta,$or show that no such constants exist.
9. Suppose that $S$ is a finite set of points in the plane such that the area of triangle $\triangle ABC$ is at most $1$ whenever $A,B,$ and $C$ are in $S.$ Show that there exists a triangle of area $4$ that (together with its interior) covers the set $S.$
10. Let $A$ be a $2n\times 2n$ matrix, with entries chosen independently at random. Every entry is chosen to be $0$ or $1,$ each with probability $1/2.$ Find the expected value of $\det(A-A^t)$ (as a function of $n$), where $A^t$ is the transpose of $A.$
11. Find all functions $f$ from the interval $(1,\infty)$ to $(1,\infty)$ with the following property: if $x,y\in(1,\infty)$ and $x^2\le y\le x^3,$ then $(f(x))^2\le f(y) \le (f(x))^3.$
12. Evaluate $\sum_{k=1}^{\infty}\frac{(-1)^{k-1}}{k}\sum_{n=0}^{\infty}\frac{1}{k2^n+1}.$

1. The integers $1, 2, 3, \ldots, 2016$ are written on a board. You can choose any two numbers on the board and replace them with their average. For example, you can replace $1$ and $2$ with $1.5$, or you can replace $1$ and $3$ with a second copy of $2$. After $2015$ replacements of this kind, the board will have only one number left on it. (a) Prove that there is a sequence of replacements that will make the final number equal to $2$. (b) Prove that there is a sequence of replacements that will make the final number equal to $1000$.
2. Consider the following system of $10$ equations in $10$ real variables $v_1, \ldots, v_{10}$ $v_i = 1 + \frac{6v_i^2}{v_1^2 + v_2^2 + \cdots + v_{10}^2} \qquad (i = 1, \ldots, 10).$Find all $10$-tuples $(v_1, v_2, \ldots , v_{10})$ that are solutions of this system.
3. Find all polynomials $P(x)$ with integer coefficients such that $P(P(n) + n)$ is a prime number for infinitely many integers $n$.
4. Let $A, B$, and $F$ be positive integers, and assume $A < B < 2A$. A flea is at the number $0$ on the number line. The flea can move by jumping to the right by $A$ or by $B$. Before the flea starts jumping, Lavaman chooses finitely many intervals $\{m+1, m+2, \ldots, m+A\}$ consisting of $A$ consecutive positive integers, and places lava at all of the integers in the intervals. The intervals must be chosen so that
(i) any two distinct intervals are disjoint and not adjacent;
(ii) there are at least $F$ positive integers with no lava between any two intervals; and
(iii) no lava is placed at any integer less than $F$.
Prove that the smallest $F$ for which the flea can jump over all the intervals and avoid all the lava, regardless of what Lavaman does, is $F = (n-1)A + B$, where $n$ is the positive integer such that $$\frac{A}{n+1} \le B-A < \frac{A}{n}.$$
5. Let $\triangle ABC$ be an acute-angled triangle with altitudes $AD$ and $BE$ meeting at $H$. Let $M$ be the midpoint of segment $AB$, and suppose that the circumcircles of $\triangle DEM$ and $\triangle ABH$ meet at points $P$ and $Q$ with $P$ on the same side of $CH$ as $A$. Prove that the lines $ED, PH,$ and $MQ$ all pass through a single point on the circumcircle of $\triangle ABC$.

1. Let $\mathbb{N} = \{1, 2, 3, \ldots\}$ be the set of positive integers. Find all functions $f$, defined on $\mathbb{N}$ and taking values in $\mathbb{N}$, such that $$(n-1)^2< f(n)f(f(n)) < n^2+n$$ for every positive integer $n$.
2. Let $ABC$ be an acute-angled triangle with altitudes $AD,BE,$ and $CF$. Let $H$ be the orthocentre, that is, the point where the altitudes meet. Prove that $\frac{AB\cdot AC+BC\cdot CA+CA\cdot CB}{AH\cdot AD+BH\cdot BE+CH\cdot CF}\leq 2.$
3. On a $(4n + 2)\times (4n + 2)$ square grid, a turtle can move between squares sharing a side.The turtle begins in a corner square of the grid and enters each square exactly once, ending in the square where she started. In terms of $n$, what is the largest positive integer $k$ such that there must be a row or column that the turtle has entered at least $k$ distinct times?
4. Let $ABC$ be an acute-angled triangle with circumcenter $O$. Let $I$ be a circle with center on the altitude from $A$ in $ABC$, passing through vertex $A$ and points $P$ and $Q$ on sides $AB$ and $AC$. Assume that $BP\cdot CQ = AP\cdot AQ.$Prove that $I$ is tangent to the circumcircle of triangle $BOC$.
5. Let $p$ be a prime number for which $\frac{p-1}{2}$ is also prime, and let $a,b,c$ be integers not divisible by $p$. Prove that there are at most $1+\sqrt {2p}$ positive integers $n$ such that $n<p$ and $p$ divides $a^n+b^n+c^n$.

1. Let $a_1,a_2,\dots,a_n$ be positive real numbers whose product is $1$. Show that the sum $\frac{a_1}{1+a_1}+\frac{a_2}{(1+a_1)(1+a_2)}+\cdots+\frac{a_n}{(1+a_1)(1+a_2)\cdots(1+a_n)}$ is greater than or equal to $\frac{2^n-1}{2^n}$.
2. Let $m$ and $n$ be odd positive integers. Each square of an $m$ by $n$ board is coloured red or blue. A row is said to be red-dominated if there are more red squares than blue squares in the row. A column is said to be blue-dominated if there are more blue squares than red squares in the column. Determine the maximum possible value of the number of red-dominated rows plus the number of blue-dominated columns. Express your answer in terms of $m$ and $n$.
3. Let $p$ be a fixed odd prime. A $p$-tuple $(a_1,a_2,a_3,\ldots,a_p)$ of integers is said to be good if
(i) $0\le a_i\le p-1$ for all $i$, and
(ii) $a_1+a_2+a_3+\cdots+a_p$ is not divisible by $p$, and
(iii) $a_1a_2+a_2a_3+a_3a_4+\cdots+a_pa_1$ is divisible by $p$.
Determine the number of good $p$-tuples.
4. The quadrilateral $ABCD$ is inscribed in a circle. The point $P$ lies in the interior of $ABCD$, and $\angle P AB = \angle P BC = \angle P CD = \angle P DA$. The lines $AD$ and $BC$ meet at $Q$, and the lines $AB$ and $CD$ meet at $R$. Prove that the lines $P Q$ and $P R$ form the same angle as the diagonals of $ABCD$.
5. Fix positive integers $n$ and $k\ge 2$. A list of $n$ integers is written in a row on a blackboard. You can choose a contiguous block of integers, and I will either add $1$ to all of them or subtract $1$ from all of them. You can repeat this step as often as you like, possibly adapting your selections based on what I do. Prove that after a finite number of steps, you can reach a state where at least $n-k+2$ of the numbers on the blackboard are all simultaneously divisible by $k$.

### William Lowell Putnam Mathematical Competition 2015 Solutions

1. Let $A$ and $B$ be points on the same branch of the hyperbola $xy=1.$ Suppose that $P$ is a point lying between $A$ and $B$ on this hyperbola, such that the area of the triangle $APB$ is as large as possible. Show that the region bounded by the hyperbola and the chord $AP$ has the same area as the region bounded by the hyperbola and the chord $PB.$
2. Let $a_0=1,a_1=2,$ and $a_n=4a_{n-1}-a_{n-2}$ for $n\ge 2.$ Find an odd prime factor of $a_{2015}.$
3. Compute $\log_2\left(\prod_{a=1}^{2015}\prod_{b=1}^{2015}\left(1+e^{2\pi iab/2015}\right)\right)$Here $i$ is the imaginary unit (that is, $i^2=-1$).
4. For each real number $x,$ let $f(x)=\sum_{n\in S_x}\frac1{2^n}$where $S_x$ is the set of positive integers $n$ for which $\lfloor nx\rfloor$ is even. What is the largest real number $L$ such that $f(x)\ge L$ for all $x\in [0,1)$? (As usual, $\lfloor z\rfloor$ denotes the greatest integer less than or equal to $z.$
5. Let $q$ be an odd positive integer, and let $N_q$ denote the number of integers $a$ such that $0<a<q/4$ and $\gcd(a,q)=1.$ Show that $N_q$ is odd if and only if $q$ is of the form $p^k$ with $k$ a positive integer and $p$ a prime congruent to $5$ or $7$ modulo $8.$
6. Let $n$ be a positive integer. Suppose that $A,B,$ and $M$ are $n\times n$ matrices with real entries such that $AM=MB,$ and such that $A$ and $B$ have the same characteristic polynomial. Prove that $\det(A-MX)=\det(B-XM)$ for every $n\times n$ matrix $X$ with real entries.
7. Let $f$ be a three times differentiable function (defined on $\mathbb{R}$ and real-valued) such that $f$ has at least five distinct real zeros. Prove that $f+6f'+12f''+8f'''$ has at least two distinct real zeros.
8. Given a list of the positive integers $1,2,3,4,\dots,$ take the first three numbers $1,2,3$ and their sum $6$ and cross all four numbers off the list. Repeat with the three smallest remaining numbers $4,5,7$ and their sum $16.$ Continue in this way, crossing off the three smallest remaining numbers and their sum and consider the sequence of sums produced: $6,16,27, 36, \dots.$ Prove or disprove that there is some number in this sequence whose base 10 representation ends with $2015.$
9. Let $S$ be the set of all $2\times 2$ real matrices $M=\begin{pmatrix}a&b\\c&d\end{pmatrix}$whose entries $a,b,c,d$ (in that order) form an arithmetic progression. Find all matrices $M$ in $S$ for which there is some integer $k>1$ such that $M^k$ is also in $S.$
10. Let $T$ be the set of all triples $(a,b,c)$ of positive integers for which there exist triangles with side lengths $a,b,c.$ Express $\sum_{(a,b,c)\in T}\frac{2^a}{3^b5^c}$as a rational number in lowest terms.
11. Let $P_n$ be the number of permutations $\pi$ of $\{1,2,\dots,n\}$ such that $|i-j|=1\text{ implies }|\pi(i)-\pi(j)|\le 2$for all $i,j$ in $\{1,2,\dots,n\}.$ Show that for $n\ge 2,$ the quantity $P_{n+5}-P_{n+4}-P_{n+3}+P_n$does not depend on $n,$ and find its value.
12. For each positive integer $k,$ let $A(k)$ be the number of odd divisors of $k$ in the interval $\left[1,\sqrt{2k}\right).$ Evaluate $\sum_{k=1}^{\infty}(-1)^{k-1}\frac{A(k)}k.$

1. Determine all polynomials $P(x)$ with real coefficients such that $(x+1)P(x-1)-(x-1)P(x)$ is a constant polynomial.
2. The sequence $a_1, a_2, \dots, a_n$ consists of the numbers $1, 2, \dots, n$ in some order. For which positive integers $n$ is it possible that the $n+1$ numbers $0$, $a_1$, $a_1+a_2$, $a_1+a_2+a_3$, $\dots$, $a_1 + a_2 +\cdots + a_n$ all have different remainders when divided by $n + 1$?
3. Let $G$ be the centroid of a right-angled triangle $ABC$ with $\angle BCA = 90^\circ$. Let $P$ be the point on ray $AG$ such that $\angle CPA = \angle CAB$, and let $Q$ be the point on ray $BG$ such that $\angle CQB = \angle ABC$. Prove that the circumcircles of triangles $AQG$ and $BPG$ meet at a point on side $AB$.
4. Let $n$ be a positive integer. For any positive integer $j$ and positive real number $r$, define $f_j(r)$ and $g_j(r)$ by $$f_j(r) = \min (jr, n) + \min\left(\frac{j}{r}, n\right),$$ $$g_j(r) = \min (\lceil jr\rceil, n) + \min \left(\left\lceil\frac{j}{r}\right\rceil, n\right),$$ where $\lceil x\rceil$ denotes the smallest integer greater than or equal to $x$. Prove that $\sum_{j=1}^n f_j(r)\leq n^2+n\leq \sum_{j=1}^n g_j(r)$ for all positive real numbers $r$.
5. Let $O$ denote the circumcentre of an acute-angled triangle $ABC$. Let point $P$ on side $AB$ be such that $\angle BOP = \angle ABC$, and let point $Q$ on side $AC$ be such that $\angle COQ = \angle ACB$. Prove that the reflection of $BC$ in the line $PQ$ is tangent to the circumcircle of triangle $APQ$.

### William Lowell Putnam Mathematical Competition 2014 Solutions

1. Prove that every nonzero coefficient of the Taylor series of $(1-x+x^2)e^x$ about $x=0$ is a rational number whose numerator (in lowest terms) is either $1$ or a prime number.
2. Let $A$ be the $n\times n$ matrix whose entry in the $i$-th row and $j$-th column is $\frac1{\min(i,j)}$ for $1\le i,j\le n.$ Compute $\det(A).$
3. Let $a_0=5/2$ and $a_k=a_{k-1}^2-2$ for $k\ge 1.$ Compute $\prod_{k=0}^{\infty}\left(1-\frac1{a_k}\right)$ in closed form.
4. Suppose $X$ is a random variable that takes on only nonnegative integer values, with $E[X]=1,$ $E[X^2]=2,$ and $E[X^3]=5.$ (Here $E[Y]$ denotes the expectation of the random variable $Y.$) Determine the smallest possible value of the probability of the event $X=0.$
5. Let $P_n(x)=1+2x+3x^2+\cdots+nx^{n-1}.$ Prove that the polynomials $P_j(x)$ and $P_k(x)$ are relatively prime for all positive integers $j$ and $k$ with $j\ne k.$
6. Let $n$ be a positive integer. What is the largest $k$ for which there exist $n\times n$ matrices $M_1,\dots,M_k$ and $N_1,\dots,N_k$ with real entries such that for all $i$ and $j,$ the matrix product $M_iN_j$ has a zero entry somewhere on its diagonal if and only if $i\ne j?$
7. A base 10 over-expansion of a positive integer $N$ is an expression of the form $$N=d_k10^k+d_{k-1}10^{k-1}+\cdots+d_0 10^0$$ with $d_k\ne 0$ and $d_i\in\{0,1,2,\dots,10\}$ for all $i.$ For instance, the integer $N=10$ has two base 10 over-expansions: $10=10\cdot 10^0$ and the usual base 10 expansion $10=1\cdot 10^1+0\cdot 10^0.$ Which positive integers have a unique base 10 over-expansion?
8. Suppose that $f$ is a function on the interval $[1,3]$ such that $-1\le f(x)\le 1$ for all $x$ and $\displaystyle \int_1^3f(x)\,dx=0.$ How large can $\displaystyle\int_1^3\frac{f(x)}x\,dx$ be?
9. Let $A$ be an $m\times n$ matrix with rational entries. Suppose that there are at least $m+n$ distinct prime numbers among the absolute values of the entries of $A.$ Show that the rank of $A$ is at least $2.$
10. Show that for each positive integer $n,$ all the roots of the polynomial $\sum_{k=0}^n 2^{k(n-k)}x^k$ are real numbers.
11. In the 75th Annual Putnam Games, participants compete at mathematical games. Patniss and Keeta play a game in which they take turns choosing an element from the group of invertible $n\times n$ matrices with entries in the field $\mathbb{Z}/p\mathbb{Z}$ of integers modulo $p,$ where $n$ is a fixed positive integer and $p$ is a fixed prime number. The rules of the game are: (1) A player cannot choose an element that has been chosen by either player on any previous turn. (2) A player can only choose an element that commutes with all previously chosen elements. (3) A player who cannot choose an element on his/her turn loses the game. Patniss takes the first turn. Which player has a winning strategy?
12. Let $f:[0,1]\to\mathbb{R}$ be a function for which there exists a constant $K>0$ such that $|f(x)-f(y)|\le K|x-y|$ for all $x,y\in [0,1].$ Suppose also that for each rational number $r\in [0,1],$ there exist integers $a$ and $b$ such that $f(r)=a+br.$ Prove that there exist finitely many intervals $I_1,\dots,I_n$ such that $f$ is a linear function on each $I_i$ and $[0,1]=\bigcup_{i=1}^nI_i.$

### William Lowell Putnam Mathematical Competition 2013 Solutions

1. Recall that a regular icosahedron is a convex polyhedron having 12 vertices and 20 faces; the faces are congruent equilateral triangles. On each face of a regular icosahedron is written a nonnegative integer such that the sum of all $20$ integers is $39.$ Show that there are two faces that share a vertex and have the same integer written on them.
2. Let $S$ be the set of all positive integers that are not perfect squares. For $n$ in $S,$ consider choices of integers $a_1,a_2,\dots, a_r$ such that $n<a_1<a_2<\cdots<a_r$ and $n\cdot a_1\cdot a_2\cdots a_r$ is a perfect square, and let $f(n)$ be the minimum of $a_r$ over all such choices. For example, $2\cdot 3\cdot 6$ is a perfect square, while $2\cdot 3,2\cdot 4, 2\cdot 5, 2\cdot 3\cdot 4,$ $2\cdot 3\cdot 5, 2\cdot 4\cdot 5,$ and $2\cdot 3\cdot 4\cdot 5$ are not, and so $f(2)=6.$ Show that the function $f$ from $S$ to the integers is one-to-one.
3. Suppose that the real numbers $a_0,a_1,\dots,a_n$ and $x,$ with $0<x<1,$ satisfy $\frac{a_0}{1-x}+\frac{a_1}{1-x^2}+\cdots+\frac{a_n}{1-x^{n+1}}=0.$ Prove that there exists a real number $y$ with $0<y<1$ such that $a_0+a_1y+\cdots+a_ny^n=0.$
4. A finite collection of digits $0$ and $1$ is written around a circle. An arc of length $L\ge 0$ consists of $L$ consecutive digits around the circle. For each arc $w,$ let $Z(w)$ and $N(w)$ denote the number of $0$'s in $w$ and the number of $1$'s in $w,$ respectively. Assume that $|Z(w)-Z(w')|\le 1$ for any two arcs $w,w'$ of the same length. Suppose that some arcs $w_1,\dots,w_k$ have the property that $Z=\frac1k\sum_{j=1}^kZ(w_j)\text{ and }N=\frac1k\sum_{j=1}^k N(w_j)$ are both integers. Prove that there exists an arc $w$ with $Z(w)=Z$ and $N(w)=N.$
5. For $m\ge 3,$ a list of $\binom m3$ real numbers $a_{ijk}$ $(1\le i<j<k\le m)$ is said to be area definite for $\mathbb{R}^n$ if the inequality $\sum_{1\le i<j<k\le m}a_{ijk}\cdot\text{Area}(\triangle A_iA_jA_k)\ge0$ holds for every choice of $m$ points $A_1,\dots,A_m$ in $\mathbb{R}^n.$ For example, the list of four numbers $a_{123}=a_{124}=a_{134}=1, a_{234}=-1$ is area definite for $\mathbb{R}^2.$ Prove that if a list of $\binom m3$ numbers is area definite for $\mathbb{R}^2,$ then it is area definite for $\mathbb{R}^3.$
6. Define a function $w:\mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}$ as follows. For $|a|,|b|\le 2,$ let $w(a,b)$ be as in the table shown; otherwise, let $w(a,b)=0.$ $\begin{array}{|lr|rrrrr|}\hline &&&&b&&\\ &w(a,b)&-2&-1&0&1&2\\ \hline &-2&-1&-2&2&-2&-1\\ &-1&-2&4&-4&4&-2\\ a&0&2&-4&12&-4&2\\ &1&-2&4&-4&4&-2\\ &2&-1&-2&2&-2&-1\\ \hline\end{array}$ For every finite subset $S$ of $\mathbb{Z}\times\mathbb{Z},$ define $A(S)=\sum_{(\mathbf{s},\mathbf{s'})\in S\times S} w(\mathbf{s}-\mathbf{s'}).$ Prove that if $S$ is any finite nonempty subset of $\mathbb{Z}\times\mathbb{Z},$ then $A(S)>0.$
For example, if $S=\{(0,1),(0,2),(2,0),(3,1)\},$ then the terms in $A(S)$ are $12,12,12,12,4,4,0,0,0,0,-1,-1,-2,-2,-4,-4.$
7. For positive integers $n,$ let the numbers $c(n)$ be determined by the rules $c(1)=1,c(2n)=c(n),$ and $c(2n+1)=(-1)^nc(n).$ Find the value of $\sum_{n=1}^{2013}c(n)c(n+2).$
8. Let $C=\bigcup_{N=1}^{\infty}C_N,$ where $C_N$ denotes the set of 'cosine polynomials' of the form $f(x)=1+\sum_{n=1}^Na_n\cos(2\pi nx)$ for which: (i) $f(x)\ge 0$ for all real $x,$ and (ii) $a_n=0$ whenever $n$ is a multiple of $3.$ Determine the maximum value of $f(0)$ as $f$ ranges through $C,$ and prove that this maximum is attained.
9. Let $P$ be a nonempty collection of subsets of $\{1,\dots,n\}$ such that: (i) if $S,S'\in P,$ then $S\cup S'\in P$ and $S\cap S'\in P,$ and (ii) if $S\in P$ and $S\ne\emptyset,$ then there is a subset $T\subset S$ such that $T\in P$ and $T$ contains exactly one fewer element than $S.$ Suppose that $f:P\to\mathbb{R}$ is a function such that $f(\emptyset)=0$ and $f(S\cup S')= f(S)+f(S')-f(S\cap S')\text{ for all }S,S'\in P.$ Must there exist real numbers $f_1,\dots,f_n$ such that $f(S)=\sum_{i\in S}f_i$ for every $S\in P?$
10. For any continuous real-valued function $f$ defined on the interval $[0,1],$ let $$\mu(f)=\int_0^1f(x)dx,$$ $$\text{Var}(f)=\int_0^1(f(x)-\mu(f))^2dx,$$ $$M(f)=\max_{0\le x\le 1}|f(x)|.$$ Show that if $f$ and $g$ are continuous real-valued functions defined on the interval $[0,1],$ then $\text{Var}(fg)\le 2\text{Var}(f)M(g)^2+2\text{Var}(g)M(f)^2.$
11. Let $X=\{1,2,\dots,n\},$ and let $k\in X.$ Show that there are exactly $k\cdot n^{n-1}$ functions $f:X\to X$ such that for every $x\in X$ there is a $j\ge 0$ such that $f^{(j)}(x)\le k.$ [Here $f^{(j)}$ denotes the $j$th iterate of $f,$ so that $f^{(0)}(x)=x$ and $f^{(j+1)}(x)=f\left(f^{(j)}(x)\right).$]
12. Let $n\ge 1$ be an odd integer. Alice and Bob play the following game, taking alternating turns, with Alice playing first. The playing area consists of $n$ spaces, arranged in a line. Initially all spaces are empty. At each turn, a player either - places a stone in an empty space, or - removes a stone from a nonempty space $s,$ places a stone in the nearest empty space to the left of $s$ (if such a space exists), and places a stone in the nearest empty space to the right of $s$ (if such a space exists). Furthermore, a move is permitted only if the resulting position has not occurred previously in the game. A player loses if he or she is unable to move. Assuming that both players play optimally throughout the game, what moves may Alice make on her first turn?

1. Let $x,y$ and $z$ be positive real numbers. Show that $$x^2+xy^2+xyz^2\ge 4xyz-4.$$
2. For any positive integers $n$ and $k$, let $L(n,k)$ be the least common multiple of the $k$ consecutive integers $n,n+1,\ldots ,n+k-1$. Show that for any integer $b$, there exist integers $n$ and $k$ such that $L(n,k)>bL(n+1,k)$.
3. Let $ABCD$ be a convex quadrilateral and let $P$ be the point of intersection of $AC$ and $BD$. Suppose that $AC+AD=BC+BD$. Prove that the internal angle bisectors of $\angle ACB$, $\angle ADB$ and $\angle APB$ meet at a common point.
4. A number of robots are placed on the squares of a finite, rectangular grid of squares. A square can hold any number of robots. Every edge of each square of the grid is classified as either passable or impassable. All edges on the boundary of the grid are impassable. You can give any of the commands up, down, left, or right. All of the robots then simultaneously try to move in the specified direction. If the edge adjacent to a robot in that direction is passable, the robot moves across the edge and into the next square. Otherwise, the robot remains on its current square. You can then give another command of up, down, left, or right, then another, for as long as you want. Suppose that for any individual robot, and any square on the grid, there is a finite sequence of commands that will move that robot to that square. Prove that you can also give a finite sequence of commands such that all of the robots end up on the same square at the same time.
5. A bookshelf contains $n$ volumes, labelled $1$ to $n$, in some order. The librarian wishes to put them in the correct order as follows. The librarian selects a volume that is too far to the right, say the volume with label $k$, takes it out, and inserts it in the $k$-th position. For example, if the bookshelf contains the volumes $1,3,2,4$ in that order, the librarian could take out volume $2$ and place it in the second position. The books will then be in the correct order $1,2,3,4$.
(a) Show that if this process is repeated, then, however the librarian makes the selections, all the volumes will eventually be in the correct order.
(b) What is the largest number of steps that this process can take?

1. Consider $70$-digit numbers with the property that each of the digits $1,2,3,...,7$ appear $10$ times in the decimal expansion of $n$ (and $8,9,0$ do not appear). Show that no number of this form can divide another number of this form.
2. Let $ABCD$ be a cyclic quadrilateral with opposite sides not parallel. Let $X$ and $Y$ be the intersections of $AB,CD$ and $AD,BC$ respectively. Let the angle bisector of $\angle AXD$ intersect $AD,BC$ at $E,F$ respectively, and let the angle bisectors of $\angle AYB$ intersect $AB,CD$ at $G,H$ respectively. Prove that $EFGH$ is a parallelogram.
3. Amy has divided a square into finitely many white and red rectangles, each with sides parallel to the sides of the square. Within each white rectangle, she writes down its width divided by its height. Within each red rectangle, she writes down its height divided by its width. Finally, she calculates $x$, the sum of these numbers. If the total area of white equals the total area of red, determine the minimum of $x$.
4. Show that there exists a positive integer $N$ such that for all integers $a>N$, there exists a contiguous substring of the decimal expansion of $a$, which is divisible by $2011$. (Note. A contiguous substring of an integer $a$ is an integer with a decimal expansion equivalent to a sequence of consecutive digits taken from the decimal expansion of $a$.)
5. Let $d$ be a positive integer. Show that for every integer $S$, there exists an integer $n>0$ and a sequence of $n$ integers $\epsilon_1, \epsilon_2,..., \epsilon_n$, where $\epsilon_i = \pm 1$ (not necessarily dependent on each other) for all integers $1\le i\le n$, such that $$S=\sum_{i=1}^{n}{\epsilon_i(1+id)^2}.$$

### William Lowell Putnam Mathematical Competition 2012 Solutions

1. Let $d_1,d_2,\dots,d_{12}$ be real numbers in the open interval $(1,12).$ Show that there exist distinct indices $i,j,k$ such that $d_i,d_j,d_k$ are the side lengths of an acute triangle.
2. Let $*$ be a commutative and associative binary operation on a set $S.$ Assume that for every $x$ and $y$ in $S,$ there exists $z$ in $S$ such that $x*z=y.$ (This $z$ may depend on $x$ and $y.$) Show that if $a,b,c$ are in $S$ and $a*c=b*c,$ then $a=b.$
3. Let $f:[-1,1]\to\mathbb{R}$ be a continuous function such that
(i) $f(x)=\frac{2-x^2}{2}f\left(\frac{x^2}{2-x^2}\right)$ for every $x$ in $[-1,1],$
(ii) $f(0)=1,$ and
(iii) $\lim_{x\to 1^-}\frac{f(x)}{\sqrt{1-x}}$ exists and is finite.
Prove that $f$ is unique, and express $f(x)$ in closed form.
4. Let $q$ and $r$ be integers with $q>0,$ and let $A$ and $B$ be intervals on the real line. Let $T$ be the set of all $b+mq$ where $b$ and $m$ are integers with $b$ in $B,$ and let $S$ be the set of all integers $a$ in $A$ such that $ra$ is in $T.$ Show that if the product of the lengths of $A$ and $B$ is less than $q,$ then $S$ is the intersection of $A$ with some arithmetic progression.
5. Let $\mathbb{F}_p$ denote the field of integers modulo a prime $p,$ and let $n$ be a positive integer. Let $v$ be a fixed vector in $\mathbb{F}_p^n,$ let $M$ be an $n\times n$ matrix with entries in $\mathbb{F}_p,$ and define $G:\mathbb{F}_p^n\to \mathbb{F}_p^n$ by $G(x)=v+Mx.$ Let $G^{(k)}$ denote the $k$-fold composition of $G$ with itself, that is, $$G^{(1)}(x)=G(x), \quad G^{(k+1)}(x)=G(G^{(k)}(x)).$$ Determine all pairs $p,n$ for which there exist $v$ and $M$ such that the $p^n$ vectors $G^{(k)}(0),$ $k=1,2,\dots,p^n$ are distinct.
6. Let $f(x,y)$ be a continuous, real-valued function on $\mathbb{R}^2.$ Suppose that, for every rectangular region $R$ of area $1,$ the double integral of $f(x,y)$ over $R$ equals $0.$ Must $f(x,y)$ be identically $0?$
7. Let $S$ be a class of functions from $[0,\infty)$ to $[0,\infty)$ that satisfies:
(i) The functions $f_1(x)=e^x-1$ and $f_2(x)=\ln(x+1)$ are in $S;$
(ii) If $f(x)$ and $g(x)$ are in $S,$ the functions $f(x)+g(x)$ and $f(g(x))$ are in $S;$
(iii) If $f(x)$ and $g(x)$ are in $S$ and $f(x)\ge g(x)$ for all $x\ge 0,$ then the function $f(x)-g(x)$ is in $S.$
Prove that if $f(x)$ and $g(x)$ are in $S,$ then the function $f(x)g(x)$ is also in $S.$
8. Let $P$ be a given (non-degenerate) polyhedron. Prove that there is a constant $c(P)>0$ with the following property: If a collection of $n$ balls whose volumes sum to $V$ contains the entire surface of $P,$ then $n>c(P)/V^2.$
9. A round-robin tournament among $2n$ teams lasted for $2n-1$ days, as follows. On each day, every team played one game against another team, with one team winning and one team losing in each of the $n$ games. Over the course of the tournament, each team played every other team exactly once. Can one necessarily choose one winning team from each day without choosing any team more than once?
10. Suppose that $a_0=1$ and that $a_{n+1}=a_n+e^{-a_n}$ for $n=0,1,2,\dots.$ Does $a_n-\log n$ have a finite limit as $n\to\infty?$ (Here $\log n=\log_en=\ln n.$)
11. Prove that, for any two bounded functions $g_1,g_2 : \mathbb{R}\to[1,\infty),$ there exist functions $h_1,h_2 : \mathbb{R}\to\mathbb{R}$ such that for every $x\in\mathbb{R},$ $\sup_{s\in\mathbb{R}}\left(g_1(s)^xg_2(s)\right)=\max_{t\in\mathbb{R}}\left(xh_1(t)+h_2(t)\right).$
12. Let $p$ be an odd prime number such that $p\equiv 2\pmod{3}.$ Define a permutation $\pi$ of the residue classes modulo $p$ by $\pi(x)\equiv x^3\pmod{p}.$ Show that $\pi$ is an even permutation if and only if $p\equiv 3\pmod{4}.$

1. For all natural $n$, an $n$-staircase is a figure consisting of unit squares, with one square in the first row, two squares in the second row, and so on, up to $n$ squares in the $n^{th}$ row, such that all the left-most squares in each row are aligned vertically. Let $f(n)$ denote the minimum number of square tiles requires to tile the $n$-staircase, where the side lengths of the square tiles can be any natural number. e.g. $f(2)=3$ and $f(4)=7$.
(a) Find all $n$ such that $f(n)=n$.
(b) Find all $n$ such that $f(n) = n+1$.
2. Let $A,B,P$ be three points on a circle. Prove that if $a,b$ are the distances from $P$ to the tangents at $A,B$ respectively, and $c$ is the distance from $P$ to the chord $AB$, then $c^2 =ab$.
3. Three speed skaters have a friendly "race" on a skating oval. They all start from the same point and skate in the same direction, but with different speeds that they maintain throughout the race. The slowest skater does $1$ lap per minute, the fastest one does $3.14$ laps per minute, and the middle one does $L$ laps a minute for some $1 < L < 3.14$. The race ends at the moment when all three skaters again come together to the same point on the oval (which may differ from the starting point.) Determine the number of different choices for $L$ such that exactly $117$ passings occur before the end of the race. (Note. A passing is defined as when one skater passes another one. The beginning and the end of the race when all three skaters are together are not counted as passings.)
4. Each vertex of a finite graph can be coloured either black or white. Initially all vertices are black. We are allowed to pick a vertex $P$ and change the colour of $P$ and all of its neighbours. Is it possible to change the colour of every vertex from black to white by a sequence of operations of this type?. (Note: A finite graph consists of a finite set of vertices and a finite set of edges between vertices. If there is an edge between vertex $A$ and vertex $B,$ then $A$ and $B$ are neighbours of each other.)
5. Let $P(x)$ and $Q(x)$ be polynomials with integer coefficients. Let $a_n = n! +n$. Show that if $\frac{P(a_n)}{Q(a_n)}$ is an integer for every $n$, then $\frac{P(n)}{Q(n)}$ is an integer for every integer $n$ such that $Q(n)\neq 0$.

1. Given an $m\times n$ grid with unit squares coloured either black or white, a black square in the grid is stranded if there is some square to its left in the same row that is white and there is some square above it in the same column that is white. Find a closed formula for the number of $2\times n$ grids with no stranded black square. (Note that $n$ is any natural number and the formula must be in terms of $n$ with no other variables.)
2. Two circles of different radii are cut out of cardboard. Each circle is subdivided into $200$ equal sectors. On each circle $100$ sectors are painted white and the other $100$ are painted black. The smaller circle is then placed on top of the larger circle, so that their centers coincide. Show that one can rotate the small circle so that the sectors on the two circles line up and at least $100$ sectors on the small circle lie over sectors of the same color on the big circle.
3. Define $$f(x,y,z)=\frac{(xy+yz+zx)(x+y+z)}{(x+y)(y+z)(z+x)}.$$ Determine the set of real numbers $r$ for which there exists a triplet of positive real numbers satisfying $f(x,y,z)=r$.
4. Find all ordered pairs of integers $(a,b)$ such that $3^a + 7^b$ is a perfect square.
5. A set of points is marked on the plane, with the property that any three marked points can be covered with a disk of radius $1$. Prove that the set of all marked points can be covered with a disk of radius $1$.

1. $ABCD$ is a convex quadrilateral for which $AB$ is the longest side. Points $M$ and $N$ are located on sides $AB$ and $BC$ respectively, so that each of the segments $AN$ and $CM$ divides the quadrilateral into two parts of equal area. Prove that the segment $MN$ bisects the diagonal $BD$.
2. Determine all functions $f$ defined on the set of rational numbers that take rational values for which $f(2f(x) + f(y)) = 2x + y,$ for each $x$ and $y$.
3. Let $a$, $b$, $c$ be positive real numbers for which $a + b + c = 1$. Prove that ${{a-bc}\over{a+bc}} + {{b-ca}\over{b+ca}} + {{c-ab}\over{c+ab}} \leq {3 \over 2}.$
4. Determine all functions $f$ defined on the natural numbers that take values among the natural numbers for which $(f(n))^p \equiv n\quad {\rm mod}\; f(p)$ for all $n \in {\bf N}$ and all prime numbers $p$.
5. A self-avoiding rook walk on a chessboard (a rectangular grid of unit squares) is a path traced by a sequence of moves parallel to an edge of the board from one unit square to another, such that each begins where the previous move ended and such that no move ever crosses a square that has previously been crossed, i.e., the rook's path is non-self-intersecting. Let $R(m, n)$ be the number of self-avoiding rook walks on an $m \times n$ ($m$ rows, $n$ columns) chessboard which begin at the lower-left corner and end at the upper-left corner. For example, $R(m, 1) = 1$ for all natural numbers $m$; $R(2, 2) = 2$; $R(3, 2) = 4$; $R(3, 3) = 11$. Find a formula for $R(3, n)$ for each natural number $n$.

1. What is the maximum number of non-overlapping $2\times 1$ dominoes that can be placed on a $8\times 9$ checkerboard if six of them are placed as shown? Each domino must be placed horizontally or vertically so as to cover two adjacent squares of the board.
2. You are given a pair of triangles for which two sides of one triangle are equal in length to two sides of the second triangle, and the triangles are similar, but not necessarily congruent. Prove that the ratio of the sides that correspond under the similarity is a number between $\frac {1}{2}(\sqrt {5} - 1)$ and $\frac {1}{2}(\sqrt {5} + 1)$.
3. Suppose that $f$ is a real-valued function for which $f(xy)+f(y-x)\geq f(y+x)$ for all real numbers $x$ and $y$.
a) Give a nonconstant polynomial that satisfies the condition.
b) Prove that $f(x)\geq 0$ for all real $x$.
4. For two real numbers $a$, $b$, with $ab\neq 1$, define the $\ast$ operation by $a\ast b=\frac{a+b-2ab}{1-ab}.$ Start with a list of $n\geq 2$ real numbers whose entries $x$ all satisfy $0<x<1$. Select any two numbers $a$ and $b$ in the list; remove them and put the number $a\ast b$ at the end of the list, thereby reducing its length by one. Repeat this procedure until a single number remains. a) Prove that this single number is the same regardless of the choice of pair at each stage. b) Suppose that the condition on the numbers $x$ is weakened to $0<x\leq 1$. What happens if the list contains exactly one $1$?
5. Let the incircle of triangle $ABC$ touch sides $BC,\, CA$ and $AB$ at $D,\, E$ and $F,$ respectively. Let $\omega,\,\omega_{1},\,\omega_{2}$ and $\omega_{3}$ denote the circumcircles of triangle $ABC$, $AEF$, $BDF$ and $CDE$ respectively. Let $\omega$ and $\omega_{1}$ intersect at $A$ and $P,\,\omega$ and $\omega_{2}$ intersect at $B$ and $Q,\,\omega$ and $\omega_{3}$ intersect at $C$ and $R.$
a) Prove that $\omega_{1},\,\omega_{2}$ and $\omega_{3}$ intersect in a common point.
b) Show that $PD,\, QE$ and $RF$ are concurrent.

1. Let $f(n,k)$ be the number of ways of distributing $k$ candies to $n$ children so that each child receives at most $2$ candies. For example $f(3,7) = 0$, $f(3,6) = 1$, $f(3,4) = 6$. Determine the value of $$f(2006,1) + f(2006,4) + \ldots + f(2006,1000) + f(2006,1003) + \ldots + f(2006,4012).$$
2. Let $ABC$ be acute triangle. Inscribe a rectangle $DEFG$ in this triangle such that $D\in AB,E\in AC,F\in BC,G\in BC$. Describe the locus of (i.e., the curve occupied by) the intersections of the diagonals of all possible rectangles $DEFG$.
3. In a rectangular array of nonnegative reals with $m$ rows and $n$ columns, each row and each column contains at least one positive element. Moreover, if a row and a column intersect in a positive element, then the sums of their elements are the same. Prove that $m=n$.
4. Consider a round-robin tournament with $2n+1$ teams, where each team plays each other team exactly one. We say that three teams $X,Y$ and $Z$, form a cycle triplet if $X$ beats $Y$, $Y$ beats $Z$ and $Z$ beats $X$. There are no ties.
a) Determine the minimum number of cycle triplets possible.
b) Determine the maximum number of cycle triplets possible.
5. The vertices of a right triangle $ABC$ inscribed in a circle divide the circumference into three arcs. The right angle is at $A$, so that the opposite arc $BC$ is a semicircle while arc $BC$ and arc $AC$ are supplementary. To each of three arcs, we draw a tangent such that its point of tangency is the mid point of that portion of the tangent intercepted by the extended lines $AB,AC$. More precisely, the point $D$ on arc $BC$ is the midpoint of the segment joining the points $D'$ and $D''$ where tangent at $D$ intersects the extended lines $AB,AC$. Similarly for $E$ on arc $AC$ and $F$ on arc $AB$. Prove that triangle $DEF$ is equilateral.

1. An equilateral triangle of side length $n$ is divided into unit triangles. Let $f(n)$ be the number of paths from the triangle in the top row to the middle triangle in the bottom row, such that adjacent triangles in a path share a common edge and the path never travels up (from a lower row to a higher row) or revisits a triangle. An example is shown on the picture for $n = 5$. Determine the value of $f(2005)$.
2. Let $(a,b,c)$ be a Pythagorean triple, i.e. a triplet of positive integers with $a^2+b^2=c^2$.
a) Prove that $\left(\frac{c}{a}+\frac{c}{b}\right)^2>8$.
b) Prove that there are no integer $n$ and Pythagorean triple $(a,b,c)$ satisfying $\left(\frac{c}{a}+\frac{c}{b}\right)^2=n$.
3. Let $S$ be a set of $n\ge 3$ points in the interior of a circle.
a) Show that there are three distinct points $a,b,c\in S$ and three distinct points $A,B,C$ on the circle such that $a$ is (strictly) closer to $A$ than any other point in $S$, $b$ is closer to $B$ than any other point in $S$ and $c$ is closer to $C$ than any other point in $S$. b) Show that for no value of $n$ can four such points in $S$ (and corresponding points on the circle) be guaranteed.
4. Let $ABC$ be a triangle with circumradius $R$, perimeter $P$ and area $K$. Determine the maximum value of: $\frac{KP}{R^3}$.
5. Let's say that an ordered triple of positive integers $(a,b,c)$ is $n$-powerful if $a\le b\le c,\gcd (a,b,c)=1$ and $a^n+b^n+c^n$ is divisible by $a+b+c$. For example, $(1,2,2)$ is $5$-powerful.
a) Determine all ordered triples (if any) which are $n$-powerful for all $n\ge 1$.
b) Determine all ordered triples (if any) which are $2004$-powerful and $2005$-powerful, but not $2007$-powerful.

1. Find all ordered triples $(x,y,z)$ of real numbers which satisfy the following system of equations $\left\{\begin{array}{rcl} xy & = & z - x - y \\ xz & = & y - x - z \\ yz & = & x - y - z \end{array} \right.$
2. How many ways can $8$ mutually non-attacking rooks be placed on the $9\times9$ chessboard (shown here) so that all $8$ rooks are on squares of the same color?. (Two rooks are said to be attacking each other if they are placed in the same row or column of the board.)
3. Let $A,B,C,D$ be four points on a circle (occurring in clockwise order), with $AB<AD$ and $BC>CD$. The bisectors of angles $BAD$ and $BCD$ meet the circle at $X$ and $Y$, respectively. Consider the hexagon formed by these six points on the circle. If four of the six sides of the hexagon have equal length, prove that $BD$ must be a diameter of the circle.
4. Let $p$ be an odd prime. Prove that $\displaystyle\sum_{k=1}^{p-1}k^{2p-1} \equiv \frac{p(p+1)}{2} \pmod{p^2}$
5. Let $T$ be the set of all positive integer divisors of $2004^{100}$. What is the largest possible number of elements of a subset $S$ of $T$ such that no element in $S$ divides any other element in $S$?