2012 AIME I Problems/Problem 15
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
It is a well-known 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 inclusion-exclusion. 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 .
|2012 AIME I (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|