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 "1993 AIME Problems/Problem 9"

m
(→‎Solution 2)
 
(8 intermediate revisions by 5 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
Two thousand points are given on a circle. Label one of the points 1. From this point, count 2 points in the clockwise direction and label this point 2. From the point labeled 2, count 3 points in the clockwise direction and label this point 3. (See figure.) Continue this process until the labels <math>1,2,3\dots,1993\,</math> are all used. Some of the points on the circle will have more than one label and some points will not have a label. What is the smallest integer that labels the same point as 1993?  
+
Two thousand points are given on a [[circle]]. Label one of the points <math>1</math>. From this point, count <math>2</math> points in the clockwise direction and label this point <math>2</math>. From the point labeled <math>2</math>, count <math>3</math> points in the clockwise direction and label this point <math>3</math>. (See figure.) Continue this process until the labels <math>1,2,3\dots,1993\,</math> are all used. Some of the points on the circle will have more than one label and some points will not have a label. What is the smallest integer that labels the same point as <math>1993</math>?  
  
 
[[Image:AIME_1993_Problem_9.png]]
 
[[Image:AIME_1993_Problem_9.png]]
  
 
== Solution ==
 
== Solution ==
−
{{solution}}
+
The label <math>1993</math> will occur on the <math>\frac12(1993)(1994) \pmod{2000}</math>th point around the circle. (Starting from 1) A number <math>n</math> will only occupy the same point on the circle if <math>\frac12(n)(n + 1)\equiv \frac12(1993)(1994) \pmod{2000}</math>.
 +
 
 +
Simplifying this expression, we see that <math>(1993)(1994) - (n)(n + 1) = (1993 - n)(1994 + n)\equiv 0\pmod{2000}</math>. Therefore, one of <math>1993 - n</math> or <math>1994 + n</math> is odd, and each of them must be a multiple of <math>125</math> or <math>16</math>.
 +
 
 +
For <math>1993 - n</math> to be a multiple of <math>125</math> and <math>1994 + n</math> to be a multiple of <math>16</math>, <math>n \equiv 118 \pmod {125}</math> and <math>n\equiv 6 \pmod {16}</math>. The smallest <math>n</math> for this case is <math>118</math>.
 +
 
 +
In order for <math>1993 - n</math> to be a multiple of <math>16</math> and <math>1994 + n</math> to be a multiple of <math>125</math>, <math>n\equiv 9\pmod{16}</math> and <math>n\equiv 6\pmod{125}</math>. The smallest <math>n</math> for this case is larger than <math>118</math>, so <math>\boxed{118}</math> is our answer.
 +
 
 +
'''Note:''' One can just substitute <math>1993\equiv-7\pmod{2000}</math> and <math>1994\equiv-6\pmod{2000}</math> to simplify calculations.
 +
== Solution 2 ==
 +
Two labels <math>a</math> and <math>b</math> occur on the same point if <math>\ a(a+1)/2\equiv \ b(b+1)/2\pmod{2000}</math>. If we assume the final answer be <math>n</math>, then we have <math>\frac12(n)(n + 1)\equiv \frac12(1993)(1994) \pmod{2000}</math>.
 +
 
 +
Multiply <math>2</math> on both side we have <math>(1993)(1994) - (n)(n + 1) = (1993 - n)(1994 + n)\equiv 0\pmod{4000}</math>. As they have different parities, the even one must be divisible by <math>32</math>. As <math> (1993 - n)+(1994 + n)\equiv 2\pmod{5}</math>, one of them is divisible by <math>5</math>, which indicates it's divisible by <math>125</math>.
 +
 
 +
Which leads to four different cases: <math>1993-n\equiv 0\pmod{4000}</math> ; <math>1994+n\equiv 0\pmod{4000}</math> ; <math>1993-n\equiv 0\pmod{32}</math> and <math>1994+n\equiv 0\pmod{125}</math> ; <math>1993-n\equiv 0\pmod{125}</math> and <math>1994+n\equiv 0\pmod{32}</math>. Which leads to <math>n\equiv 1993,2006,3881</math> and <math>118\pmod{4000}</math> respectively, and only <math>n=118</math> satisfied.Therefore answer is <math>\boxed{118}</math>.(by ZJY)
  
 
== See also ==
 
== See also ==
−
* [[1993 AIME Problems/Problem 8 | Previous problem]]
+
{{AIME box|year=1993|num-b=8|num-a=10}}
−
* [[1993 AIME Problems/Problem 10 | Next problem]]
+
 
−
* [[1993 AIME Problems]]
+
[[Category:Intermediate Number Theory Problems]]
 +
{{MAA Notice}}

Latest revision as of 01:06, 22 September 2023

Problem

Two thousand points are given on a circle. Label one of the points $1$. From this point, count $2$ points in the clockwise direction and label this point $2$. From the point labeled $2$, count $3$ points in the clockwise direction and label this point $3$. (See figure.) Continue this process until the labels $1,2,3\dots,1993\,$ are all used. Some of the points on the circle will have more than one label and some points will not have a label. What is the smallest integer that labels the same point as $1993$?

AIME 1993 Problem 9.png

Solution

The label $1993$ will occur on the $\frac12(1993)(1994) \pmod{2000}$th point around the circle. (Starting from 1) A number $n$ will only occupy the same point on the circle if $\frac12(n)(n + 1)\equiv \frac12(1993)(1994) \pmod{2000}$.

Simplifying this expression, we see that $(1993)(1994) - (n)(n + 1) = (1993 - n)(1994 + n)\equiv 0\pmod{2000}$. Therefore, one of $1993 - n$ or $1994 + n$ is odd, and each of them must be a multiple of $125$ or $16$.

For $1993 - n$ to be a multiple of $125$ and $1994 + n$ to be a multiple of $16$, $n \equiv 118 \pmod {125}$ and $n\equiv 6 \pmod {16}$. The smallest $n$ for this case is $118$.

In order for $1993 - n$ to be a multiple of $16$ and $1994 + n$ to be a multiple of $125$, $n\equiv 9\pmod{16}$ and $n\equiv 6\pmod{125}$. The smallest $n$ for this case is larger than $118$, so $\boxed{118}$ is our answer.

Note: One can just substitute $1993\equiv-7\pmod{2000}$ and $1994\equiv-6\pmod{2000}$ to simplify calculations.

Solution 2

Two labels $a$ and $b$ occur on the same point if $\ a(a+1)/2\equiv \ b(b+1)/2\pmod{2000}$. If we assume the final answer be $n$, then we have $\frac12(n)(n + 1)\equiv \frac12(1993)(1994) \pmod{2000}$.

Multiply $2$ on both side we have $(1993)(1994) - (n)(n + 1) = (1993 - n)(1994 + n)\equiv 0\pmod{4000}$. As they have different parities, the even one must be divisible by $32$. As $(1993 - n)+(1994 + n)\equiv 2\pmod{5}$, one of them is divisible by $5$, which indicates it's divisible by $125$.

Which leads to four different cases: $1993-n\equiv 0\pmod{4000}$ ; $1994+n\equiv 0\pmod{4000}$ ; $1993-n\equiv 0\pmod{32}$ and $1994+n\equiv 0\pmod{125}$ ; $1993-n\equiv 0\pmod{125}$ and $1994+n\equiv 0\pmod{32}$. Which leads to $n\equiv 1993,2006,3881$ and $118\pmod{4000}$ respectively, and only $n=118$ satisfied.Therefore answer is $\boxed{118}$.(by ZJY)

See also

1993 AIME (Problems • Answer Key • Resources)
Preceded by
Problem 8 		Followed by
Problem 10
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1993_AIME_Problems/Problem_9&oldid=198474"