Difference between revisions of "2006 USAMO Problems"

m (Resources)
m
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 exist integers <math>m</math> and <math>n</math> with <math>0<m<n<p</math> and
 
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 exist integers <math>m</math> and <math>n</math> with <math>0<m<n<p</math> and
 
<cmath>\left\lbrace\frac{sm}{p}\right\rbrace<\left\lbrace\frac{sn}{p}\right\rbrace<\frac{s}{p}</cmath>
 
<cmath>\left\lbrace\frac{sm}{p}\right\rbrace<\left\lbrace\frac{sn}{p}\right\rbrace<\frac{s}{p}</cmath>
Line 9: Line 9:
 
[[2006 USAMO Problems/Problem 1 | Solution]]
 
[[2006 USAMO Problems/Problem 1 | Solution]]
  
== Problem 2 ==
+
=== Problem 2 ===
 
For a given positive integer <math>k</math> find, in terms of <math>k</math>, 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 <math>k</math> has sum at most <math>N/2</math>.
 
For a given positive integer <math>k</math> find, in terms of <math>k</math>, 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 <math>k</math> has sum at most <math>N/2</math>.
  
 
[[2006 USAMO Problems/Problem 2 | Solution]]
 
[[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(\pm1)=1</math> and <math>p(0)=\infty</math>. Find all polynomials <math>f</math> with integer coefficients such that the sequence <math>\lbrace p(f(n^2))-2n\rbrace_{n\ge0}</math> is bounded above. (In particular, this requires <math>f(n^2)\neq0</math> for <math>n\ge0</math>.)
 
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(\pm1)=1</math> and <math>p(0)=\infty</math>. Find all polynomials <math>f</math> with integer coefficients such that the sequence <math>\lbrace p(f(n^2))-2n\rbrace_{n\ge0}</math> is bounded above. (In particular, this requires <math>f(n^2)\neq0</math> for <math>n\ge0</math>.)
  
 
[[2006 USAMO Problems/Problem 3 | Solution]]
 
[[2006 USAMO Problems/Problem 3 | Solution]]
  
= Day 2 =
+
== Day 2 ==
== Problem 4 ==
+
=== Problem 4 ===
 
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+\ldots+a_k=a_1\cdot a_2\cdots a_k=n</math>.
 
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+\ldots+a_k=a_1\cdot a_2\cdots a_k=n</math>.
  
 
[[2006 USAMO Problems/Problem 4 | Solution]]
 
[[2006 USAMO Problems/Problem 4 | Solution]]
  
== Problem 5 ==
+
=== 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 <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 2 that is a factor of <math>n</math>. Show that if <math>k\ge2</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 1, 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 2 that is a factor of <math>n</math>. Show that if <math>k\ge2</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]]
  
== Problem 6 ==
+
=== Problem 6 ===
 
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>AE/ED=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</math>, <math>SBF</math>, <math>TCF</math>, and <math>TDE</math> pass through a common point.
 
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>AE/ED=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</math>, <math>SBF</math>, <math>TCF</math>, and <math>TDE</math> pass through a common point.
  

Revision as of 17:14, 17 September 2012

Day 1

Problem 1

Let $p$ be a prime number and let $s$ be an integer with $0<s<p$. Prove that there exist integers $m$ and $n$ with $0<m<n<p$ and \[\left\lbrace\frac{sm}{p}\right\rbrace<\left\lbrace\frac{sn}{p}\right\rbrace<\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 $\lbrace x\rbrace=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 $N/2$.

Solution

Problem 3

For integral $m$, let $p(m)$ be the greatest prime divisor of $m$. By convention, we set $p(\pm1)=1$ and $p(0)=\infty$. Find all polynomials $f$ with integer coefficients such that the sequence $\lbrace p(f(n^2))-2n\rbrace_{n\ge0}$ is bounded above. (In particular, this requires $f(n^2)\neq0$ for $n\ge0$.)

Solution

Day 2

Problem 4

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+\ldots+a_k=a_1\cdot a_2\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 $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\ge2$ 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 6

Let $ABCD$ be a quadrilateral, and let $E$ and $F$ be points on sides $AD$ and $BC$, respectively, such that $AE/ED=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

See Also

2006 USAMO (ProblemsResources)
Preceded by
2005 USAMO
Followed by
2007 USAMO
1 2 3 4 5 6
All USAMO Problems and Solutions