Difference between revisions of "2012 AIME I Problems/Problem 15"
I Love Math (talk | contribs) m |
|||
Line 19: | Line 19: | ||
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. | 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 using inclusion-exclusion. We get a final answer of <math>998 - (499 + 333 - 166) = \boxed{332 | + | 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>. |
Revision as of 15:34, 29 February 2020
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
-
(






-
(

Find the number of possible values of with
Solution
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
.
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.