Difference between revisions of "2012 AIME I Problems/Problem 15"
Algebra2000 (talk | contribs) (→Solution) |
m (→Solution) |
||
Line 17: | Line 17: | ||
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 \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-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 | + | 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>p</math> and <math>q</math> are relatively prime if and only if <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. |
− | Now we simply count all <math>n</math> that are not multiples of <math>2</math> or <math>3</math>, which is easy by | + | Now we simply count all <math>n</math> that are not multiples of <math>2</math> or <math>3</math>, which is easy by the principle of inclusion-exclusion. We get a final answer of <math>998 - (499 + 333 - 166) = \boxed{332.}</math> |
== 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}} |
Revision as of 19:39, 17 March 2012
Problem 15
There are mathematicians seated around a circular table with
seats numbered
in clockwise order. After a break the again sit around the table. The mathematicians note that there is a positive integer
such that
-
(
![$1$](http://latex.artofproblemsolving.com/d/c/e/dce34f4dfb2406144304ad0d6106c5382ddd1446.png)
![$k,$](http://latex.artofproblemsolving.com/c/9/9/c99a6aaebc17474bd09ea71d84d4e769a0662b55.png)
![$k$](http://latex.artofproblemsolving.com/8/c/3/8c325612684d41304b9751c175df7bcc0f61f64f.png)
![$ka$](http://latex.artofproblemsolving.com/4/0/8/408730e185e0b41fcc93fd334b48e79f1c8e799d.png)
![$i + n$](http://latex.artofproblemsolving.com/d/4/9/d49c43f56bface4f34de7ad1d3e6a46a70fc1b63.png)
![$i$](http://latex.artofproblemsolving.com/3/4/8/34857b3ba74ce5cd8607f3ebd23e9015908ada71.png)
-
(
![$2$](http://latex.artofproblemsolving.com/4/1/c/41c544263a265ff15498ee45f7392c5f86c6d151.png)
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 by the principle of inclusion-exclusion. We get a final answer of
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 |