https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Vishwathganesan&feedformat=atomAoPS Wiki - User contributions [en]2024-03-29T13:30:21ZUser contributionsMediaWiki 1.31.1https://artofproblemsolving.com/wiki/index.php?title=2011_AMC_12B_Problems/Problem_23&diff=886452011 AMC 12B Problems/Problem 232017-11-26T17:31:48Z<p>Vishwathganesan: Undo revision 88643 by Hydrahead (talk)</p>
<hr />
<div>==Problem==<br />
<br />
A bug travels in the coordinate plane, moving only along the lines that are parallel to the <math>x</math>-axis or <math>y</math>-axis. Let <math>A = (-3, 2)</math> and <math>B = (3, -2)</math>. Consider all possible paths of the bug from <math>A</math> to <math>B</math> of length at most <math>20</math>. How many points with integer coordinates lie on at least one of these paths?<br />
<br />
<math>\textbf{(A)}\ 161 \qquad \textbf{(B)}\ 185 \qquad \textbf{(C)}\ 195 \qquad \textbf{(D)}\ 227 \qquad \textbf{(E)}\ 255</math><br />
<br />
==Solution==<br />
Answer: (C)<br />
<br />
If a point <math>(x, y)</math> satisfy the property that <math>|x - 3| + |y + 2| + |x + 3| + |y - 2| \le 20</math>, then it is in the desirable range because <math>|x - 3| + |y + 2|</math> is the shortest path from <math>(x,y)</math> to <math>B</math>, and <math>|x + 3| + |y - 2|</math> is the shortest path from <math>(x,y)</math> to <math>A</math><br />
<br />
<br />
If <math>-3\le x \le 3</math>, then <math>-7\le y \le 7</math> satisfy the property. there are <math>15 \times 7 = 105</math> lattice points here.<br />
<br />
else let <math>3< x \le 8</math> (and for <math>-8 \le x < -3</math> it is symmetrical, <math>-7 + (x - 3)\le y \le 7 - (x - 3)</math>,<br />
<br />
<math>-4 + x\le y \le 4 - x</math><br />
<br />
So for <math>x = 4</math>, there are <math>13</math> lattice points,<br />
<br />
for <math>x = 5</math>, there are <math>11</math> lattice points,<br />
<br />
etc.<br />
<br />
For <math>x = 8</math>, there are <math>5</math> lattice points.<br />
<br /><br />
<br />
Hence, there are a total of <math>105 + 2 ( 13 + 11 + 9 + 7 + 5) = \boxed{195}</math> lattice points.<br />
<br />
== See also ==<br />
{{AMC12 box|year=2011|num-b=22|num-a=24|ab=B}}<br />
{{MAA Notice}}</div>Vishwathganesanhttps://artofproblemsolving.com/wiki/index.php?title=Fermat%27s_Little_Theorem&diff=87130Fermat's Little Theorem2017-08-20T01:18:40Z<p>Vishwathganesan: Undo revision 87127 by Douzz (talk)</p>
<hr />
<div>'''Fermat's Little Theorem''' is highly useful in [[number theory]] for simplifying the computation of exponents in [[modular arithmetic]] (which students should study more at the introductory level if they have a hard time following the rest of this article). This theorem is credited to [[Pierre de Fermat]].<br />
<br />
<br />
== Statement ==<br />
<br />
If <math>{a}</math> is an [[integer]], <math>{p}</math> is a [[prime number]] and <math>{a}</math> is not [[divisibility|divisible]] by <math>{p}</math>, then <math>a^{p-1}\equiv 1 \pmod {p}</math>.<br />
<br />
A frequently used corollary of Fermat's Little Theorem is <math> a^p \equiv a \pmod {p}</math>. As you can see, it is derived by multipling both sides of the theorem by <math>a</math>. The restated form is nice because we no longer need to restrict ourselves to integers <math>{a}</math> not divisible by <math>{p}</math>.<br />
<br />
This theorem is a special case of [[Euler's Totient Theorem]], which states that if <math>a</math> and <math>n</math> are integers, then <math>a^{\phi(n)} \equiv 1 \pmod{n}</math>, where <math>\phi(n)</math> denotes [[Euler's totient function]]. In particular, <math>\phi(p) = p-1</math> for prime numbers <math>p</math>. In turn, this is a special case of [[Lagrange's Theorem]].<br />
<br />
In contest problems, Fermat's Little Theorem is often used in conjunction with the [[Chinese Remainder Theorem]] to simplify tedious calculations.<br />
<br />
== Proof ==<br />
We offer several proofs using different techniques to prove the statement <math>a^p \equiv a \pmod{p}</math>. If <math>\text{gcd}\,(a,p) = 1</math>, then we can cancel a factor of <math>a</math> from both sides and retrieve the first version of the theorem. <br />
<br />
=== Proof 1 (Induction) ===<br />
<br />
The most straightforward way to prove this theorem is by by applying the [[induction]] principle. We fix <math>p</math> as a prime number. The base case, <math>1^p \equiv 1 \pmod{p}</math>, is obviously true. Suppose the statement <math>a^p \equiv a \pmod{p}</math> is true. Then, by the [[binomial theorem]], <br />
<br />
<center><cmath>(a+1)^p = a^p + {p \choose 1} a^{p-1} + {p \choose 2} a^{p-2} + \cdots + {p \choose p-1} a + 1.</cmath></center><br />
<br />
Note that <math>p</math> divides into any binomial coefficient of the form <math>{p \choose k}</math> for <math>1 \le k \le p-1</math>. This follows by the definition of the binomial coefficient as <math>{p \choose k} = \frac{p!}{k! (p-k)!}</math>; since <math>p</math> is prime, then <math>p</math> divides the numerator, but not the denominator. <br />
<br />
Taken <math>\mod p</math>, all of the middle terms disappear, and we end up with <math>(a+1)^p \equiv a^p + 1 \pmod{p}</math>. Since we also know that <math>a^p \equiv a\pmod{p}</math>, then <math>(a+1)^p \equiv a+1 \pmod{p}</math>, as desired. <br />
<br />
=== Proof 2 (Inverses) ===<br />
<br />
Let <math>S = \{1,2,3,\cdots, p-1\}</math>. Then, we claim that the set <math>a \cdot S</math>, consisting of the product of the elements of <math>S</math> with <math>a</math>, taken modulo <math>p</math>, is simply a permutation of <math>S</math>. In other words, <br />
<br />
<center><cmath>S \equiv \{1a, 2a, \cdots, (p-1)a\} \pmod{p}.</cmath></center><br><br />
<br />
Clearly none of the <math>ia</math> for <math>1 \le i \le p-1</math> are divisible by <math>p</math>, so it suffices to show that all of the elements in <math>a \cdot S</math> are distinct. Suppose that <math>ai \equiv aj \pmod{p}</math> for <math>i \neq j</math>. Since <math>\text{gcd}\, (a,p) = 1</math>, by the cancellation rule, that reduces to <math>i \equiv j \pmod{p}</math>, which is a contradiction. <br />
<br />
Thus, <math>\mod{p}</math>, we have that the product of the elements of <math>S</math> is <br />
<br />
<center><cmath>1a \cdot 2a \cdots (p-1)a \equiv 1 \cdot 2 \cdots (p-1) \pmod{p}.</cmath></center> <br><br />
<br />
Cancelling the factors <math>1, 2, 3, \ldots, p-1</math> from both sides, we are left with the statement <math>a^{p-1} \equiv 1 \pmod{p}</math>.<br><br />
<br />
A similar version can be used to prove [[Euler's Totient Theorem]], if we let <math>S = \{\text{natural numbers relatively prime to and less than}\ n\}</math>.<br />
<br />
=== Proof 3 (Combinatorics) ===<br />
<center><asy> <br />
real r = 0.3, row1 = 3.5, row2 = 0, row3 = -3.5;<br />
void necklace(pair k, pen colors[]){<br />
draw(shift(k)*unitcircle); <br />
for(int i = 0; i < colors.length; ++i){<br />
pair p = k+expi(pi/2+2*pi*i/colors.length);<br />
fill(Circle(p,r),colors[i]);<br />
draw(Circle(p,r));<br />
}<br />
}<br />
<br />
pen BEADS1[] = {red,red,red},BEADS2[] = {blue,blue,blue},BEADS3[] = {red,red,blue},BEADS4[] = {blue,red,red},BEADS5[] = {red,blue,red},BEADS6[] = {blue,blue,red},BEADS7[] = {red,blue,blue},BEADS8[] = {blue,red,blue};<br />
necklace((-1.5,row1),BEADS1);necklace((1.5,row1),BEADS2);necklace((-2.5,row2),BEADS3);necklace((0,row2),BEADS4);necklace((2.5,row2),BEADS5);necklace((-2.5,row3),BEADS6);necklace((0,row3),BEADS7);necklace((2.5,row3),BEADS8);<br />
</asy><br> An illustration of the case <math>p=3,a=2</math>.<br></center><br />
<br />
Consider a necklace with <math>p</math> beads, each bead of which can be colored in <math>a</math> different ways. There are <math>a^p</math> ways to pick the colors of the beads. <math>a</math> of these are necklaces that consists of beads of the same color. Of the remaining necklaces, for each necklace, there are exactly <math>p-1</math> more necklaces that are rotationally equivalent to this necklace. It follows that <math>a^p-a</math> must be divisible by <math>p</math>. Written in another way, <math>a^p \equiv a \pmod{p}</math>.<br />
<br />
=== Proof 4 (Geometry) ===<br />
<center><asy><br />
void match(int i, int j){ <br />
draw(shift((i,j))*unitsquare,linewidth(1));<br />
draw(shift((j,i))*unitsquare,linewidth(1));<br />
draw((i+0.5,j+0.5)--(j+0.5,i+0.5),linewidth(2));<br />
}<br />
int n = 6;<br />
for(int i = 0; i < n; ++i){<br />
for(int j = 0; j < n; ++j)<br />
draw(shift((i,j))*unitsquare, linewidth(0.5));<br />
}<br />
draw((0,0)--(n,n),red+linewidth(2)); match(2,4); match(0,3);<br />
</asy>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<asy><br />
import three; currentprojection = perspective(3,-2,4);<br />
void match(int i, int j, int k){ <br />
draw(shift((i,j,k))*box((0,0,0),(1,1,1)),linewidth(1));<br />
draw(shift((k,i,j))*box((0,0,0),(1,1,1)),linewidth(1));<br />
draw(shift((j,k,i))*box((0,0,0),(1,1,1)),linewidth(1));<br />
draw((i+0.5,j+0.5,k+0.5)--(j+0.5,k+0.5,i+0.5)--(k+0.5,i+0.5,j+0.5)--cycle,linewidth(2));<br />
}<br />
int n = 4;<br />
for(int i = 0; i < n; ++i){<br />
for(int j = 0; j < n; ++j)<br />
for(int k = 0; k < n; ++k)<br />
draw(shift((i,j,k))*box((0,0,0),(1,1,1)), linewidth(0.5));<br />
}<br />
draw((0,0,0)--(n,n,n),red+linewidth(2));match(2,3,1); </asy>For <math>p=2,3</math> and <math>a=6,4</math>, respectively.</center><br />
We imbed a [[hypercube]] of side length <math>a</math> in <math>\mathbb{R}^p</math> (the <math>p</math>-th dimensional [[Euclidean space]]), such that the vertices of the hypercube are at <math>(\pm a/2,\pm a/2, \ldots, \pm a/2)</math>. A hypercube is essentially a cube, generalized to higher dimensions. This hypercube consists of <math>a^p</math> separate unit hypercubes, with centers consisting of the points <br />
<br />
<center><cmath>P(x_1, x_2, \ldots, x_n) = \left(a + \frac 12 - x_1, a + \frac 12 - x_2, \ldots, a + \frac 12 - x_p\right),</cmath></center><br><br />
<br />
where each <math>x_i</math> is an integer from <math>1</math> to <math>a</math>. Besides the <math>a</math> centers of the unit hypercubes in the main diagonal (from <math>(-a/2, -a/2, \ldots, -a/2)</math> to <math>(a/2, a/2, \ldots, a/2)</math>), the transformation carrying <br />
<br />
<cmath>P(x_1, x_2, \ldots, x_n) \mapsto P(x_2, x_3, \ldots, x_n, x_1)</cmath><br><br />
<br />
maps one unit hypercube to a distinct hypercube. Much like the combinatorial proof, this splits the non-main diagonal unit hypercubes into groups of size <math>p</math>, from which it follows that <math>a^p \equiv a \pmod{p}</math>. Thus, we have another way to visualize the above combinatorial proof, by imagining the described transformation to be, in a sense, a rotation about the main diagonal of the hyp<br />
<br />
== Problems ==<br />
=== Introductory ===<br />
* Compute some examples, for example find <math>3^{31} \pmod{7}, 29^{25} \pmod{11}</math>, and <math>128^{129} \pmod{17}</math>, and check your answers by calculator where possible.<br />
<br />
* Let <math>k = 2008^2 + 2^{2008}</math>. What is the units digit of <math>k^2 + 2^k</math>? ([[2008 AMC 12A Problems/Problem 15]])<br />
<br />
* Find <math>2^{20} + 3^{30} + 4^{40} + 5^{50} + 6^{60}</math> mod <math>7</math>. ([http://www.artofproblemsolving.com/Forum/viewtopic.php?search_id=207352162&t=304326 Discussion]).<br />
<br />
=== Intermediate ===<br />
* One of Euler's conjectures was disproved in the 1960s by three American mathematicians when they showed there was a positive integer such that <math>133^5+110^5+84^5+27^5=n^5</math>. Find the value of <math>{n}</math>. ([[1989 AIME Problems/Problem 9|1989 AIME, #9]])<br><br><br />
<br />
*If <math>f(x) = x^{x^{x^x}}</math>, find the last two digits of <math>f(17) + f(18) + f(19) + f(20)</math>. ([https://pumac.princeton.edu/info/archives/pumac-2008/ 2008 PUMaC, NT A#4])<br />
<br />
=== Advanced ===<br />
*Is it true that if <math>p</math> is a prime number, and <math>k</math> is an integer <math>2 \le k \le p</math>, then the sum of the products of each <math>k</math>-element subset of <math>\{1, 2, \ldots, p\}</math> will be divisible by <math>p</math>? <br><br><br />
<br />
== Hints/Solutions ==<br />
Introductory: <br />
* Hint: For the first example, we have <math>3^6 \equiv 1 \pmod{7}</math> by FLT (Fermat's Little Theorem). It follows that <math>3^{31} = 3 \cdot 3^{30} = 3 \cdot \left(3^{6}\right)^5 \equiv 3 \cdot 1^5 \equiv 3 \pmod{7}</math>.<br />
<br />
Intermediate:<br />
* Solution (1989 AIME, 9) To solve this problem, it would be nice to know some information about the remainders <math>n</math> can have after division by certain numbers. By Fermat's Little Theorem, we know <math>{n^{5}}</math> is congruent to <math>n</math> [[modulo]] 5. Hence,<br><br />
<center><math>3 + 0 + 4 + 7 \equiv n\pmod{5}</math></center><br />
<center><math>4 \equiv n\pmod{5}</math></center><br />
<br><br><br />
:Continuing, we examine the equation modulo 3,<br />
<center><math>-1 + 1 + 0 + 0 \equiv n\pmod{3}</math></center><br />
<center><math>0 \equiv n\pmod{3}</math></center><br />
<br />
<br><br><br><br />
:Thus, <math>n</math> is divisible by three and leaves a remainder of four when divided by 5. It's obvious that <math>n>133</math>, so the only possibilities are <math>n = 144</math> or <math>n = 174</math>. It quickly becomes apparent that 174 is much too large, so <math>n</math> must be 144.<br />
<br />
Advanced:<br />
* Hint: try to establish the identity <math>x^{p} - x \equiv x(x-1)(x-2) \cdots (x-(p-1)) \pmod{p}</math>, and then apply [[Vieta's formulas]]. <br />
<br />
== See also ==<br />
* [[Number theory]]<br />
* [[Modular arithmetic]]<br />
* [[Euler's Totient Theorem]]<br />
* [[Order (group theory)]]<br />
<br />
[[Category:Number theory]]<br />
[[Category:Theorems]]</div>Vishwathganesanhttps://artofproblemsolving.com/wiki/index.php?title=Fermat%27s_Little_Theorem&diff=87129Fermat's Little Theorem2017-08-20T01:18:18Z<p>Vishwathganesan: Undo revision 87128 by Douzz (talk)</p>
<hr />
<div>'''Fermat's Little Theorem''' is highly useful in [[number theory]] for simplifying the computation of exponents in [[modular arithmetic]] (which students should study more at the introductory level if they have a hard time following the rest of this article). This theorem is credited to [[Pierre de Fermat]].<br />
<br />
<br />
== Statement ==<br />
<br />
If <math>{a}</math> is an [[integer]], <math>{p}</math> is a [[prime number]] and <math>{a}</math> is not [[divisibility|divisible]] by <math>{p}</math>, then <math>a^{p-1}\equiv 1 \pmod {p}</math>.<br />
<br />
A frequently used corollary of Fermat's Little Theorem is <math> a^p \equiv a \pmod {p}</math>. As you can see, it is derived by multipling both sides of the theorem by <math>a</math>. The restated form is nice because we no longer need to restrict ourselves to integers <math>{a}</math> not divisible by <math>{p}</math>.<br />
<br />
This theorem is a special case of [[Euler's Totient Theorem]], which states that if <math>a</math> and <math>n</math> are integers, then <math>a^{\phi(n)} \equiv 1 \pmod{n}</math>, where <math>\phi(n)</math> denotes [[Euler's totient function]]. In particular, <math>\phi(p) = p-1</math> for prime numbers <math>p</math>. In turn, this is a special case of [[Lagrange's Theorem]].<br />
<br />
In contest problems, Fermat's Little Theorem is often used in conjunction with the [[Chinese Remainder Theorem]] to simplify tedious calculations.<br />
<br />
== Proof ==<br />
We offer several proofs using different techniques to prove the statement <math>a^p \equiv a \pmod{p}</math>. If <math>\text{gcd}\,(a,p) = 1</math>, then we can cancel a factor of <math>a</math> from both sides and retrieve the first version of the theorem. <br />
<br />
=== Proof 1 (Induction) ===<br />
<br />
The most straightforward way to prove this theorem is by by applying the [[induction]] principle. We fix <math>p</math> as a prime number. The base case, <math>1^p \equiv 1 \pmod{p}</math>, is obviously true. Suppose the statement <math>a^p \equiv a \pmod{p}</math> is true. Then, by the [[binomial theorem]], <br />
<br />
<center><cmath>(a+1)^p = a^p + {p \choose 1} a^{p-1} + {p \choose 2} a^{p-2} + \cdots + {p \choose p-1} a + 1.</cmath></center><br />
<br />
Note that <math>p</math> divides into any binomial coefficient of the form <math>{p \choose k}</math> for <math>1 \le k \le p-1</math>. This follows by the definition of the binomial coefficient as <math>{p \choose k} = \frac{p!}{k! (p-k)!}</math>; since <math>p</math> is prime, then <math>p</math> divides the numerator, but not the denominator. <br />
<br />
Taken <math>\mod p</math>, all of the middle terms disappear, and we end up with <math>(a+1)^p \equiv a^p + 1 \pmod{p}</math>. Since we also know that <math>a^p \equiv a\pmod{p}</math>, then <math>(a+1)^p \equiv a+1 \pmod{p}</math>, as desired. <br />
<br />
=== Proof 2 (Inverses) ===<br />
<br />
Let <math>S = \{1,2,3,\cdots, p-1\}</math>. Then, we claim that the set <math>a \cdot S</math>, consisting of the product of the elements of <math>S</math> with <math>a</math>, taken modulo <math>p</math>, is simply a permutation of <math>S</math>. In other words, <br />
<br />
<center><cmath>S \equiv \{1a, 2a, \cdots, (p-1)a\} \pmod{p}.</cmath></center><br><br />
<br />
Clearly none of the <math>ia</math> for <math>1 \le i \le p-1</math> are divisible by <math>p</math>, so it suffices to show that all of the elements in <math>a \cdot S</math> are distinct. Suppose that <math>ai \equiv aj \pmod{p}</math> for <math>i \neq j</math>. Since <math>\text{gcd}\, (a,p) = 1</math>, by the cancellation rule, that reduces to <math>i \equiv j \pmod{p}</math>, which is a contradiction. <br />
<br />
Thus, <math>\mod{p}</math>, we have that the product of the elements of <math>S</math> is <br />
<br />
<center><cmath>1a \cdot 2a \cdots (p-1)a \equiv 1 \cdot 2 \cdots (p-1) \pmod{p}.</cmath></center> <br><br />
<br />
Cancelling the factors <math>1, 2, 3, \ldots, p-1</math> from both sides, we are left with the statement <math>a^{p-1} \equiv 1 \pmod{p}</math>.<br><br />
<br />
A similar version can be used to prove [[Euler's Totient Theorem]], if we let <math>S = \{\text{natural numbers relatively prime to and less than}\ n\}</math>.<br />
<br />
=== Proof 3 (Combinatorics) ===<br />
<center><asy> <br />
real r = 0.3, row1 = 3.5, row2 = 0, row3 = -3.5;<br />
void necklace(pair k, pen colors[]){<br />
draw(shift(k)*unitcircle); <br />
for(int i = 0; i < colors.length; ++i){<br />
pair p = k+expi(pi/2+2*pi*i/colors.length);<br />
fill(Circle(p,r),colors[i]);<br />
draw(Circle(p,r));<br />
}<br />
}<br />
<br />
pen BEADS1[] = {red,red,red},BEADS2[] = {blue,blue,blue},BEADS3[] = {red,red,blue},BEADS4[] = {blue,red,red},BEADS5[] = {red,blue,red},BEADS6[] = {blue,blue,red},BEADS7[] = {red,blue,blue},BEADS8[] = {blue,red,blue};<br />
necklace((-1.5,row1),BEADS1);necklace((1.5,row1),BEADS2);necklace((-2.5,row2),BEADS3);necklace((0,row2),BEADS4);necklace((2.5,row2),BEADS5);necklace((-2.5,row3),BEADS6);necklace((0,row3),BEADS7);necklace((2.5,row3),BEADS8);<br />
</asy><br> An illustration of the case <math>p=3,a=2</math>.<br></center><br />
<br />
Consider a necklace with <math>p</math> beads, each bead of which can be colored in <math>a</math> different ways. There are <math>a^p</math> ways to pick the colors of the beads. <math>a</math> of these are necklaces that consists of beads of the same color. Of the remaining necklaces, for each necklace, there are exactly <math>p-1</math> more necklaces that are rotationally equivalent to this necklace. It follows that <math>a^p-a</math> must be divisible by <math>p</math>. Written in another way, <math>a^p \equiv a \pmod{p}</math>.<br />
<br />
=== Proof 4 (Geometry) ===<br />
<center><asy><br />
void match(int i, int j){ <br />
draw(shift((i,j))*unitsquare,linewidth(1));<br />
draw(shift((j,i))*unitsquare,linewidth(1));<br />
draw((i+0.5,j+0.5)--(j+0.5,i+0.5),linewidth(2));<br />
}<br />
int n = 6;<br />
for(int i = 0; i < n; ++i){<br />
for(int j = 0; j < n; ++j)<br />
draw(shift((i,j))*unitsquare, linewidth(0.5));<br />
}<br />
draw((0,0)--(n,n),red+linewidth(2)); match(2,4); match(0,3);<br />
</asy>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<asy><br />
import three; currentprojection = perspective(3,-2,4);<br />
void match(int i, int j, int k){ <br />
draw(shift((i,j,k))*box((0,0,0),(1,1,1)),linewidth(1));<br />
draw(shift((k,i,j))*box((0,0,0),(1,1,1)),linewidth(1));<br />
draw(shift((j,k,i))*box((0,0,0),(1,1,1)),linewidth(1));<br />
draw((i+0.5,j+0.5,k+0.5)--(j+0.5,k+0.5,i+0.5)--(k+0.5,i+0.5,j+0.5)--cycle,linewidth(2));<br />
}<br />
int n = 4;<br />
for(int i = 0; i < n; ++i){<br />
for(int j = 0; j < n; ++j)<br />
for(int k = 0; k < n; ++k)<br />
draw(shift((i,j,k))*box((0,0,0),(1,1,1)), linewidth(0.5));<br />
}<br />
draw((0,0,0)--(n,n,n),red+linewidth(2));match(2,3,1); </asy>For <math>p=2,3</math> and <math>a=6,4</math>, respectively.</center><br />
We imbed a [[hypercube]] of side length <math>a</math> in <math>\mathbb{R}^p</math> (the <math>p</math>-th dimensional [[Euclidean space]]), such that the vertices of the hypercube are at <math>(\pm a/2,\pm a/2, \ldots, \pm a/2)</math>. A hypercube is essentially a cube, generalized to higher dimensions. This hypercube consists of <math>a^p</math> separate unit hypercubes, with centers consisting of the points <br />
<br />
<center><cmath>P(x_1, x_2, \ldots, x_n) = \left(a + \frac 12 - x_1, a + \frac 12 - x_2, \ldots, a + \frac 12 - x_p\right),</cmath></center><br><br />
<br />
where each <math>x_i</math> is an integer from <math>1</math> to <math>a</math>. Besides the <math>a</math> centers of the unit hypercubes in the main diagonal (from <math>(-a/2, -a/2, \ldots, -a/2)</math> to <math>(a/2, a/2, \ldots, a/2)</math>), the transformation carrying <br />
<br />
<cmath>P(x_1, x_2, \ldots, x_n) \mapsto P(x_2, x_3, \ldots, x_n, x_1)</cmath><br><br />
<br />
maps one unit hypercube to a distinct hypercube. Much like the combinatorial proof, this splits the non-main diagonal unit hypercubes into groups of size <math>\color{red}{\text{FUCK YOU!!}}</math>, from which it follows that <math>a^p \equiv a \pmod{p}</math>. Thus, we have another way to visualize the above combinatorial proof, by imagining the described transformation to be, in a sense, a rotation about the main diagonal of the hyp<br />
<br />
== Problems ==<br />
=== Introductory ===<br />
* Compute some examples, for example find <math>3^{31} \pmod{7}, 29^{25} \pmod{11}</math>, and <math>128^{129} \pmod{17}</math>, and check your answers by calculator where possible.<br />
<br />
* Let <math>k = 2008^2 + 2^{2008}</math>. What is the units digit of <math>k^2 + 2^k</math>? ([[2008 AMC 12A Problems/Problem 15]])<br />
<br />
* Find <math>2^{20} + 3^{30} + 4^{40} + 5^{50} + 6^{60}</math> mod <math>7</math>. ([http://www.artofproblemsolving.com/Forum/viewtopic.php?search_id=207352162&t=304326 Discussion]).<br />
<br />
=== Intermediate ===<br />
* One of Euler's conjectures was disproved in the 1960s by three American mathematicians when they showed there was a positive integer such that <math>133^5+110^5+84^5+27^5=n^5</math>. Find the value of <math>{n}</math>. ([[1989 AIME Problems/Problem 9|1989 AIME, #9]])<br><br><br />
<br />
*If <math>f(x) = x^{x^{x^x}}</math>, find the last two digits of <math>f(17) + f(18) + f(19) + f(20)</math>. ([https://pumac.princeton.edu/info/archives/pumac-2008/ 2008 PUMaC, NT A#4])<br />
<br />
=== Advanced ===<br />
*Is it true that if <math>p</math> is a prime number, and <math>k</math> is an integer <math>2 \le k \le p</math>, then the sum of the products of each <math>k</math>-element subset of <math>\{1, 2, \ldots, p\}</math> will be divisible by <math>p</math>? <br><br><br />
<br />
== Hints/Solutions ==<br />
Introductory: <br />
* Hint: For the first example, we have <math>3^6 \equiv 1 \pmod{7}</math> by FLT (Fermat's Little Theorem). It follows that <math>3^{31} = 3 \cdot 3^{30} = 3 \cdot \left(3^{6}\right)^5 \equiv 3 \cdot 1^5 \equiv 3 \pmod{7}</math>.<br />
<br />
Intermediate:<br />
* Solution (1989 AIME, 9) To solve this problem, it would be nice to know some information about the remainders <math>n</math> can have after division by certain numbers. By Fermat's Little Theorem, we know <math>{n^{5}}</math> is congruent to <math>n</math> [[modulo]] 5. Hence,<br><br />
<center><math>3 + 0 + 4 + 7 \equiv n\pmod{5}</math></center><br />
<center><math>4 \equiv n\pmod{5}</math></center><br />
<br><br><br />
:Continuing, we examine the equation modulo 3,<br />
<center><math>-1 + 1 + 0 + 0 \equiv n\pmod{3}</math></center><br />
<center><math>0 \equiv n\pmod{3}</math></center><br />
<br />
<br><br><br><br />
:Thus, <math>n</math> is divisible by three and leaves a remainder of four when divided by 5. It's obvious that <math>n>133</math>, so the only possibilities are <math>n = 144</math> or <math>n = 174</math>. It quickly becomes apparent that 174 is much too large, so <math>n</math> must be 144.<br />
<br />
Advanced:<br />
* Hint: try to establish the identity <math>x^{p} - x \equiv x(x-1)(x-2) \cdots (x-(p-1)) \pmod{p}</math>, and then apply [[Vieta's formulas]]. <br />
<br />
== See also ==<br />
* [[Number theory]]<br />
* [[Modular arithmetic]]<br />
* [[Euler's Totient Theorem]]<br />
* [[Order (group theory)]]<br />
<br />
[[Category:Number theory]]<br />
[[Category:Theorems]]</div>Vishwathganesanhttps://artofproblemsolving.com/wiki/index.php?title=2017_AIME_II_Problems&diff=848952017 AIME II Problems2017-03-23T16:51:40Z<p>Vishwathganesan: /* Problem 1 */</p>
<hr />
<div>{{AIME Problems|year=2017|n=II}}<br />
<br />
==Problem 1==<br />
Find the number of subsets of <math>\{1, 2, 3, 4, 5, 6, 7, 8\}</math> that are subsets of neither <math>\{1, 2, 3, 4, 5\}</math> nor <math>\{4, 5, 6, 7, 8\}</math>.<br />
<br />
[[2017 AIME II Problems/Problem 1 | Solution]]<br />
<br />
==Problem 2==<br />
Theams <math>T_1</math>, <math>T_2</math>, <math>T_3</math>, and <math>T_4</math> are in the playoffs. In the semifinal matches, <math>T_1</math> plays <math>T_4</math>, and <math>T_2</math> plays <math>T_3</math>. The winners of those two matches will play each other in the final match to determine the champion. When <math>T_i</math> plays <math>T_j</math>, the probability that <math>T_i</math> wins is <math>\frac{i}{i+j}</math>, and the outcomes of all the matches are independent. The probability that <math>T_4</math> will be the champion is <math>\frac{p}{q}</math>, where <math>p</math> and <math>q</math> are relatively prime positive integers. Find <math>p+q</math>.<br />
<br />
[[2017 AIME I Problems/Problem 2 | Solution]]<br />
<br />
==Problem 3==<br />
A triangle has vertices <math>A(0,0)</math>, <math>B(12,0)</math>, and <math>C(8,10)</math>. The probability that a randomly chosen point inside the triangle is closer to vertex <math>B</math> than to either vertex <math>A</math> or vertex <math>C</math> can be written as <math>\frac{p}{q}</math>, where <math>p</math> and <math>q</math> are relatively prime positive integers. Find <math>p+q</math>.<br />
<br />
[[2017 AIME I Problems/Problem 3 | Solution]]<br />
<br />
==Problem 4==<br />
Find the number of positive integers less than or equal to <math>2017</math> whose base-three representation contains no digit equal to <math>0</math>.<br />
<br />
[[2017 AIME I Problems/Problem 4 | Solution]]<br />
<br />
==Problem 5==<br />
A set contains four numbers. The six pairwise sums of distinct elements of the set, in no particular order, are <math>189</math>, <math>320</math>, <math>287</math>, <math>234</math>, <math>x</math>, and <math>y</math>. Find the greatest possible value of <math>x+y</math>.<br />
<br />
[[2017 AIME I Problems/Problem 5 | Solution]]<br />
<br />
==Problem 6==<br />
Find the sum of all positive integers <math>n</math> such that <math>\sqrt{n^2+85n+2017}</math> is an integer.<br />
<br />
[[2017 AIME I Problems/Problem 6 | Solution]]<br />
<br />
==Problem 7==<br />
Find the number of integer values of <math>k</math> in the closed interval <math>[-500,500]</math> for which the equation <math>\log(kx)=2\log(x+2)</math> has exactly one real solution.<br />
<br />
[[2017 AIME I Problems/Problem 7 | Solution]]<br />
<br />
==Problem 8==<br />
Find the number of positive integers <math>n</math> less than <math>2017</math> such that <cmath>1+n+\frac{n^2}{2!}+\frac{n^3}{3!}+\frac{n^4}{4!}+\frac{n^5}{5!}+\frac{n^6}{6!}</cmath> is an integer.<br />
<br />
[[2017 AIME I Problems/Problem 8 | Solution]]<br />
<br />
==Problem 9==<br />
A special deck of cards contains <math>49</math> cards, each labeled with a number from <math>1</math> to <math>7</math> and colored with one of seven solors. Each number-color combination appears on exactly one card. Sharon will select a set of eight cards from the deck at random. Given that she gets at least one card of each color and at least one cardf with each number, the probability that Sharon can discard one of her cards and <math>\textit{still}</math> have at least one card of each color and at least one card with each number if <math>\frac{p}{q}</math>, where <math>p</math> and <math>q</math> are relatively prime positive integers. Find <math>p+q</math>.<br />
<br />
[[2017 AIME I Problems/Problem 9 | Solution]]<br />
<br />
==Problem 10==<br />
Rectangle <math>ABCD</math> has side lengths <math>AB=84</math> and <math>AD=42</math>. Point <math>M</math> is the midpoint of <math>\overline{AD}</math>, point <math>N</math> is the trisection point of <math>\overline{AB}</math> closer to <math>A</math>, and point <math>O</math> is the intersection of <math>\overline{CM}</math> and <math>\overline{DN}</math>. Point <math>P</math> lies on the quadrilateral <math>BCON</math>, and <math>\overline{BP}</math> bisects the area of <math>BCON</math>. Find the area of <math>\triangle CDP</math>.<br />
<br />
[[2017 AIME I Problems/Problem 10 | Solution]]<br />
<br />
==Problem 11==<br />
Five towns are connected by a system of raods. There is exactly one road connecting each pair of towns. Find the number of ways there are to make all the roads one-way in such a way that it is still possible to get from any town to any other town using the roads (possibly passing through other towns on the way).<br />
<br />
[[2017 AIME I Problems/Problem 11 | Solution]]<br />
<br />
==Problem 12==<br />
Circle <math>C_0</math> has radius <math>1</math>, and the point <math>A_0</math> is a point on the circle. Circle <math>C_1</math> has radius <math>r<1</math> and is internally tangent to <math>C_0</math> at point <math>A_0</math>. Point <math>A_1</math> lies on circle <math>C_1</math> so that <math>A_1</math> is located <math>90^{\circ}</math> counterclockwise from <math>A_0</math> on <math>C_1</math>. Circle <math>C_2</math> has radius <math>r^2</math> and is internally tangent to <math>C_1</math> at point <math>A_1</math>. In this way a sequence of circles <math>C_1,C_2,C_3,\cdots</math> and a sequence of points on the circles <math>A_1,A_2,A_3,\cdots</math> are constructed, where circle <math>C_n</math> has radius <math>r^n</math> and is internally tangent to circle <math>C_{n-1}</math> at point <math>A_{n-1}</math>, and point <math>A_n</math> lies on <math>C_n</math> <math>90^{\circ}</math> counterclockwise from point <math>A_{n-1}</math>, as shown in the figure below. There is one point <math>B</math> inside all of these circles. When <math>r = \frac{11}{60}</math>, the distance from the center <math>C_0</math> to <math>B</math> is <math>\frac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m+n</math>.<br />
<br />
\usepackage{asymptote}<br />
\begin{figure}[h]<br />
\begin{asy}<br />
draw(Circle((0,0),125));<br />
draw(Circle((25,0),100));<br />
draw(Circle((25,20),80));<br />
draw(Circle((9,20),64));<br />
dot((125,0));<br />
label("<math>A_0</math>",(125,0),E);<br />
dot((25,100));<br />
label("<math>A_1</math>",(25,100),SE);<br />
dot((-55,20));<br />
label("<math>A_2</math>",(-55,20),E);<br />
\end{asy}<br />
\end{figure}<br />
<br />
[[2017 AIME I Problems/Problem 12 | Solution]]<br />
<br />
==Problem 13==<br />
For each integer <math>n\geq3</math>, let <math>f(n)</math> be the number of <math>3</math>-element subsets of the vertices of the regular <math>n</math>-gon that are the vertices of an isosceles triangle (including equilateral triangles). Find the sum of all values of <math>n</math> such that <math>f(n+1)=f(n)+78</math>.<br />
<br />
[[2017 AIME I Problems/Problem 13 | Solution]]<br />
<br />
==Problem 14==<br />
A <math>10\times10\times10</math> grid of points consists of all points in space of the form <math>(i,j,k)</math>, where <math>i</math>, <math>j</math>, and <math>k</math> are integers between <math>1</math> and <math>10</math>, inclusive. Find the number of different lines that contain exactly <math>8</math> of these points.<br />
<br />
[[2017 AIME I Problems/Problem 14 | Solution]]<br />
<br />
==Problem 15==<br />
Tetrahedron <math>ABCD</math> has <math>AD=BC=28</math>, <math>AC=BD=44</math>, and <math>AB=CD=52</math>. For any point <math>X</math> in space, define <math>f(X)=AX+BX+CX+DX</math>. The least possible value of <math>f(X)</math> can be expressed as <math>m\sqrt{n}</math>, where <math>m</math> and <math>n</math> are positive integers, and <math>n</math> is not divisible by the square of any prime. Find <math>m+n</math>.<br />
<br />
[[2017 AIME I Problems/Problem 15 | Solution]]</div>Vishwathganesanhttps://artofproblemsolving.com/wiki/index.php?title=2006_IMO_Problems/Problem_3&diff=698742006 IMO Problems/Problem 32015-04-09T00:30:43Z<p>Vishwathganesan: /* Problem */</p>
<hr />
<div>==Problem==<br />
Determine the least real number <math>M</math> such that the inequality <math> \left|ab\left(a^{2}-b^{2}\right)\right+bc\left(b^{2}-c^{2}\right)+ca\left(c^{2}-a^{2}\right)|\leq M\left(a^{2}+b^{2}+c^{2}\right)^{2} </math> holds for all real numbers <math>a,b</math> and <math>c</math><br />
<br />
==Solution==<br />
.</div>Vishwathganesan