Difference between revisions of "2012 AIME I Problems/Problem 15"
Line 1:  Line 1:  
−  ==Problem  +  ==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 they 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  
Line 24:  Line 24:  
Note: another way to find that <math>(a1)</math> and <math>(a+1)</math> have to be relative prime to <math>n</math> is the following: start with <math>apaq \not \equiv \pm(pq) \pmod n</math>. Then, we can divide by <math>pq</math> to get <math>a \not \equiv \pm 1</math> modulo <math>\frac{n}{\gcd(n, pq)}</math>. Since <math>\gcd(n, pq)</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(a1, n) = \gcd(a+1, n) = 1</math>.  Note: another way to find that <math>(a1)</math> and <math>(a+1)</math> have to be relative prime to <math>n</math> is the following: start with <math>apaq \not \equiv \pm(pq) \pmod n</math>. Then, we can divide by <math>pq</math> to get <math>a \not \equiv \pm 1</math> modulo <math>\frac{n}{\gcd(n, pq)}</math>. Since <math>\gcd(n, pq)</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(a1, n) = \gcd(a+1, n) = 1</math>.  
−  +  == Video Solution by Richard Rusczyk ==  
https://artofproblemsolving.com/videos/amc/2012aimei/355  https://artofproblemsolving.com/videos/amc/2012aimei/355 
Latest revision as of 19:41, 24 January 2021
Problem
There are mathematicians seated around a circular table with seats numbered in clockwise order. After a break they again sit around the table. The mathematicians note that there is a positive integer such that

() for each the mathematician who was seated in seat before the break is seated in seat after the break (where seat is seat );

() 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 with
Solution
It is a wellknown fact that the set forms a complete set of residues if and only if is relatively prime to .
Thus, we have is relatively prime to . In addition, for any seats and , we must have not be equivalent to either or modulo to satisfy our conditions. These simplify to and modulo , so multiplication by both and must form a complete set of residues mod as well.
Thus, we have , , and are relatively prime to . We must find all for which such an exists. obviously cannot be a multiple of or , but for any other , we can set , and then and . All three of these will be relatively prime to , since two numbers and are relatively prime if and only if is relatively prime to . In this case, , , and are all relatively prime to , so works.
Now we simply count all that are not multiples of or , which is easy using inclusionexclusion. We get a final answer of .
Note: another way to find that and have to be relative prime to is the following: start with . Then, we can divide by to get modulo . Since ranges through all the divisors of , we get that modulo the divisors of or .
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.