Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2024 AIME I Problems/Problem 11"

(Created blank page)
 
m (→‎Solution 1)
 
(19 intermediate revisions by 10 users not shown)
Line 1: Line 1:
 +
==Problem==
 +
Each vertex of a regular octagon is independently colored either red or blue with equal probability. The probability that the octagon can then be rotated so that all of the blue vertices end up at positions where there were originally red vertices is <math>\tfrac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. What is <math>m+n</math>?
  
 +
==Video Solution ==
 +
https://www.youtube.com/watch?v=Nf80-0Eo72E&t=4s&ab_channel=MegaMathChannel
 +
 +
==Solution 1==
 +
Notice that the question's condition mandates all blues to go to reds, but reds do not necessarily have to go to blue. Let us do casework on how many blues there are.
 +
 +
If there are no blues whatsoever, there is only one case. This case is valid, as all of the (zero) blues have gone to reds. (One could also view it as: the location of all the blues now were not previously red.) Thus, we have <math>1</math>.
 +
 +
If there is a single blue somewhere, there are <math>8</math> cases - where can the blue be? Each of these is valid.
 +
 +
If there are two blues, again, every case is valid, and there are <math>\dbinom82=28</math> cases.
 +
 +
If there are three blues, every case is again valid; there are <math>\dbinom83=56</math> such cases.
 +
 +
The case with four blues is trickier. Let us look at all possible subcases.
 +
 +
If all four are adjacent (as in the diagram below), it is obvious: we can simply reverse the diagram (rotate it by <math>4</math> units) to achieve the problem's condition. There are <math>8</math> possible ways to have <math>4</math> adjacent blues, so this subcase contributes <math>8</math>.
 +
<asy>
 +
import graph;
 +
 +
void oct11(int[] pts) {
 +
pair[] vertices = {(0,0),(1,0),(1.707,0.707),(1.707,1.707),(1,2.414),(0,2.414),(-0.707,1.707),(-0.707,0.707)};
 +
draw((0,0)--(1,0)--(1.707,0.707)--(1.707,1.707)--(1,2.414)--(0,2.414)--(-0.707,1.707)--(-0.707,0.707)--cycle);
 +
for (int i = 0; i < 8; i+=1) {
 +
if (pts[i] == 0) {
 +
dot(vertices[i], blue);
 +
}
 +
if (pts[i] == 1) {
 +
dot(vertices[i], red);
 +
}
 +
}
 +
};
 +
int[] sus = {0,0,0,0,1,1,1,1};
 +
oct11(sus);
 +
</asy>
 +
 +
If three are adjacent and one is one away (as shown in the diagram below), we can not rotate the diagram to satisfy the question. This subcase does not work.
 +
 +
<asy>
 +
import graph;
 +
 +
void oct11(int[] pts) {
 +
pair[] vertices = {(0,0),(1,0),(1.707,0.707),(1.707,1.707),(1,2.414),(0,2.414),(-0.707,1.707),(-0.707,0.707)};
 +
draw((0,0)--(1,0)--(1.707,0.707)--(1.707,1.707)--(1,2.414)--(0,2.414)--(-0.707,1.707)--(-0.707,0.707)--cycle);
 +
for (int i = 0; i < 8; i+=1) {
 +
if (pts[i] == 0) {
 +
dot(vertices[i], blue);
 +
}
 +
if (pts[i] == 1) {
 +
dot(vertices[i], red);
 +
}
 +
}
 +
};
 +
int[] sus = {0,0,0,1,0,1,1,1};
 +
oct11(sus);
 +
</asy>
 +
 +
If three are adjacent and one is two away, obviously it is not possible as there is nowhere for the three adjacent blues to go.
 +
 +
<asy>
 +
import graph;
 +
 +
void oct11(int[] pts) {
 +
pair[] vertices = {(0,0),(1,0),(1.707,0.707),(1.707,1.707),(1,2.414),(0,2.414),(-0.707,1.707),(-0.707,0.707)};
 +
draw((0,0)--(1,0)--(1.707,0.707)--(1.707,1.707)--(1,2.414)--(0,2.414)--(-0.707,1.707)--(-0.707,0.707)--cycle);
 +
for (int i = 0; i < 8; i+=1) {
 +
if (pts[i] == 0) {
 +
dot(vertices[i], blue);
 +
}
 +
if (pts[i] == 1) {
 +
dot(vertices[i], red);
 +
}
 +
}
 +
};
 +
int[] sus = {0,0,0,1,1,0,1,1};
 +
oct11(sus);
 +
</asy>
 +
 +
If there are two adjacent pairs that are <math>1</math> apart, it is not possible since we do not have anywhere to put the two pairs.
 +
 +
<asy>
 +
import graph;
 +
 +
void oct11(int[] pts) {
 +
pair[] vertices = {(0,0),(1,0),(1.707,0.707),(1.707,1.707),(1,2.414),(0,2.414),(-0.707,1.707),(-0.707,0.707)};
 +
draw((0,0)--(1,0)--(1.707,0.707)--(1.707,1.707)--(1,2.414)--(0,2.414)--(-0.707,1.707)--(-0.707,0.707)--cycle);
 +
for (int i = 0; i < 8; i+=1) {
 +
if (pts[i] == 0) {
 +
dot(vertices[i], blue);
 +
}
 +
if (pts[i] == 1) {
 +
dot(vertices[i], red);
 +
}
 +
}
 +
};
 +
int[] sus = {0,0,1,0,0,1,1,1};
 +
oct11(sus);
 +
</asy>
 +
 +
If there are two adjacent pairs that are <math>2</math> apart, all of these cases are possible as we can rotate the diagram by <math>2</math> vertices to work. There are <math>4</math> of these cases.
 +
 +
<asy>
 +
import graph;
 +
 +
void oct11(int[] pts) {
 +
pair[] vertices = {(0,0),(1,0),(1.707,0.707),(1.707,1.707),(1,2.414),(0,2.414),(-0.707,1.707),(-0.707,0.707)};
 +
draw((0,0)--(1,0)--(1.707,0.707)--(1.707,1.707)--(1,2.414)--(0,2.414)--(-0.707,1.707)--(-0.707,0.707)--cycle);
 +
for (int i = 0; i < 8; i+=1) {
 +
if (pts[i] == 0) {
 +
dot(vertices[i], blue);
 +
}
 +
if (pts[i] == 1) {
 +
dot(vertices[i], red);
 +
}
 +
}
 +
};
 +
int[] sus = {0,0,1,1,0,0,1,1};
 +
oct11(sus);
 +
</asy>
 +
 +
If there is one adjacent pair and there are two separate ones each a distance of <math>1</math> from the other, this case does not work.
 +
 +
<asy>
 +
import graph;
 +
 +
void oct11(int[] pts) {
 +
pair[] vertices = {(0,0),(1,0),(1.707,0.707),(1.707,1.707),(1,2.414),(0,2.414),(-0.707,1.707),(-0.707,0.707)};
 +
draw((0,0)--(1,0)--(1.707,0.707)--(1.707,1.707)--(1,2.414)--(0,2.414)--(-0.707,1.707)--(-0.707,0.707)--cycle);
 +
for (int i = 0; i < 8; i+=1) {
 +
if (pts[i] == 0) {
 +
dot(vertices[i], blue);
 +
}
 +
if (pts[i] == 1) {
 +
dot(vertices[i], red);
 +
}
 +
}
 +
};
 +
int[] sus = {0,0,1,0,1,0,1,1};
 +
oct11(sus);
 +
</asy>
 +
 +
If we have one adjacent pair and two separate ones that are <math>2</math> away from each other, we can flip the diagram by <math>4</math> vertices. There are <math>8</math> of these cases.
 +
 +
<asy>
 +
import graph;
 +
 +
void oct11(int[] pts) {
 +
pair[] vertices = {(0,0),(1,0),(1.707,0.707),(1.707,1.707),(1,2.414),(0,2.414),(-0.707,1.707),(-0.707,0.707)};
 +
draw((0,0)--(1,0)--(1.707,0.707)--(1.707,1.707)--(1,2.414)--(0,2.414)--(-0.707,1.707)--(-0.707,0.707)--cycle);
 +
for (int i = 0; i < 8; i+=1) {
 +
if (pts[i] == 0) {
 +
dot(vertices[i], blue);
 +
}
 +
if (pts[i] == 1) {
 +
dot(vertices[i], red);
 +
}
 +
}
 +
};
 +
int[] sus = {0,0,1,0,1,1,0,1};
 +
oct11(sus);
 +
</asy>
 +
 +
Finally, if the red and blues alternate, we can simply shift the diagram by a single vertex to satisfy the question. Thus, all of these cases work, and we have <math>2</math> subcases.
 +
 +
<asy>
 +
import graph;
 +
 +
void oct11(int[] pts) {
 +
pair[] vertices = {(0,0),(1,0),(1.707,0.707),(1.707,1.707),(1,2.414),(0,2.414),(-0.707,1.707),(-0.707,0.707)};
 +
draw((0,0)--(1,0)--(1.707,0.707)--(1.707,1.707)--(1,2.414)--(0,2.414)--(-0.707,1.707)--(-0.707,0.707)--cycle);
 +
for (int i = 0; i < 8; i+=1) {
 +
if (pts[i] == 0) {
 +
dot(vertices[i], blue);
 +
}
 +
if (pts[i] == 1) {
 +
dot(vertices[i], red);
 +
}
 +
}
 +
};
 +
int[] sus = {0,1,0,1,0,1,0,1};
 +
oct11(sus);
 +
</asy>
 +
 +
There can not be more than <math>4</math> blues, so we are done.
 +
 +
Our total is <math>1+8+28+56+8+4+8+2=115</math>. There are <math>2^8=256</math> possible colorings, so we have <math>\dfrac{115}{256}</math> and our answer is <math>115+256=\boxed{371}</math>.
 +
 +
~Technodoggo
 +
 +
==Solution 2==
 +
 +
Let <math>r</math> be the number of red vertices and <math>b</math> be the number of blue vertices, where <math>r+b=8</math>. By the Pigeonhole Principle, <math>r\geq{b} \Longrightarrow b\leq4</math> if a configuration is valid.
 +
 +
We claim that if <math>b\leq3</math>, then any configuration is valid. We attempt to prove by the following:
 +
 +
If there are <cmath>b\in{0,1,2}</cmath> vertices, then intuitively any configuration is valid. For <math>b=3</math>, we do cases:
 +
 +
If all the vertices in <math>b</math> are non-adjacent, then simply rotating once in any direction suffices. If there are <math>2</math> adjacent vertices, then WLOG let us create a set <math>\{b_1,b_2,r_1\cdots\}</math> where the third <math>b_3</math> is somewhere later in the set. If we assign the set as <math>\{1,2,3,4,5,6,7,8\}</math> and <math>b_3\leq4</math>, then intuitively, rotating it <math>4</math> will suffice. If <math>b_3=5</math>, then rotating it by 2 will suffice. Consider any other <math>b_3>5</math> as simply a mirror to a configuration of the cases.
 +
 +
Therefore, if <math>b\leq3</math>, then there are <math>\sum_{i=0}^{3}{\binom{8}{i}}=93</math> ways. We do count the [i]degenerate[/i] case.
 +
 +
Now if <math>b=4</math>, we do casework on the number of adjacent vertices.
 +
0 adjacent: <math>\{b_1,r_1,b_2,r_2\cdots{r_4}\}</math>. There are 4 axes of symmetry so there are only <math>\frac{8}{4}=2</math> rotations of this configuration.
 +
 +
1 adjacent: WLOG <math>\{b_1,b_2\cdots{b_3}\cdots{b_4}\}</math> where <math>b_4\neq{8}</math>. Listing out the cases and trying, we get that <math>b_3=4</math> and <math>b_4=7</math> is the only configuration. There are <math>8</math> ways to choose <math>b_1</math> and <math>b_2</math> and the rest is set, so there are <math>8</math> ways.
 +
 +
2 adjacent: We can have WLOG <math>\{b_1,b_2\cdots{b_3},b_4\}</math> or <math>\{b_1,b_2,b_3\cdots\}</math> where <math>b_4\neq{8}</math>. The former yields the case <math>b_3=5</math> and <math>b_4=6</math> by simply rotating it 2 times. The latter yields none. There are 2 axes of symmetry so there are <math>\frac{8}{2}=4</math> configurations.
 +
 +
3 adjacent: WLOG <math>\{b_1,b_2,b_3,b_4\cdots\}</math> which intuitively works. There are <math>8</math> configurations here as <math>b_1</math> can is unique.
 +
 +
In total, <math>b=4</math> yields <math>2+8+4+8=22</math> configurations.
 +
 +
There are <math>22+93=115</math> configurations in total. There are <math>2^8=256</math> total cases, so the probability is <math>\frac{115}{256}</math>. Adding them up, we get <math>115+256=\boxed{371}</math>.
 +
 +
==Video Solution==
 +
https://youtu.be/QnOatg7af7s
 +
 +
==See also==
 +
{{AIME box|year=2024|n=I|num-b=10|num-a=12}}
 +
 +
{{MAA Notice}}

Latest revision as of 21:23, 26 November 2024

Problem

Each vertex of a regular octagon is independently colored either red or blue with equal probability. The probability that the octagon can then be rotated so that all of the blue vertices end up at positions where there were originally red vertices is $\tfrac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. What is $m+n$?

Video Solution

https://www.youtube.com/watch?v=Nf80-0Eo72E&t=4s&ab_channel=MegaMathChannel

Solution 1

Notice that the question's condition mandates all blues to go to reds, but reds do not necessarily have to go to blue. Let us do casework on how many blues there are.

If there are no blues whatsoever, there is only one case. This case is valid, as all of the (zero) blues have gone to reds. (One could also view it as: the location of all the blues now were not previously red.) Thus, we have $1$.

If there is a single blue somewhere, there are $8$ cases - where can the blue be? Each of these is valid.

If there are two blues, again, every case is valid, and there are $\dbinom82=28$ cases.

If there are three blues, every case is again valid; there are $\dbinom83=56$ such cases.

The case with four blues is trickier. Let us look at all possible subcases.

If all four are adjacent (as in the diagram below), it is obvious: we can simply reverse the diagram (rotate it by $4$ units) to achieve the problem's condition. There are $8$ possible ways to have $4$ adjacent blues, so this subcase contributes $8$. [asy] import graph; void oct11(int[] pts) { pair[] vertices = {(0,0),(1,0),(1.707,0.707),(1.707,1.707),(1,2.414),(0,2.414),(-0.707,1.707),(-0.707,0.707)}; draw((0,0)--(1,0)--(1.707,0.707)--(1.707,1.707)--(1,2.414)--(0,2.414)--(-0.707,1.707)--(-0.707,0.707)--cycle); for (int i = 0; i < 8; i+=1) { if (pts[i] == 0) { dot(vertices[i], blue); } if (pts[i] == 1) { dot(vertices[i], red); } } }; int[] sus = {0,0,0,0,1,1,1,1}; oct11(sus); [/asy]

If three are adjacent and one is one away (as shown in the diagram below), we can not rotate the diagram to satisfy the question. This subcase does not work.

[asy] import graph; void oct11(int[] pts) { pair[] vertices = {(0,0),(1,0),(1.707,0.707),(1.707,1.707),(1,2.414),(0,2.414),(-0.707,1.707),(-0.707,0.707)}; draw((0,0)--(1,0)--(1.707,0.707)--(1.707,1.707)--(1,2.414)--(0,2.414)--(-0.707,1.707)--(-0.707,0.707)--cycle); for (int i = 0; i < 8; i+=1) { if (pts[i] == 0) { dot(vertices[i], blue); } if (pts[i] == 1) { dot(vertices[i], red); } } }; int[] sus = {0,0,0,1,0,1,1,1}; oct11(sus); [/asy]

If three are adjacent and one is two away, obviously it is not possible as there is nowhere for the three adjacent blues to go.

[asy] import graph; void oct11(int[] pts) { pair[] vertices = {(0,0),(1,0),(1.707,0.707),(1.707,1.707),(1,2.414),(0,2.414),(-0.707,1.707),(-0.707,0.707)}; draw((0,0)--(1,0)--(1.707,0.707)--(1.707,1.707)--(1,2.414)--(0,2.414)--(-0.707,1.707)--(-0.707,0.707)--cycle); for (int i = 0; i < 8; i+=1) { if (pts[i] == 0) { dot(vertices[i], blue); } if (pts[i] == 1) { dot(vertices[i], red); } } }; int[] sus = {0,0,0,1,1,0,1,1}; oct11(sus); [/asy]

If there are two adjacent pairs that are $1$ apart, it is not possible since we do not have anywhere to put the two pairs.

[asy] import graph; void oct11(int[] pts) { pair[] vertices = {(0,0),(1,0),(1.707,0.707),(1.707,1.707),(1,2.414),(0,2.414),(-0.707,1.707),(-0.707,0.707)}; draw((0,0)--(1,0)--(1.707,0.707)--(1.707,1.707)--(1,2.414)--(0,2.414)--(-0.707,1.707)--(-0.707,0.707)--cycle); for (int i = 0; i < 8; i+=1) { if (pts[i] == 0) { dot(vertices[i], blue); } if (pts[i] == 1) { dot(vertices[i], red); } } }; int[] sus = {0,0,1,0,0,1,1,1}; oct11(sus); [/asy]

If there are two adjacent pairs that are $2$ apart, all of these cases are possible as we can rotate the diagram by $2$ vertices to work. There are $4$ of these cases.

[asy] import graph; void oct11(int[] pts) { pair[] vertices = {(0,0),(1,0),(1.707,0.707),(1.707,1.707),(1,2.414),(0,2.414),(-0.707,1.707),(-0.707,0.707)}; draw((0,0)--(1,0)--(1.707,0.707)--(1.707,1.707)--(1,2.414)--(0,2.414)--(-0.707,1.707)--(-0.707,0.707)--cycle); for (int i = 0; i < 8; i+=1) { if (pts[i] == 0) { dot(vertices[i], blue); } if (pts[i] == 1) { dot(vertices[i], red); } } }; int[] sus = {0,0,1,1,0,0,1,1}; oct11(sus); [/asy]

If there is one adjacent pair and there are two separate ones each a distance of $1$ from the other, this case does not work.

[asy] import graph; void oct11(int[] pts) { pair[] vertices = {(0,0),(1,0),(1.707,0.707),(1.707,1.707),(1,2.414),(0,2.414),(-0.707,1.707),(-0.707,0.707)}; draw((0,0)--(1,0)--(1.707,0.707)--(1.707,1.707)--(1,2.414)--(0,2.414)--(-0.707,1.707)--(-0.707,0.707)--cycle); for (int i = 0; i < 8; i+=1) { if (pts[i] == 0) { dot(vertices[i], blue); } if (pts[i] == 1) { dot(vertices[i], red); } } }; int[] sus = {0,0,1,0,1,0,1,1}; oct11(sus); [/asy]

If we have one adjacent pair and two separate ones that are $2$ away from each other, we can flip the diagram by $4$ vertices. There are $8$ of these cases.

[asy] import graph; void oct11(int[] pts) { pair[] vertices = {(0,0),(1,0),(1.707,0.707),(1.707,1.707),(1,2.414),(0,2.414),(-0.707,1.707),(-0.707,0.707)}; draw((0,0)--(1,0)--(1.707,0.707)--(1.707,1.707)--(1,2.414)--(0,2.414)--(-0.707,1.707)--(-0.707,0.707)--cycle); for (int i = 0; i < 8; i+=1) { if (pts[i] == 0) { dot(vertices[i], blue); } if (pts[i] == 1) { dot(vertices[i], red); } } }; int[] sus = {0,0,1,0,1,1,0,1}; oct11(sus); [/asy]

Finally, if the red and blues alternate, we can simply shift the diagram by a single vertex to satisfy the question. Thus, all of these cases work, and we have $2$ subcases.

[asy] import graph; void oct11(int[] pts) { pair[] vertices = {(0,0),(1,0),(1.707,0.707),(1.707,1.707),(1,2.414),(0,2.414),(-0.707,1.707),(-0.707,0.707)}; draw((0,0)--(1,0)--(1.707,0.707)--(1.707,1.707)--(1,2.414)--(0,2.414)--(-0.707,1.707)--(-0.707,0.707)--cycle); for (int i = 0; i < 8; i+=1) { if (pts[i] == 0) { dot(vertices[i], blue); } if (pts[i] == 1) { dot(vertices[i], red); } } }; int[] sus = {0,1,0,1,0,1,0,1}; oct11(sus); [/asy]

There can not be more than $4$ blues, so we are done.

Our total is $1+8+28+56+8+4+8+2=115$. There are $2^8=256$ possible colorings, so we have $\dfrac{115}{256}$ and our answer is $115+256=\boxed{371}$.

~Technodoggo

Solution 2

Let $r$ be the number of red vertices and $b$ be the number of blue vertices, where $r+b=8$. By the Pigeonhole Principle, $r\geq{b} \Longrightarrow b\leq4$ if a configuration is valid.

We claim that if $b\leq3$, then any configuration is valid. We attempt to prove by the following:

If there are \[b\in{0,1,2}\] vertices, then intuitively any configuration is valid. For $b=3$, we do cases:

If all the vertices in $b$ are non-adjacent, then simply rotating once in any direction suffices. If there are $2$ adjacent vertices, then WLOG let us create a set $\{b_1,b_2,r_1\cdots\}$ where the third $b_3$ is somewhere later in the set. If we assign the set as $\{1,2,3,4,5,6,7,8\}$ and $b_3\leq4$, then intuitively, rotating it $4$ will suffice. If $b_3=5$, then rotating it by 2 will suffice. Consider any other $b_3>5$ as simply a mirror to a configuration of the cases.

Therefore, if $b\leq3$, then there are $\sum_{i=0}^{3}{\binom{8}{i}}=93$ ways. We do count the [i]degenerate[/i] case.

Now if $b=4$, we do casework on the number of adjacent vertices. 0 adjacent: $\{b_1,r_1,b_2,r_2\cdots{r_4}\}$. There are 4 axes of symmetry so there are only $\frac{8}{4}=2$ rotations of this configuration.

1 adjacent: WLOG $\{b_1,b_2\cdots{b_3}\cdots{b_4}\}$ where $b_4\neq{8}$. Listing out the cases and trying, we get that $b_3=4$ and $b_4=7$ is the only configuration. There are $8$ ways to choose $b_1$ and $b_2$ and the rest is set, so there are $8$ ways.

2 adjacent: We can have WLOG $\{b_1,b_2\cdots{b_3},b_4\}$ or $\{b_1,b_2,b_3\cdots\}$ where $b_4\neq{8}$. The former yields the case $b_3=5$ and $b_4=6$ by simply rotating it 2 times. The latter yields none. There are 2 axes of symmetry so there are $\frac{8}{2}=4$ configurations.

3 adjacent: WLOG $\{b_1,b_2,b_3,b_4\cdots\}$ which intuitively works. There are $8$ configurations here as $b_1$ can is unique.

In total, $b=4$ yields $2+8+4+8=22$ configurations.

There are $22+93=115$ configurations in total. There are $2^8=256$ total cases, so the probability is $\frac{115}{256}$. Adding them up, we get $115+256=\boxed{371}$.

Video Solution

https://youtu.be/QnOatg7af7s

See also

2024 AIME I (Problems • Answer Key • Resources)
Preceded by
Problem 10 		Followed by
Problem 12
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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2024_AIME_I_Problems/Problem_11&oldid=235662"