ELMO SL 2010

Determine all strictly increasing functions $f: \mathbb{N}\to\mathbb{N}$ satisfying $nf(f(n))=f(n)^2$ for all positive integers $n$ .

Carl Lian and Brian Hamrick.

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.$$

Calvin Deng.

Find all functions $f: \mathbb{R} \to \mathbb{R}$ such that $f(x+y) = \max(f(x),y) + \min(f(y),x)$.

George Xing.

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)$ .

Evan O' Dorney.

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.

Brian Hamrick.

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.$$

In-Sung Na.

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$ .

Evan O' Dorney.

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)$ . [list=1] [] Given $n$ , what is $\sum \text{Inv}(\pi)$ where the sum ranges over all permutations $\pi$ of $\{1,2,3,\ldots,n\}$ ? [] 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\}$ ?[/list]

Brian Hamrick.

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.$$

Alex Zhu.

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.

Brian Hamrick.

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$ .

Brian Hamrick.

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.

• 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.
• Assume all counters are distinguishable. Prove that there is no returning sequence that switches two counters and returns the rest to their original positions.

Mitchell Lee and Benjamin Gunby.

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.

Brian Hamrick.

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?

Brian Hamrick.

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$ ?

David Yang.

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.

Carl Lian.

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$ .

Brian Hamrick.

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$ .

Evan O' Dorney.

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$ .

Amol Aggarwal.

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.

Carl Lian.

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.

Carl Lian.

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.

Wenyu Cao.

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}.$$

Timothy Chu.

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*}

Travis Hance.

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 $\frac{f_n}{f_kf_{n-k}}$ is an integer for all integers $n$ and $k$ such that $0 < k < n$ .

Evan O' Dorney.

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}}$ .

Brian Hamrick.