Difference between revisions of "2006 USAMO Problems"

(Problem 2)
(Fixed strange LaTeX; standardized)
Line 1: Line 1:
 
== Day 1 ==
 
== Day 1 ==
 +
 
=== Problem 1 ===
 
=== Problem 1 ===
Let '''<math>p</math>''' be a prime number and let '''<math>s</math>''' be an integer with '''<math>0 < s < p</math>.''' Prove that there exists integers '''<math>m</math>''' and '''<math>n</math>''' with '''<math>0 < m < n < p</math>''' and
 
  
'''<center>{<math>\frac{sm}{p}</math>} < {<math>\frac{sn}{p}</math>}< <math>{\frac{s}{p}}</math></center>'''
+
Let <math>\displaystyle p</math> be a prime number and let <math>\displaystyle s</math> be an integer with <math> \displaystyle 0 < s < p </math>. Prove that there exist integers <math>\displaystyle m</math> and <math>\displaystyle n</math> with <math>\displaystyle 0 < m < n < p</math> and
 +
 
 +
<center>
 +
<math> \left\{ \frac{sm}{p} \right\} < \left\{ \frac{sn}{p} \right\} < \frac{s}{p} </math>
 +
</center>
 +
 
 +
if and only if <math>\displaystyle s </math> is not a divisor of <math>\displaystyle p-1 </math>.
  
if and only if '''<math>s</math>''' is not a divisor of '''<math>p-1</math>.'''
+
Note: For <math> \displaystyle 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 <math> \displaystyle x </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.
+
[[2006 USAMO Problems/Problem 1 | Solution]]
  
[[2006 USAMO Problems/Problem 1|Solution]]
 
 
=== Problem 2 ===
 
=== 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 Problems/Problem 2|Solution]]
+
For a given positive integer <math> \displaystyle k </math> find, in terms of <math> \displaystyle k </math>, the minimum value of <math> \displaystyle N </math> for which there is a set of <math> \displaystyle 2k+1 </math> distinct positive integers that has sum greater than <math> \displaystyle N </math> but every subset of size <math> \displaystyle k </math> has sum at most <math>\displaystyle N/2 </math>.
 +
 
 +
[[2006 USAMO Problems/Problem 2 | Solution]]
 +
 
 
=== Problem 3 ===
 
=== 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>
+
For integral <math>\displaystyle m </math>, let <math> \displaystyle p(m) </math> be the greatest prime divisor of <math> \displaystyle m </math>. By convention, we set <math> p(\pm 1)=1</math> and <math>p(0)=\infty</math>. Find all polynomials <math>\displaystyle 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>.)
 +
 
 +
[[2006 USAMO Problems/Problem 3 | Solution]]
 +
 
 +
== Day 2 ==
 +
 
 +
=== Problem 4 ===
 +
 
 +
Find all positive integers <math> \displaystyle n</math> such that there are <math>k\ge 2</math> positive rational numbers <math>a_1,a_2,\ldots a_k</math> satisfying <math>a_1+a_2+...+a_k = a_1 \cdot a_2 \cdot \cdots a_k = n</math>.
 +
 
 +
[[2006 USAMO Problems/Problem 4 | Solution]]
 +
 
 +
=== Problem 5 ===
  
is bounded above. (In particular, this requires <math>f(n^2)\neq 0</math> for <math>n\ge 0</math>)
+
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 <math> \displaystyle n </math>, then it can jump either to <math> \displaystyle n+1 </math> or to <math>n+2^{m_n+1}</math> where <math>2^{m_n}</math> is the largest power of 2 that is a factor of <math> \displaystyle n </math>. Show that if <math>k\ge 2</math> is a positive integer and <math> \displaystyle i </math> is a nonnegative integer, then the minimum number of jumps needed to reach <math> \displaystyle 2^i k </math> is greater than the minimum number of jumps needed to reach <math> \displaystyle 2^i </math>.
  
[[2006 USAMO Problems/Problem 3|Solution]]
+
[[2006 USAMO Problems/Problem 5 | Solution]]
  
== Day 2 ==
+
=== Problem 6 ===
=== Problem 1 ===
 
Find all positive integers <math>n</math> such that there are <math>k\ge 2</math> positive rational numbers <math>a_1,a_2,\ldots a_k</math> satisfying <math>a_1+a_2+...+a_k=a_1\cdot a_2\cdots a_k=n.</math>
 
  
[[2006 USAMO Problems/Problem 4|Solution]]
+
Let <math> \displaystyle ABCD </math> be a quadrilateral, and let <math> \displaystyle  E </math> and <math> \displaystyle F </math> be points on sides <math> \displaystyle AD </math> and <math> \displaystyle BC </math>, respectively, such that <math> \displaystyle AE/ED = BF/FC </math>.  Ray <math> \displaystyle FE </math> meets rays <math> \displaystyle BA </math> and <math> \displaystyle CD </math> at <math> \displaystyle S </math> and <math> \displaystyle T </math> respectively. Prove that the circumcircles of triangles  <math> \displaystyle SAE, SBF, TCF, </math> and <math> \displaystyle TDE </math> pass through a common point.
=== 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>
 
  
[[2006 USAMO Problems/Problem 5|Solution]]
+
[[2006 USAMO Problems/Problem 6 | Solution]]
  
=== Problem 3 ===
+
== Resources ==
Let <math>ABCD</math> be a quadrilateral, and let <math>E</math> and <math>F</math> be points on sides <math>AD</math> and <math>BC</math> respectively, such that <math>\frac{AE}{ED}=\frac{BF}{FC}.</math> Ray <math>FE</math> meets rays <math>BA</math> and <math>CD</math> at <math>S</math> and <math>T</math> respectively. Prove that the circumcircles of triangles  <math>SAE, SBF, TCF,</math> and <math>TDE</math> pass through a common point.
 
  
[[2006 USAMO Problems/Problem 6|Solution]]
+
* [[2006 USAMO]]
 +
* [http://www.artofproblemsolving.com/Forum/resources.php?c=182&cid=27&year=2006 USAMO 2006 Problems on the Resources Page]
 +
* [http://www.unl.edu/amc/e-exams/e8-usamo/e8-1-usamoarchive/2006-ua/2006usamoQ.pdf USAMO 2006 Questions Document]
 +
* [http://www.unl.edu/amc/e-exams/e8-usamo/e8-1-usamoarchive/2006-ua/2006usamoS.pdf USAMO 2006 Solutions Document]

Revision as of 21:05, 1 September 2006

Day 1

Problem 1

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

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

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

Note: For $\displaystyle 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 $\displaystyle x$.

Solution

Problem 2

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

Solution

Problem 3

For integral $\displaystyle m$, let $\displaystyle p(m)$ be the greatest prime divisor of $\displaystyle m$. By convention, we set $p(\pm 1)=1$ and $p(0)=\infty$. Find all polynomials $\displaystyle 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 4

Find all positive integers $\displaystyle 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 \cdot \cdots a_k = n$.

Solution

Problem 5

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 $\displaystyle n$, then it can jump either to $\displaystyle n+1$ or to $n+2^{m_n+1}$ where $2^{m_n}$ is the largest power of 2 that is a factor of $\displaystyle n$. Show that if $k\ge 2$ is a positive integer and $\displaystyle i$ is a nonnegative integer, then the minimum number of jumps needed to reach $\displaystyle 2^i k$ is greater than the minimum number of jumps needed to reach $\displaystyle 2^i$.

Solution

Problem 6

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

Solution

Resources