# [Shortlists & Solutions] Easy Little Math Olympiad 2010

### Algebra

1. Determine all strictly increasing functions $f: \mathbb{N}\to\mathbb{N}$ satisfying $$nf(f(n))=f(n)^2$$ for all positive integers $n$.
2. Let $a,b,c$ be positive reals. Prove that $\frac{(a-b)(a-c)}{2a^2 + (b+c)^2} + \frac{(b-c)(b-a)}{2b^2 + (c+a)^2} + \frac{(c-a)(c-b)}{2c^2 + (a+b)^2} \geq 0.$
3. Find all functions $f: \mathbb{R} \to \mathbb{R}$ such that $$f(x+y) = \max(f(x),y) + \min(f(y),x).$$
4. Let $-2 < x_1 < 2$ be a real number and define $x_2, x_3, \ldots$ by $x_{n+1} = x_n^2-2$ for $n \geq 1$. Assume that no $x_n$ is $0$ and define a number $A$, $0 \leq A \leq 1$ in the following way: The $n^{\text{th}}$ digit after the decimal point in the binary representation of $A$ is a $0$ if $x_1x_2\cdots x_n$ is positive and $1$ otherwise. Prove that $$A = \frac{1}{\pi}\cos^{-1}\left(\frac{x_1}{2}\right).$$
5. Given a prime $p$, let $d(a,b)$ be the number of integers $c$ such that $1 \leq c < p$, and the remainders when $ac$ and $bc$ are divided by $p$ are both at most $\frac{p}{3}$. Determine the maximum value of $\sqrt{\sum_{a=1}^{p-1}\sum_{b=1}^{p-1}d(a,b)(x_a + 1)(x_b + 1)} - \sqrt{\sum_{a=1}^{p-1}\sum_{b=1}^{p-1}d(a,b)x_ax_b}$ over all $(p-1)$-tuples $(x_1,x_2,\ldots,x_{p-1})$ of real numbers.
6. For all positive real numbers $a,b,c$, prove that $\sqrt{\frac{a^4 + 2b^2c^2}{a^2+2bc}} + \sqrt{\frac{b^4+2c^2a^2}{b^2+2ca}} + \sqrt{\frac{c^4 + 2a^2b^2}{c^2 + 2ab}} \geq a + b + c.$
7. Find the smallest real number $M$ with the following property: Given nine nonnegative real numbers with sum $1$, it is possible to arrange them in the cells of a $3 \times 3$ square so that the product of each row or column is at most $M$.

### Combinatorics

1. For a permutation $\pi$ of $\{1,2,3,\ldots,n\}$, let $\text{Inv}(\pi)$ be the number of pairs $(i,j)$ with $1 \leq i < j \leq n$ and $\pi(i) > \pi(j)$.
a) Given $n$, what is $\sum \text{Inv}(\pi)$ where the sum ranges over all permutations $\pi$ of $\{1,2,3,\ldots,n\}$?.
b) Given $n$, what is $\sum \left(\text{Inv}(\pi)\right)^2$ where the sum ranges over all permutations $\pi$ of $\{1,2,3,\ldots,n\}$?
2. For a positive integer $n$, let $s(n)$ be the number of ways that $n$ can be written as the sum of strictly increasing perfect $2010^{\text{th}}$ powers. For instance, $s(2) = 0$ and $s(1^{2010} + 2^{2010}) = 1$. Show that for every real number $x$, there exists an integer $N$ such that for all $n > N$, $\frac{\max_{1 \leq i \leq n} s(i)}{n} > x.$
3. $2010$ MOPpers are assigned numbers $1$ through $2010$. Each one is given a red slip and a blue slip of paper. Two positive integers, $A$ and $B$, each less than or equal to $2010$ are chosen. On the red slip of paper, each MOPper writes the remainder when the product of $A$ and his or her number is divided by $2011$. On the blue slip of paper, he or she writes the remainder when the product of $B$ and his or her number is divided by $2011$. The MOPpers may then perform either of the following two operations
• Each MOPper gives his or her red slip to the MOPper whose number is written on his or her blue slip.
• Each MOPper gives his or her blue slip to the MOPper whose number is written on his or her red slip.
• Show that it is always possible to perform some number of these operations such that each MOPper is holding a red slip with his or her number written on it.
4. The numbers $1, 2, \ldots, n$ are written on a blackboard. Each minute, a student goes up to the board, chooses two numbers $x$ and $y$, erases them, and writes the number $2x+2y$ on the board. This continues until only one number remains. Prove that this number is at least $\frac{4}{9}n^3$.
5. Let $n > 1$ be a positive integer. A 2-dimensional grid, infinite in all directions, is given. Each 1 by 1 square in a given $n$ by $n$ square has a counter on it. A move consists of taking $n$ adjacent counters in a row or column and sliding them each by one space along that row or column. A returning sequence is a finite sequence of moves such that all counters again fill the original $n$ by $n$ square at the end of the sequence.
a) Assume that all counters are distinguishable except two, which are indistinguishable from each other. Prove that any distinguishable arrangement of counters in the $n$ by $n$ square can be reached by a returning sequence.
b) Assume all counters are distinguishable. Prove that there is no returning sequence that switches two counters and returns the rest to their original positions.
6. Hamster is playing a game on an $m \times n$ chessboard. He places a rook anywhere on the board and then moves it around with the restriction that every vertical move must be followed by a horizontal move and every horizontal move must be followed by a vertical move. For what values of $m,n$ is it possible for the rook to visit every square of the chessboard exactly once? A square is only considered visited if the rook was initially placed there or if it ended one of its moves on it.
7. The game of circulate is played with a deck of $kn$ cards each with a number in $1,2,\ldots,n$ such that there are $k$ cards with each number. First, $n$ piles numbered $1,2,\ldots,n$ of $k$ cards each are dealt out face down. The player then flips over a card from pile $1$, places that card face up at the bottom of the pile, then next flips over a card from the pile whose number matches the number on the card just flipped. The player repeats this until he reaches a pile in which every card has already been flipped and wins if at that point every card has been flipped. Hamster has grown tired of losing every time, so he decides to cheat. He looks at the piles beforehand and rearranges the $k$ cards in each pile as he pleases. When can Hamster perform this procedure such that he will win the game?
8. A tree $T$ is given. Starting with the complete graph on $n$ vertices, subgraphs isomorphic to $T$ are erased at random until no such subgraph remains. For what trees does there exist a positive constant $c$ such that the expected number of edges remaining is at least $cn^2$ for all positive integers $n$?.

### Geometry

1. Let $ABC$ be a triangle. Let $A_1$, $A_2$ be points on $AB$ and $AC$ respectively such that $A_1A_2 \parallel BC$ and the circumcircle of $\triangle AA_1A_2$ is tangent to $BC$ at $A_3$. Define $B_3$, $C_3$ similarly. Prove that $AA_3$, $BB_3$, and $CC_3$ are concurrent.
2. Given a triangle $ABC$, a point $P$ is chosen on side $BC$. Points $M$ and $N$ lie on sides $AB$ and $AC$, respectively, such that $MP \parallel AC$ and $NP \parallel AB$. Point $P$ is reflected across $MN$ to point $Q$. Show that triangle $QMB$ is similar to triangle $CNQ$.
3. A circle $\omega$ not passing through any vertex of $\triangle ABC$ intersects each of the segments $AB$, $BC$, $CA$ in 2 distinct points. Prove that the incenter of $\triangle ABC$ lies inside $\omega$.
4. Let $ABC$ be a triangle with circumcircle $\omega$, incenter $I$, and $A$-excenter $I_A$. Let the incircle and the $A$-excircle hit $BC$ at $D$ and $E$, respectively, and let $M$ be the midpoint of arc $BC$ without $A$. Consider the circle tangent to $BC$ at $D$ and arc $BAC$ at $T$. If $TI$ intersects $\omega$ again at $S$, prove that $SI_A$ and $ME$ meet on $\omega$.
5. Determine all (not necessarily finite) sets $S$ of points in the plane such that given any four distinct points in $S$, there is a circle passing through all four or a line passing through some three.
6. Let $ABC$ be a triangle with circumcircle $\Omega$. $X$ and $Y$ are points on $\Omega$ such that $XY$ meets $AB$ and $AC$ at $D$ and $E$, respectively. Show that the midpoints of $XY$, $BE$, $CD$, and $DE$ are concyclic.

### Number Theory

1. For a positive integer $n$, let $\mu(n) = 0$ if $n$ is not squarefree and $(-1)^k$ if $n$ is a product of $k$ primes, and let $\sigma(n)$ be the sum of the divisors of $n$. Prove that for all $n$ we have $\left|\sum_{d|n}\frac{\mu(d)\sigma(d)}{d}\right| \geq \frac{1}{n},$ and determine when equality holds.
2. Given a prime $p$, show that $\left(1+p\sum_{k=1}^{p-1}k^{-1}\right)^2 \equiv 1-p^2\sum_{k=1}^{p-1}k^{-2} \pmod{p^4}.$
3. Prove that there are infinitely many quadruples of integers $(a,b,c,d)$ such that \begin{align*} a^2 + b^2 + 3 &= 4ab\\ c^2 + d^2 + 3 &= 4cd\\ 4c^3 - 3c &= a \end{align*}
4. Let $r$ and $s$ be positive integers. Define $a_0 = 0$, $a_1 = 1$, and $a_n = ra_{n-1} + sa_{n-2}$ for $n \geq 2$. Let $f_n = a_1a_2\cdots a_n$. Prove that $\displaystyle\frac{f_n}{f_kf_{n-k}}$ is an integer for all integers $n$ and $k$ such that $0 < k < n$.
5. Find the set $S$ of primes such that $p \in S$ if and only if there exists an integer $x$ such that $x^{2010} + x^{2009} + \cdots + 1 \equiv p^{2010} \pmod{p^{2011}}$.
 MOlympiad.NET là dự án thu thập và phát hành các đề thi tuyển sinh và học sinh giỏi toán. Quý bạn đọc muốn giúp chúng tôi chỉnh sửa đề thi này, xin hãy để lại bình luận facebook (có thể đính kèm hình ảnh) hoặc google (có thể sử dụng $\LaTeX$) bên dưới. BBT rất mong bạn đọc ủng hộ UPLOAD đề thi và đáp án mới hoặc liên hệbbt.molympiad@gmail.comChúng tôi nhận tất cả các định dạng của tài liệu: $\TeX$, PDF, WORD, IMG,...