Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2006 USAMO Problems"

(→‎Problem 3)
(→‎Problem 2)
Line 29: Line 29:
 
[[2006 USAMO Problems/Problem 4|Solution]]
 
[[2006 USAMO Problems/Problem 4|Solution]]
 
=== Problem 2 ===
 
=== Problem 2 ===
−
A mathematical frog jumps along the number line. The frog starts at <math>1</math>, and jumps according to the following rule: if the frog is at integer <math>n</math>, then it can jump either to <math>n+1</math> or to <math>n+2^{m_n+1}</math> where <math>2^{m_n}</math> is the largest power of <math>2</math> that is a factor of <math>n</math>. Show that if <math>k/ge 2</math> is a positive integer and <math>i</math> is a nonnegative integer, then the minimum number of jumps needed to reach <math>2^ik</math> is greater than the minimum number of jumps needed to reach <math> 2^i.</math>
+
A mathematical frog jumps along the number line. The frog starts at <math>1</math>, and jumps according to the following rule: if the frog is at integer <math>n</math>, then it can jump either to <math>n+1</math> or to <math>n+2^{m_n+1}</math> where <math>2^{m_n}</math> is the largest power of <math>2</math> that is a factor of <math>n</math>. Show that if <math>k\ge 2</math> is a positive integer and <math>i</math> is a nonnegative integer, then the minimum number of jumps needed to reach <math>2^ik</math> is greater than the minimum number of jumps needed to reach <math> 2^i.</math>
  
 
[[2006 USAMO Problems/Problem 5|Solution]]
 
[[2006 USAMO Problems/Problem 5|Solution]]

Revision as of 11:08, 12 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$)

Solution

Day 2

Problem 1

Find all positive integers $n$ such that there are $k\ge 2$ positive rational numbers $a_1,a_2,\ldots a_k$ satisfying $a_1+a_2+...+a_k=a_1\cdot a_2\cdots a_k=n.$

Solution

Problem 2

A mathematical frog jumps along the number line. The frog starts at $1$, and jumps according to the following rule: if the frog is at integer $n$, then it can jump either to $n+1$ or to $n+2^{m_n+1}$ where $2^{m_n}$ is the largest power of $2$ that is a factor of $n$. Show that if $k\ge 2$ is a positive integer and $i$ is a nonnegative integer, then the minimum number of jumps needed to reach $2^ik$ is greater than the minimum number of jumps needed to reach $2^i.$

Solution

Problem 3

Let $ABCD$ be a quadrilateral, and let $E$ and $F$ be points on sides $AD$ and $BC$ respectively, such that $\frac{AE}{ED}=\frac{BF}{FC}.$ Ray $FE$ meets rays $BA$ and $CD$ at $S$ and $T$ respectively. Prove that the circumcircles of triangles $SAE, SBF, TCF,$ and $TDE$ pass through a common point.

Solution

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2006_USAMO_Problems&oldid=7451"