Difference between revisions of "2006 USAMO Problems"

Revision as of 20:31, 4 July 2006

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$

@@ Line 7: / Line 7: @@
 if and only if '''<math>s</math>''' is not a divisor of '''<math>p-1</math>.'''
-Note: For <math>x</math> a real number, let <math>\lfloor x \rfloor</math> denote the greatest integer less than or equal to <math>x</math>, and let <math>\{x\} = x - \lfloor x \rfloor</math> denote the fractional part of x
+Note: For <math>x</math> a real number, let <math>\lfloor x \rfloor</math> denote the greatest integer less than or equal to <math>x</math>, and let <math>\{x\} = x - \lfloor x \rfloor</math> denote the fractional part of x.
+[[2006 USAMO Problem 1|Solution]]
+=== Problem 2 ===
+For a given positive integer '''k''' find, in terms of '''k''', the minimum value of <math>N</math> for which there is a set of <math>2k+1</math> distinct positive integers that has sum greater than <math>N</math> but every subset of size '''k''' has sum at most <math>\frac{N}{2}</math>.
+[[2006 USAMO Problem 2|Solution]]
+=== Problem 3 ===
+For integral <math>m</math>, let <math>p(m)</math> be the greatest prime divisor of <math>m</math>. By convention, we set <math>p(\pm 1)=1</math> and <math>p(0)=\infty</math>. Find all polynomial <math>f</math> with integer coefficients such that the sequence
+<math>(p(f(n^2))-2n)_{n\ge 0}</math>
+is bounded above. (In particular, this requires <math>f(n^2)\neq 0</math> for <math>n\ge 0</math>

Page

Toolbox

Search