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 "2012 AIME I Problems/Problem 15"

(→‎Solution)
 
(16 intermediate revisions by 10 users not shown)
Line 1: Line 1:
−
==Problem 15==
+
==Problem==
−
There are <math>n</math> mathematicians seated around a circular table with <math>n</math> seats numbered <math>1,</math> <math>2,</math> <math>3,</math> <math>...,</math> <math>n</math> in clockwise order. After a break the again sit around the table. The mathematicians note that there is a positive integer <math>a</math> such that
+
There are <math>n</math> mathematicians seated around a circular table with <math>n</math> seats numbered <math>1,</math> <math>2,</math> <math>3,</math> <math>...,</math> <math>n</math> in clockwise order. After a break they again sit around the table. The mathematicians note that there is a positive integer <math>a</math> such that
  
 
<UL>
 
<UL>
Line 15: Line 15:
 
It is a well-known fact that the set <math>0, a, 2a, ... (n-1)a</math> forms a complete set of residues if and only if <math>a</math> is relatively prime to <math>n</math>.
 
It is a well-known fact that the set <math>0, a, 2a, ... (n-1)a</math> forms a complete set of residues if and only if <math>a</math> is relatively prime to <math>n</math>.
  
−
Thus, we have <math>a</math> is relatively prime to <math>n</math>. In addition, for any seats <math>p</math> and <math>q</math>, we must have <math>ap - aq</math> not be equivalent to either <math>p - q</math> or <math>q - p</math> modulo <math>n</math> to satisfy our conditions. These simplify to <math>(a-1)p \equiv (a-1)q</math> and <math>(a+1)p \equiv (a+1)q</math> modulo <math>n</math>, so multiplication by both <math>a-1</math> and <math>a+1</math> must form a complete set of residues mod <math>n</math> as well.  
+
Thus, we have <math>a</math> is relatively prime to <math>n</math>. In addition, for any seats <math>p</math> and <math>q</math>, we must have <math>ap - aq</math> not be equivalent to either <math>p - q</math> or <math>q - p</math> modulo <math>n</math> to satisfy our conditions. These simplify to <math>(a-1)p \not\equiv (a-1)q</math> and <math>(a+1)p \not\equiv (a+1)q</math> modulo <math>n</math>, so multiplication by both <math>a-1</math> and <math>a+1</math> must form a complete set of residues mod <math>n</math> as well.  
  
−
Thus, we have <math>a-1</math>, <math>a</math>, and <math>a+1</math> are relatively prime to <math>n</math>. We must find all <math>n</math> for which such an <math>a</math> exists. <math>n</math> cannot obviously not be a multiple of <math>2</math> or <math>3</math>, but for any other <math>n</math>, we can set <math>a = n-2</math>, and then <math>a-1 = n-3</math> and <math>a+1 = n-1</math>. All three of these will be relatively prime to <math>n</math>, since two numbers <math>p</math> and <math>q</math> are relatively prime iff <math>p-q</math> is relatively prime to <math>p</math>. In this case, <math>1</math>, <math>2</math>, and <math>3</math> are all relatively prime to <math>n</math>, so <math>a = n-2</math> works.
+
Thus, we have <math>a-1</math>, <math>a</math>, and <math>a+1</math> are relatively prime to <math>n</math>. We must find all <math>n</math> for which such an <math>a</math> exists. <math>n</math> obviously cannot be a multiple of <math>2</math> or <math>3</math>, but for any other <math>n</math>, we can set <math>a = n-2</math>, and then <math>a-1 = n-3</math> and <math>a+1 = n-1</math>. All three of these will be relatively prime to <math>n</math>, since two numbers <math>x</math> and <math>y</math> are relatively prime if and only if <math>x-y</math> is relatively prime to <math>x</math>. In this case, <math>1</math>, <math>2</math>, and <math>3</math> are all relatively prime to <math>n</math>, so <math>a = n-2</math> works.
  
−
Now we simply count all <math>n</math> that are not multiples of <math>2</math> or <math>3</math>, which is easy by PIE. We get a final answer of <math>998 - (499 + 333 - 166) = \boxed{332}</math>.
+
Now we simply count all <math>n</math> that are not multiples of <math>2</math> or <math>3</math>, which is easy using inclusion-exclusion. We get a final answer of <math>998 - (499 + 333 - 166) = \boxed{332}</math>.
 +
 
 +
 
 +
Note: another way to find that <math>(a-1)</math> and <math>(a+1)</math> have to be relative prime to <math>n</math> is the following: start with <math>ap-aq \not \equiv \pm(p-q) \pmod n</math>. Then, we can divide by <math>p-q</math> to get <math>a \not \equiv \pm 1</math> modulo <math>\frac{n}{\gcd(n, p-q)}</math>. Since <math>\gcd(n, p-q)</math> ranges through all the divisors of <math>n</math>, we get that <math>a \not \equiv \pm 1</math> modulo the divisors of <math>n</math> or <math>\gcd(a-1, n) = \gcd(a+1, n) = 1</math>.
 +
 
 +
== Video Solution by Richard Rusczyk ==
 +
 
 +
https://artofproblemsolving.com/videos/amc/2012aimei/355
 +
 
 +
~ dolphin7
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=2012|n=I|num-b=14|after=Last Problem}}
 
{{AIME box|year=2012|n=I|num-b=14|after=Last Problem}}
 +
{{MAA Notice}}

Latest revision as of 19:41, 24 January 2021

Problem

There are $n$ mathematicians seated around a circular table with $n$ seats numbered $1,$ $2,$ $3,$ $...,$ $n$ in clockwise order. After a break they again sit around the table. The mathematicians note that there is a positive integer $a$ such that

    ($1$) for each $k,$ the mathematician who was seated in seat $k$ before the break is seated in seat $ka$ after the break (where seat $i + n$ is seat $i$);
    ($2$) for every pair of mathematicians, the number of mathematicians sitting between them after the break, counting in both the clockwise and the counterclockwise directions, is different from either of the number of mathematicians sitting between them before the break.

Find the number of possible values of $n$ with $1 < n < 1000.$

Solution

It is a well-known fact that the set $0, a, 2a, ... (n-1)a$ forms a complete set of residues if and only if $a$ is relatively prime to $n$.

Thus, we have $a$ is relatively prime to $n$. In addition, for any seats $p$ and $q$, we must have $ap - aq$ not be equivalent to either $p - q$ or $q - p$ modulo $n$ to satisfy our conditions. These simplify to $(a-1)p \not\equiv (a-1)q$ and $(a+1)p \not\equiv (a+1)q$ modulo $n$, so multiplication by both $a-1$ and $a+1$ must form a complete set of residues mod $n$ as well.

Thus, we have $a-1$, $a$, and $a+1$ are relatively prime to $n$. We must find all $n$ for which such an $a$ exists. $n$ obviously cannot be a multiple of $2$ or $3$, but for any other $n$, we can set $a = n-2$, and then $a-1 = n-3$ and $a+1 = n-1$. All three of these will be relatively prime to $n$, since two numbers $x$ and $y$ are relatively prime if and only if $x-y$ is relatively prime to $x$. In this case, $1$, $2$, and $3$ are all relatively prime to $n$, so $a = n-2$ works.

Now we simply count all $n$ that are not multiples of $2$ or $3$, which is easy using inclusion-exclusion. We get a final answer of $998 - (499 + 333 - 166) = \boxed{332}$.


Note: another way to find that $(a-1)$ and $(a+1)$ have to be relative prime to $n$ is the following: start with $ap-aq \not \equiv \pm(p-q) \pmod n$. Then, we can divide by $p-q$ to get $a \not \equiv \pm 1$ modulo $\frac{n}{\gcd(n, p-q)}$. Since $\gcd(n, p-q)$ ranges through all the divisors of $n$, we get that $a \not \equiv \pm 1$ modulo the divisors of $n$ or $\gcd(a-1, n) = \gcd(a+1, n) = 1$.

Video Solution by Richard Rusczyk

https://artofproblemsolving.com/videos/amc/2012aimei/355

~ dolphin7

See also

2012 AIME I (Problems • Answer Key • Resources)
Preceded by
Problem 14 		Followed by
Last Problem
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=2012_AIME_I_Problems/Problem_15&oldid=143156"