Difference between revisions of "2012 AIME I Problems/Problem 15"
Michelangelo (talk | contribs) (→Solution) |
|||
(10 intermediate revisions by 6 users not shown) | |||
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 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 \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</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> 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> | + | 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.}</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}} | {{MAA Notice}} |
Latest revision as of 20: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
-
(
![$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 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
.
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.