2006 USAMO Problems

Day 1

Problem 1

Let $p$ be a prime number and let $s$ be an integer with $0 < s < p$ . Prove that there exists integers $m$ and $n$ with $0 < m < n < p$ and

{ $\frac{sm}{p}$ } < { $\frac{sn}{p}$ }< ${\frac{s}{p}}$

if and only if $s$ is not a divisor of $p-1$ .

Note: For $x$ a real number, let $\lfloor x \rfloor$ denote the greatest integer less than or equal to $x$ , and let $\{x\} = x - \lfloor x \rfloor$ denote the fractional part of x.

Solution

Problem 2

For a given positive integer k find, in terms of k, the minimum value of $N$ for which there is a set of $2k+1$ distinct positive integers that has sum greater than $N$ but every subset of size k has sum at most $\frac{N}{2}$ .

Solution

Problem 3

For integral $m$ , let $p(m)$ be the greatest prime divisor of $m$ . By convention, we set $p(\pm 1)=1$ and $p(0)=\infty$ . Find all polynomial $f$ with integer coefficients such that the sequence

$(p(f(n^2))-2n)_{n\ge 0}$

is bounded above. (In particular, this requires $f(n^2)\neq 0$ for $n\ge 0$

Page

Toolbox

Search

2006 USAMO Problems

Contents

Day 1

Problem 1

Problem 2

Problem 3