Practice (TheColoringMethod)

back to index  |  new

Let $m_1, m_2, \ldots, m_n$ be a collection of $n$ positive integers, not necessarily distinct. For any sequence of integers $A = (a_1, \ldots, a_n)$ and any permutation $w = w_1, \ldots, w_n$ of $m_1, \ldots, m_n$, define an $A$-inversion of $w$ to be a pair of entries $w_i, w_j$ with $i < j$ for which one of the following conditions holds: $a_i \ge w_i > w_j$ $w_j > a_i \ge w_i$, or $w_i > w_j > a_i$. Show that, for any two sequences of integers $A = (a_1, \ldots, a_n)$ and $B = (b_1, \ldots, b_n)$, and for any positive integer $k$, the number of permutations of $m_1, \ldots, m_n$ having exactly $k$ $A$-inversions is equal to the number of permutations of $m_1, \ldots, m_n$ having exactly $k$ $B$-inversions.

Let $ABC$ be a scalene triangle with circumcircle $\Omega$ and incenter $I$. Ray $AI$ meets $\overline{BC}$ at $D$ and meets $\Omega$ again at $M$; the circle with diameter $\overline{DM}$ cuts $\Omega$ again at $K$. Lines $MK$ and $BC$ meet at $S$, and $N$ is the midpoint of $\overline{IS}$. The circumcircles of $\triangle KID$ and $\triangle MAN$ intersect at points $L_1$ and $L_2$. Prove that $\Omega$ passes through the midpoint of either $\overline{IL_1}$ or $\overline{IL_2}$.

Let $P_1$, $P_2$, $\dots$, $P_{2n}$ be $2n$ distinct points on the unit circle $x^2+y^2=1$, other than $(1,0)$. Each point is colored either red or blue, with exactly $n$ red points and $n$ blue points. Let $R_1$, $R_2$, $\dots$, $R_n$ be any ordering of the red points. Let $B_1$ be the nearest blue point to $R_1$ traveling counterclockwise around the circle starting from $R_1$. Then let $B_2$ be the nearest of the remaining blue points to $R_2$ travelling counterclockwise around the circle from $R_2$, and so on, until we have labeled all of the blue points $B_1, \dots, B_n$. Show that the number of counterclockwise arcs of the form $R_i \to B_i$ that contain the point $(1,0)$ is independent of the way we chose the ordering $R_1, \dots, R_n$ of the red points.

Let $\mathbf{Z}$ denote the set of all integers. Find all real numbers $c > 0$ such that there exists a labeling of the lattice points $( x, y ) \in \mathbf{Z}^2$ with positive integers for which: only finitely many distinct labels occur, and for each label $i$, the distance between any two points labeled $i$ is at least $c^i$.

Find the minimum possible value of \[\frac{a}{b^3+4}+\frac{b}{c^3+4}+\frac{c}{d^3+4}+\frac{d}{a^3+4}\]given that $a$, $b$, $c$, $d$ are nonnegative real numbers such that $a+b+c+d=4$.

Prove that there are infinitely many distinct pairs $(a,b)$ of relatively prime positive integers $a > 1$ and $b > 1$ such that $(a^b + b^a)$ is divisible by $(a + b)$.

Consider the equation \[\left(3x^3 + xy^2 \right) \left(x^2y + 3y^3 \right) = (x-y)^7.\] (a) Prove that there are infinitely many pairs $(x,y)$ of positive integers satisfying the equation. (b) Describe all pairs $(x,y)$ of positive integers satisfying the equation.

Let $ABC$ be an equilateral triangle and let $P$ be a point on its circumcircle. Let lines $PA$ and $BC$ intersect at $D$; let lines $PB$ and $CA$ intersect at $E$; and let lines $PC$ and $AB$ intersect at $F$. Prove that the area of triangle $DEF$ is twice the area of triangle $ABC$.

Are there any triples $(a,b,c)$ of positive integers such that $(a-2)(b-2)(c-2) + 12$ is prime that properly divides the number $a^2 + b^2 + c^2 + abc - 2017$?

Let $O$ and $H$ be the circumcenter and the orthocenter of an acute triangle $ABC$. Points $M$ and $D$ lie on side $BC$ such that $BM = CM$ and $\angle BAD = \angle CAD$. Ray $MO$ intersects the circumcircle of triangle $BHC$ in point $N$. Prove that $\angle ADO = \angle HAN$.

Let $P_1, \ldots, P_{2n}$ be $2n$ distinct points on the unit circle $x^2 + y^2 = 1$ other than $(1,0)$. Each point is colored either red or blue, with exactly $n$ of them red and exactly $n$ of them blue. Let $R_1, \ldots, R_n$ be any ordering of the red points. Let $B_1$ be the nearest blue point to $R_1$ traveling counterclockwise around the circle starting from $R_1$. Then let $B_2$ be the nearest of the remaining blue points to $R_2$ traveling counterclockwise around the circle from $R_2$, and so on, until we have labeled all the blue points $B_1, \ldots, B_n$. Show that the number of counterclockwise arcs of the form $R_i \rightarrow B_i$ that contain the point $(1,0)$ is independent of the way we chose the ordering $R_1, \ldots, R_n$ of the red points.

Let $f(x)=x^3 -x^2 -13x+24$. Find three pairs of $(x,y)$ such that if $y=f(x)$, then $x=f(y)$.

Each point of a circle is colored either red or blue. (a) Prove that there always exists an isosceles triangle inscribed in this circle such that all its vertices are colored the same. (b) Does there always exist an equilateral triangle inscribed in this circle such that all its vertices are colored the same?

The function $f$ satisfies $f(0)=0$, $f(1)=1$, and $f(\frac{x+y}{2})=\frac{f(x)+f(y)}{2}$ for all $x,y\in\mathbb{R}$. Show that $f(x)=x$ for all rational numbers $x$.

Let $f$ be a function such that $$ \sqrt {x - \sqrt { x + f(x) } } = f(x) , $$for $x > 1$. In that domain, $f(x)$ has the form $\frac{a+\sqrt{cx+d}}{b},$ where $a,b,c,d$ are integers and $a,b$ are relatively prime. Find $a+b+c+d.$

Find the number of possible arrangements in Fisher Random Chess. The diagram below is one possible arrangement.

In a legal arrangement, the White's position must satisfy the following criteria:

  • Eight pawns must be in the $2^{nd}$ row. (The same as regular chess)
  • Two bishops must be in opposite colored squares (e.g. $b1$ and $e1$ in the above diagram)
  •  King must locate between two rooks (e.g. in the diagram above, King is at $c1$ and two rooks are at $a1$ and $g1$)

The Black's position will be mirroring to the White's.


For what real values of $x$ is \[ \sqrt{x+\sqrt{2x-1}}+\sqrt{x-\sqrt{2x-1}}=A \] given a) $A=\sqrt{2}$; b) $A=1$; c) $A=2$, where only non-negative real numbers are admitted for square roots?

Determine all three-digit numbers $N$ having the property that $N$ is divisible by 11, and $\dfrac{N}{11}$ is equal to the sum of the squares of the digits of $N$.

Numbers $1,2,\cdots, 1974$ are written on a board. You are allowed to replace any two of these numbers by one number which is either the sum or the difference of these numbers. Show that after $1973$ times performing this operation, the only number left on the board cannot be $0$.


On an $8\times 8$ chess board, there are $32$ white pieces and $32$ black pieces, one piece in each square. If a player can change all the white pieces to black and all the black pieces to white in any row or column in a single move, then is it possible that after finitely many movies, there will be exactly one black piece left on the board?


Four $x$'s and five $o$'s are written around the circle in an arbitrary order. If two consecutive symbols are the same, then a new $x$ is inserted in between. Otherwise, a new $o$ is inserted. After nine new symbols are inserted, the previous 9 old ones are erased. Is it possible to get nine $o$'s after having repeated this operation for a finite time?

There are three piles which contain $8$, $9$, and $19$ stones, respectively. You are allowed to choose two piles and transfer one stone from each of them to the third pile. Is it possible to make all piles all contain exactly $12$ stones after several such operations?

Let the lengths of five line segments be $a_1$, $a_2$, $a_3$, $a_4$, and $a_5$, respectively, where $a_1 \ge a_2\ge a_3\ge a_4\ge a_5$. If any three of these five line segments can form a triangle, then prove at least one of such triangle is acute.

Given $n > 2$ points on a plane. Prove if any straight line passing two of these points, it must pass another one among these points, then all these $n$ points must be collinear.


If all sides of a convex pentagon $ABCDE$ are equal in length and $\angle{A}\ge\angle{B}\ge\angle{C}\ge\angle{D}\ge\angle{E}$, show that $ABCDE$ is a regular pentagon.