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 "1995 USAMO Problems"

(problems page)
 
(revert to original wording)
Line 1: Line 1:
 +
Problems of the [[1995 USAMO | 1995]] [[USAMO]].
 +
 
==Problem 1==
 
==Problem 1==
−
The sequence <math>a_i</math> of [[nonnegative]] [[integer]]s is defined as follows: The first <math>p-1</math> terms are <math>0, 1, 2, 3, ... , p-2</math>. Then <math>a_n</math> is the least positive integer so that there is no arithmetic progression of length <math>p</math> in the first n+1 terms. If <math>p</math> is an odd prime, show that an is the number obtained by writing <math>n</math> in base <math>p-1</math>, then treating the result as a number in base <math>p</math>.
+
 
 +
Let <math>\, p \,</math> be an odd [[prime]].  The sequence <math>(a_n)_{n \geq 0}</math> is defined as follows: <math>\, a_0 = 0, </math> <math>a_1 = 1, \, \ldots, \, a_{p-2} = p-2 \,</math> and, for all <math>\, n \geq p-1, \,</math> <math>\, a_n \,</math> is the least positive integer that does not form an arithmetic sequence of length <math>\, p \,</math> with any of the preceding terms. Prove that, for all <math>\, n, \,</math> <math>\, a_n \,</math> is the number obtained by writing <math>\, n \,</math> in base <math>\, p-1 \,</math> and reading the result in base <math>\, p</math>.
  
 
[[1995 USAMO Problems/Problem 1|Solution]]
 
[[1995 USAMO Problems/Problem 1|Solution]]
 +
 
==Problem 2==
 
==Problem 2==
−
A trigonometric map is any one of <math>\sin, \cos, \tan, \arcsin, \arccos</math> and <math>\arctan</math>. Show that given any [[positive]] [[rational]] number <math>x</math>, one can find a finite sequence of trigonometric maps which take <math>0</math> to <math>x</math>.
+
 
 +
A calculator is broken so that the only keys that still work are the <math>\, \sin, \; \cos, </math>  <math>\tan, \; \sin^{-1}, \; \cos^{-1}, \,</math> and <math>\, \tan^{-1} \,</math> buttons. The display initially shows 0. Given any positive rational number <math>\, q, \,</math> show that pressing some finite sequence of buttons will yield <math>\, q</math>.  Assume that the calculator does real number calculations with infinite precision.  All functions are in terms of radians.
  
 
[[1995 USAMO Problems/Problem 2|Solution]]
 
[[1995 USAMO Problems/Problem 2|Solution]]
 +
 
==Problem 3==
 
==Problem 3==
−
The circumcenter <math>O</math> of the triangle <math>\triangle ABC</math> does not lie on any side or [[median]]. Let the midpoints of <math>BC, CA, AB</math> be <math>L, M, N</math> respectively. Construct <math>P, Q, R</math> on the rays <math>OL, OM, ON</math> respectively so that <math>\angle OPA = \angle OAL, \angle OQB = \angle OBM and \angle ORC = \angle OCN</math>. Show that <math>AP, BQ</math> and <math>CR</math> are [[concurrent]].
+
 
 +
Given a nonisosceles, nonright triangle <math>\, ABC, \,</math> let <math>\, O \,</math> denote the center of its circumscribed circle, and let <math>\, A_1, \, B_1, \,</math> and <math>\, C_1 \,</math> be the midpoints of sides <math>\, BC, \, CA, \,</math> and <math>\, AB, \,</math> respectively. Point <math>\, A_2 \,</math> is located on the ray <math>\, OA_1 \,</math> so that <math>\, \Delta OAA_1 \,</math> is similar to <math>\, \Delta OA_2A</math>.  Points <math>\, B_2 \,</math> and <math>\, C_2 \,</math> on rays <math>\, OB_1 \,</math> and <math>\, OC_1, \,</math> respectively, are defined similarly. Prove that lines <math>\, AA_2, \, BB_2, \,</math> and <math>\, CC_2 \,</math> are concurrent, i.e. these three lines intersect at a point.
  
 
[[1995 USAMO Problems/Problem 3|Solution]]
 
[[1995 USAMO Problems/Problem 3|Solution]]
  
 
==Problem 4==
 
==Problem 4==
−
<math>a_1</math> is an [[infinite]] sequence of [[integers]] such that <math>a_n - a_m</math> is divisible by <math>n - m</math> for all <math>n</math> and <math>m</math> such that <math>n\ne m</math>. For some polynomial <math>p(x)</math> we have <math>p(n) > |a_n|</math> for all <math>n</math>. Show that there is a polynomial <math>q(x)</math> such that <math>q(n) = a_n</math> for all <math>n</math>.  
+
 
 +
Suppose <math>\, q_0, \, q_1, \,  q_2, \ldots \; \,</math> is an infinite sequence of integers satisfying the following two conditions:<br>
 +
(i)  <math>\, m-n \,</math> divides <math>\, q_m - q_n \,</math> for <math>\, m > n \geq 0,</math> <br>
 +
(ii) there is a polynomial <math>\, P \,</math> such that <math>\, |q_n| < P(n) \,</math> for all <math>\, n</math>. <br>
 +
Prove that there is a polynomial <math>\, Q \,</math> such that <math>\, q_n = Q(n) \,</math> for all <math>\, n</math>.
  
 
[[1995 USAMO Problems/Problem 4|Solution]]
 
[[1995 USAMO Problems/Problem 4|Solution]]
  
 
==Problem 5==
 
==Problem 5==
−
A [[graph (graph theory)|graph]] with <math>n</math> [[vertex|vertices]] and <math>k</math> edges has no faces of degree three. Show that it has a vertice <math>P</math> such that there are at most <math>k(1 - \frac{4k}{n^2})</math> edges between points not joined to <math>P</math>.
+
 
 +
Suppose that in a certain society, each pair of persons can be classified as either ''amicable'' or ''hostile''. We shall say that each member of an amicable pair is a ''friend'' of the other, and each member of a hostile pair is a ''foe'' of the other.  Suppose that the society has <math>\, n \,</math> persons and <math>\, q \,</math> amicable pairs, and that for every set of three persons, at least one pair is hostile. Prove that there is at least one member of the society whose foes include <math>\, q(1 - 4q/n^2) \,</math> or fewer amicable pairs.
  
 
[[1995 USAMO Problems/Problem 5|Solution]]
 
[[1995 USAMO Problems/Problem 5|Solution]]
 +
 +
== Resources ==
 +
 +
{{USAMO box|year=1995|before=[[1994 USAMO]]|after=[[1996 USAMO]]}}
 +
 +
* [http://www.artofproblemsolving.com/resources.php?c=182&cid=27&year=1995 1995 USAMO Problems on the resources page]
 +
* [http://www.unl.edu/amc/a-activities/a7-problems/USAMO-IMO/q-usamo/-tex/usamo1995.tex 1995 USAMO Problems (TEX)]
 +
* [http://www.unl.edu/amc/a-activities/a7-problems/USAMO-IMO/q-usamo/-pdf/usamo1995.pdf 1995 USAMO Problems (PDF)]

Revision as of 12:22, 10 February 2008

Problems of the 1995 USAMO.

Problem 1

Let $\, p \,$ be an odd prime. The sequence $(a_n)_{n \geq 0}$ is defined as follows: $\, a_0 = 0,$ $a_1 = 1, \, \ldots, \, a_{p-2} = p-2 \,$ and, for all $\, n \geq p-1, \,$ $\, a_n \,$ is the least positive integer that does not form an arithmetic sequence of length $\, p \,$ with any of the preceding terms. Prove that, for all $\, n, \,$ $\, a_n \,$ is the number obtained by writing $\, n \,$ in base $\, p-1 \,$ and reading the result in base $\, p$.

Solution

Problem 2

A calculator is broken so that the only keys that still work are the $\, \sin, \; \cos,$ $\tan, \; \sin^{-1}, \; \cos^{-1}, \,$ and $\, \tan^{-1} \,$ buttons. The display initially shows 0. Given any positive rational number $\, q, \,$ show that pressing some finite sequence of buttons will yield $\, q$. Assume that the calculator does real number calculations with infinite precision. All functions are in terms of radians.

Solution

Problem 3

Given a nonisosceles, nonright triangle $\, ABC, \,$ let $\, O \,$ denote the center of its circumscribed circle, and let $\, A_1, \, B_1, \,$ and $\, C_1 \,$ be the midpoints of sides $\, BC, \, CA, \,$ and $\, AB, \,$ respectively. Point $\, A_2 \,$ is located on the ray $\, OA_1 \,$ so that $\, \Delta OAA_1 \,$ is similar to $\, \Delta OA_2A$. Points $\, B_2 \,$ and $\, C_2 \,$ on rays $\, OB_1 \,$ and $\, OC_1, \,$ respectively, are defined similarly. Prove that lines $\, AA_2, \, BB_2, \,$ and $\, CC_2 \,$ are concurrent, i.e. these three lines intersect at a point.

Solution

Problem 4

Suppose $\, q_0, \, q_1, \, q_2, \ldots \; \,$ is an infinite sequence of integers satisfying the following two conditions:
(i) $\, m-n \,$ divides $\, q_m - q_n \,$ for $\, m > n \geq 0,$
(ii) there is a polynomial $\, P \,$ such that $\, |q_n| < P(n) \,$ for all $\, n$.
Prove that there is a polynomial $\, Q \,$ such that $\, q_n = Q(n) \,$ for all $\, n$.

Solution

Problem 5

Suppose that in a certain society, each pair of persons can be classified as either amicable or hostile. We shall say that each member of an amicable pair is a friend of the other, and each member of a hostile pair is a foe of the other. Suppose that the society has $\, n \,$ persons and $\, q \,$ amicable pairs, and that for every set of three persons, at least one pair is hostile. Prove that there is at least one member of the society whose foes include $\, q(1 - 4q/n^2) \,$ or fewer amicable pairs.

Solution

Resources

1995 USAMO (Problems • Resources)
Preceded by
1994 USAMO 		Followed by
1996 USAMO
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1995_USAMO_Problems&oldid=23137"