Practice (TheColoringMethod)

back to index  |  new

Determine (with proof) whether there is a subset $X$ of the integers with the following property: for any integer $n$ there is exactly one solution of $a + 2b = n$ with $a,b \in X$.

Let $p_1, p_2, p_3, \ldots$ be the prime numbers listed in increasing order, and let $x_0$ be a real number between 0 and 1. For positive integer $k$, define \[ x_k = \begin{cases} 0 & \mbox{if} \; x_{k-1} = 0, \\[.1in] {\displaystyle \left\{ \frac{p_k}{x_{k-1}} \right\}} & \mbox{if} \; x_{k-1} \neq 0, \end{cases} \] where $\{x\}$ denotes the fractional part of $x$. (The fractional part of $x$ is given by $x - \lfloor x \rfloor$ where $\lfloor x \rfloor$ is the greatest integer less than or equal to $x$.) Find, with proof, all $x_0$ satisfying $0 < x_0 < 1$ for which the sequence $x_0, x_1, x_2, \ldots$ eventually becomes 0.

Let $ABC$ be a triangle. Take points $D$, $E$, $F$ on the perpendicular bisectors of $BC$, $CA$, $AB$ respectively. Show that the lines through $A$, $B$, $C$ perpendicular to $EF$, $FD$, $DE$ respectively are concurrent.

Prove that for any integer $n$, there exists a unique polynomial $Q$ with coefficients in $\{0,1,\ldots,9\}$ such that $Q(-2) = Q(-5) = n$.

To clip a convex $n$-gon means to choose a pair of consecutive sides $AB, BC$ and to replace them by the three segments $AM, MN$, and $NC$, where $M$ is the midpoint of $AB$ and $N$ is the midpoint of $BC$. In other words, one cuts off the triangle $MBN$ to obtain a convex $(n+1)$-gon. A regular hexagon ${\cal P}_6$ of area 1 is clipped to obtain a heptagon ${\cal P}_7$. Then ${\cal P}_7$ is clipped (in one of the seven possible ways) to obtain an octagon ${\cal P}_8$, and so on. Prove that no matter how the clippings are done, the area of ${\cal P}_n$ is greater than $\frac 13$, for all $n \geq 6$.

Prove that, for all positive real numbers $ a$, $ b$, $ c$, the inequality \[ \frac {1}{a^3 + b^3 + abc} + \frac {1}{b^3 + c^3 + abc} + \frac {1}{c^3 + a^3 + abc} \leq \frac {1}{abc} \] holds.

Suppose the sequence of nonnegative integers $a_1, a_2, \ldots, a_{1997}$ satisfies \[ a_i + a_j \leq a_{i+j} \leq a_i + a_j + 1 \] for all $i,j \geq 1$ with $i + j \leq 1997$. Show that there exists a real number $x$ such that $a_n = \lfloor nx \rfloor$ (the greatest integer $\leq nx$) for all $1 \leq n \leq 1997$. MithsApprentice view topic

Suppose that the set $\{1,2,\cdots, 1998\}$ has been partitioned into disjoint pairs $\{a_i,b_i\}$ ($1\leq i\leq 999$) so that for all $i$, $|a_i-b_i|$ equals $1$ or $6$. Prove that the sum \[ |a_1-b_1|+|a_2-b_2|+\cdots +|a_{999}-b_{999}| \] ends in the digit $9$.

Let ${\cal C}_1$ and ${\cal C}_2$ be concentric circles, with ${\cal C}_2$ in the interior of ${\cal C}_1$. From a point $A$ on ${\cal C}_1$ one draws the tangent $AB$ to ${\cal C}_2$ ($B\in {\cal C}_2$). Let $C$ be the second point of intersection of $AB$ and ${\cal C}_1$, and let $D$ be the midpoint of $AB$. A line passing through $A$ intersects ${\cal C}_2$ at $E$ and $F$ in such a way that the perpendicular bisectors of $DE$ and $CF$ intersect at a point $M$ on $AB$. Find, with proof, the ratio $AM/MC$.

Let $a_0,a_1,\cdots ,a_n$ be numbers from the interval $(0,\pi/2)$ such that \[ \tan (a_0-\frac{\pi}{4})+ \tan (a_1-\frac{\pi}{4})+\cdots +\tan (a_n-\frac{\pi}{4})\geq n-1. \] Prove that \[ \tan a_0\tan a_1 \cdots \tan a_n\geq n^{n+1}. \]

A computer screen shows a $98 \times 98$ chessboard, colored in the usual way. One can select with a mouse any rectangle with sides on the lines of the chessboard and click the mouse button: as a result, the colors in the selected rectangle switch (black becomes white, white becomes black). Find, with proof, the minimum number of mouse clicks needed to make the chessboard all one color.

Prove that for each $n\geq 2$, there is a set $S$ of $n$ integers such that $(a-b)^2$ divides $ab$ for every distinct $a,b\in S$.

Let $n \geq 5$ be an integer. Find the largest integer $k$ (as a function of $n$) such that there exists a convex $n$-gon $A_{1}A_{2}\dots A_{n}$ for which exactly $k$ of the quadrilaterals $A_{i}A_{i+1}A_{i+2}A_{i+3}$ have an inscribed circle. (Here $A_{n+j} = A_{j}$.)

Some checkers placed on an $n \times n$ checkerboard satisfy the following conditions: (a) every square that does not contain a checker shares a side with one that does; (b) given any pair of squares that contain checkers, there is a sequence of squares containing checkers, starting and ending with the given squares, such that every two consecutive squares of the sequence share a side. Prove that at least $(n^{2}-2)/3$ checkers have been placed on the board.

Let $ABCD$ be a cyclic quadrilateral. Prove that \[ |AB - CD| + |AD - BC| \geq 2|AC - BD|. \]

Let $p > 2$ be a prime and let $a,b,c,d$ be integers not divisible by $p$, such that \[ \left\{ \dfrac{ra}{p} \right\} + \left\{ \dfrac{rb}{p} \right\} + \left\{ \dfrac{rc}{p} \right\} + \left\{ \dfrac{rd}{p} \right\} = 2 \] for any integer $r$ not divisible by $p$. Prove that at least two of the numbers $a+b$, $a+c$, $a+d$, $b+c$, $b+d$, $c+d$ are divisible by $p$. (Note: $\{x\} = x - \lfloor x \rfloor$ denotes the fractional part of $x$.)

Let $a_{1}, a_{2}, \dots, a_{n}$ ($n > 3$) be real numbers such that \[ a_{1} + a_{2} + \cdots + a_{n} \geq n \qquad \mbox{and} \qquad a_{1}^{2} + a_{2}^{2} + \cdots + a_{n}^{2} \geq n^{2}. \] Prove that $\max(a_{1}, a_{2}, \dots, a_{n}) \geq 2$.

The Y2K Game is played on a $1 \times 2000$ grid as follows. Two players in turn write either an S or an O in an empty square. The first player who produces three consecutive boxes that spell SOS wins. If all boxes are filled without producing SOS then the game is a draw. Prove that the second player has a winning strategy.

Let $ABCD$ be an isosceles trapezoid with $AB \parallel CD$. The inscribed circle $\omega$ of triangle $BCD$ meets $CD$ at $E$. Let $F$ be a point on the (internal) angle bisector of $\angle DAC$ such that $EF \perp CD$. Let the circumscribed circle of triangle $ACF$ meet line $CD$ at $C$ and $G$. Prove that the triangle $AFG$ is isosceles.

Call a real-valued function $ f$ very convex if \[ \frac {f(x) + f(y)}{2} \ge f\left(\frac {x + y}{2}\right) + |x - y| \] holds for all real numbers $ x$ and $ y$. Prove that no very convex function exists.

Let $S$ be the set of all triangles $ABC$ for which \[ 5 \left( \dfrac{1}{AP} + \dfrac{1}{BQ} + \dfrac{1}{CR} \right) - \dfrac{3}{\min\{ AP, BQ, CR \}} = \dfrac{6}{r}, \] where $r$ is the inradius and $P, Q, R$ are the points of tangency of the incircle with sides $AB, BC, CA,$ respectively. Prove that all triangles in $S$ are isosceles and similar to one another.

A game of solitaire is played with $R$ red cards, $W$ white cards, and $B$ blue cards. A player plays all the cards one at a time. With each play he accumulates a penalty. If he plays a blue card, then he is charged a penalty which is the number of white cards still in his hand. If he plays a white card, then he is charged a penalty which is twice the number of red cards still in his hand. If he plays a red card, then he is charged a penalty which is three times the number of blue cards still in his hand. Find, as a function of $R, W,$ and $B,$ the minimal total penalty a player can amass and all the ways in which this minimum can be achieved.

Find the smallest positive integer $n$ such that if $n$ squares of a $1000 \times 1000$ chessboard are colored, then there will exist three colored squares whose centers form a right triangle with sides parallel to the edges of the board.

Let $A_1A_2A_3$ be a triangle and let $\omega_1$ be a circle in its plane passing through $A_1$ and $A_2.$ Suppose there exist circles $\omega_2, \omega_3, \dots, \omega_7$ such that for $k = 2, 3, \dots, 7,$ $\omega_k$ is externally tangent to $\omega_{k-1}$ and passes through $A_k$ and $A_{k+1},$ where $A_{n+3} = A_{n}$ for all $n \ge 1$. Prove that $\omega_7 = \omega_1.$

Let $a_1, b_1, a_2, b_2, \dots , a_n, b_n$ be nonnegative real numbers. Prove that