## Practice Test Problem 1 Determine all functions \( f: \mathbb{N} \to \mathbb{N} \) (where \( \mathbb{N} \) is the set of positive integers) such that \( f(4)=4 \) and \[ \frac{1}{f(1)f(2)} + \frac{1}{f(2)f(3)} + \cdots + \frac{1}{f(n)f(n+1)} = \frac{f(n)}{f(n+1)}.\] Observe that \( f(2) \neq 0 \), \( f(1)=1 \). Applying the last condition twice yields \[ \frac{f(n)}{f(n+1)} - \frac{f(n-1)}{f(n)} = \frac{1}{f(n)f(n+1)} \] and hence \[ f(n+1) = \frac{[f(n)]^2 - 1}{f(n-1)}. \] We can easily verify that \( f(k)=k \) for \( k \leq 4 \) and use induction to prove \( f(n)=n \). Indeed this function works so it is the only one. Problem 2 Given \( n \) biased coins \( C_1 \), \( C_2 \), \( \dots \), \( C_n \), assume that the probability of getting heads when \( C_k \) is tossed is equal to \( \frac1{2k+1} \) for each \( k \). Find the probability of getting an odd number of heads when all these \( n \) coins are tossed. Let \[ f(X)=\prod_{k=1}^n\left(1-\frac1{2k+1}+\frac1{2k+1}X\right).\] Assume that \( f(X)=a_0+a_1X+a_2X^2+\cdots+a_nX^n \) is the expansion of \( f \). Then \( a_k \) is the probability of getting exactly \( k \) heads when these \( n \) coins are tossed. The probability of getting an odd number of heads is equal to \[ a_1+a_3+\cdots=\frac{f(1)-f(-1)}2=\frac13\cdot\frac35\cdot\frac57\cdot \frac 79\cdots\frac{2n-1}{2n+1}=\frac1{2n+1}.\] Problem 3 Let \( N \) be the number of ordered pairs \( (x,y) \) of integers such that \[ x^2+xy+y^2\leq 2012.\] Prove that \( N \) is not divisible by \( 3 \). Let \( f(x,y)=x^2+xy+y^2 \). Notice that \( f(x,y)=f(-x-y,x) \). Let \[ S=\left\{(x,y)\in\mathbb Z^2: x^2+y^2+xy\leq 2012\right\}.\] Notice that \( S\setminus\{(0,0)\} \) can be written as a union of disjoint sets of the form \( \{(x,y),(-x-y,x), (y,-x-y)\} \). Therefore \( 3\mid\left|S\setminus \{(0,0)\}\right| \) hence \( N\equiv 1 \) (mod \( 3 \)). Problem 4 Assume that \( P(x)=ax^4+bx^3+cx^2+dx+e \) is a polynomial of degree four with integer coefficients that has two roots \( x_1 \) and \( x_2 \) such that \[ x_1+x_2\in\mathbb Q\setminus\left\{\frac{-b}{2a} \right\}.\] Prove that \( x_1x_2\in\mathbb Q \). Denote by \( x_1 \), \( x_2 \), \( x_3 \), and \( x_4 \) the roots (real or complex) of the polynomial. By Vieta’s formulas we know that \( x_1+x_2+x_3+x_4\in\mathbb Q \) and \( x_1x_2+x_1x_3+x_1x_4+x_2x_3+x_2x_4+x_3x_4\in\mathbb Q \) hence \( x_3+x_4\in\mathbb Q \) and \[ x_1^2+x_2^2+x_3^2+x_4^2=(x_1+x_2+x_3+x_4)^2-2\left(x_1x_2+x_1x_3+x_1x_4+x_2x_3+x_2x_4+x_3x_4\right)\in\mathbb Q.\] Therefore \( (x_1+x_2)^2+(x_3+x_4)^2-\left(x_1^2+x_2^2+x_3^2+x_4^2\right)\in\mathbb Q \) hence \( x_1x_2+x_3x_4\in\mathbb Q \). Since \( x_1x_2x_3+x_1x_2x_4+x_1x_3x_4+x_2x_3x_4\in\mathbb Q \) we have that \[ (x_1x_2+x_3x_4)(x_1+x_2+x_3+x_4)-2\left(x_1x_2x_3+x_1x_2x_4+x_1x_3x_4+x_2x_3x_4 \right)\in\mathbb Q,\] which is equivalent to \[ (x_1x_2-x_3x_4)(x_1+x_2-x_3-x_4)\in\mathbb Q\] Using that \( x_1+x_2-x_3-x_4\in\mathbb Q\setminus \{0\} \) we conclude that \( x_1x_2-x_3x_4\in\mathbb Q \) which together with \( x_1x_2+x_3x_4\in\mathbb Q \) implies the required relation. Problem 5 Let \( s:\mathbb C\to\mathbb C \) be defined as \[ s(z)=\left\{\begin{array}{cc} z,& \mbox{ if Re }(z)\geq 0\\ -z,&\mbox{ if Re }(z)< 0.\end{array}\right.\] Given a complex number \( \gamma \), consider the sequence \( (z_n)_{n=1}^{\infty} \) defined by \[ z_1=\gamma\quad\quad\quad\mbox{ and }\quad\quad\quad z_{n+1}=s\left(z_n^2+z_n+1\right) \mbox{ for }n\geq 1.\] Determine all \( \gamma\in\mathbb C \) for which the sequence \( (z_n)_{n=1}^{\infty} \) is periodic. Let us define \( a_n=\mbox{Re }(z_n) \) and \( b_n=\mbox{Im }(z_n) \) to be real and imaginary parts of \( (z_n)_{n=1}^{\infty} \). Then we have \begin{eqnarray*} a_{n+1}&=&a_n^2+a_n+1-b_n^2\\ b_{n+1}&=&b_n\cdot(2a_n+1). \end{eqnarray*} Consider the function \( f:\mathbb R_0^+\times\mathbb R\to\mathbb R \) defined as \( f(a,b)=2a^2+b^2 \). Simple algebraic manipulations yield: \begin{eqnarray*} f(a_{n+1},b_{n+1})-f(a_n,b_n)&=& 2\left((a_n^2+a_n)+(1-b_n^2)\right)^2+4b_n^2\cdot (a_n^2+a_n)-2a_n^2 \\ &=&2\left( (a_n^2+a_n)^2+(b_n^2-1)^2+2(a_n^2+a_n)(1-b_n^2)+2b_n^2(a_n^2+a_n)-a_n^2\right)\\ &=&2\left( (a_n^2+a_n)^2+(b_n^2-1)^2+a_n\right)\geq0. \end{eqnarray*} The equality holds if and only if \( a_n=0 \) and \( b_n\in\{1,-1\} \). Assume that \( \gamma\in\{i,-i\} \). Then the sequence \( (z_n)_{n=1}^{\infty} \) is constant, hence periodic. If, however, \( \gamma\not\in\{i,-i\} \) we can first prove by induction that \( (a_n,b_n)\not\in\{(0,1),(0,-1)\} \) implies that \( (a_{n+1},b_{n+1})\not\in\{(0,1),(0,-1)\} \). (Indeed, if \( |b_n|> 1 \) then \( |b_{n+1}|=|b_n|\cdot( 2a_n+1)> 1 \), hence \( |b_n|=1 \). This implies that \( a_n^2+a_n=0 \) which is possible only for \( a_n=0 \).) Thus, the value \( f(a_n,b_n) \) is strictly increasing and the sequence \( (a_n,b_n)_{n=1}^{\infty} \) can’t be periodic. Problem 6 Numbers \( 1 \), \( 2 \), \( \dots \), \( 2013^2 \) are written in the cells of a \( 2013\times 2013 \) table. In each of the moves a player is allowed to perform one of the following transformations: Exchange places of any two rows, or any two columns; or reverse a row or a column. (When row or column is reversed, the first and the last entry exchange their positions, so do the second and second last, etc.) Is it possible that after finitely many moves arbitrary two numbers exchange their positions and no other number exchange its position? The answer is yes. It is enough to prove that we can swap numbers \( 1 \) and \( 2 \) in the first row. Denote by \( a \), \( b \), and \( c \) the middle three elements of the first row. We prove that using only column switching and row-reversing we can transform the middle three elements to \( bca \) and \( cab \). Then we prove that for any three elements in the first row we can do cyclic permutations. Denote by \( xyz \) the first three elements in the last row. We will prove that we can transform the table into the one in which \( a \) and \( b \) as well as \( x \) and \( y \) switch places. First we can reverse the first column to obtain the table in which in the first row we have \( xbc \) and in the last we have \( ayz \). Then we perform the operation on the first row to obtain \( bcx \), and then we reverse the first column again to get \( acx \) and \( byz \). We can transform the submatrix \( \left[\begin{array}{ccc} a&b&c\\ x&y&z\end{array}\right] \) to \( \left[\begin{array}{ccc} a&c&x\\ b&y&z\end{array}\right] \). This is as if we did a cyclic permutation on \( \{b,c,x\} \). Analogously we can transform \( \left[\begin{array}{ccc} a&b&c\\ x&y&z\end{array}\right] \) to \( \left[\begin{array}{ccc} y&b&c\\ x&z&a\end{array}\right] \). Applying this sequence of operations we get the following submatrices: \begin{eqnarray*}\left[\begin{array}{ccc} a&b&c\\ x&y&z\end{array}\right] &\mapsto& \left[\begin{array}{ccc} a&c&x\\ b&y&z\end{array}\right] \mapsto \left[\begin{array}{ccc} y&c&x\\ b&z&a\end{array}\right] \mapsto \left[\begin{array}{ccc} x&y&c\\ b&z&a\end{array}\right] \mapsto \left[\begin{array}{ccc} x&y&c\\ a&b&z\end{array}\right]. \end{eqnarray*} Well, we did something we didn’t want to but it is analogously good: We switched simultaneously \( x\leftrightarrow a \) and \( y\leftrightarrow b \). Of course, we could do \( a\leftrightarrow b \) and \( x\leftrightarrow y \) in the same way. This is the main ingredient of the proof. Now we do the following: We first do the flips in pairs: \( (a_{21}\leftrightarrow a_{22}, a_{31}\leftrightarrow a_{32}) \), \( \dots \), \( (a_{2012,1}\leftrightarrow a_{2012,2},a_{2013,1}\leftrightarrow a_{2013,2}) \). Then we change the places of the first and second column and we are done. |

2005-2018 IMOmath.com | imomath"at"gmail.com | Math rendered by MathJax Home | Olympiads | Book | Training | IMO Results | Forum | Links | About | Contact us |