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 "2014 AMC 10B Problems/Problem 24"

(→‎Solution)
(→‎Solution 4 (Maximal Casework))
 
(35 intermediate revisions by 24 users not shown)
Line 2: Line 2:
  
 
==Problem==
 
==Problem==
−
The numbers 1, 2, 3, 4, 5 are to be arranged in a circle. An arrangement is <math>bad</math> if it is not true that for every <math>n</math> from <math>1</math> to <math>15</math> one can find a subset of the numbers that appear consecutively on the circle that sum to <math>n</math>. Arrangements that differ only by a rotation or a reflection are considered the same. How many different bad arrangements are there?
+
The numbers <math>1, 2, 3, 4, 5</math> are to be arranged in a circle. An arrangement is <math>\textit{bad}</math> if it is not true that for every <math>n</math> from <math>1</math> to <math>15</math> one can find a subset of the numbers that appear consecutively on the circle that sum to <math>n</math>. Arrangements that differ only by a rotation or a reflection are considered the same. How many different bad arrangements are there?
  
 
<math> \textbf {(A) } 1 \qquad \textbf {(B) } 2 \qquad \textbf {(C) } 3 \qquad \textbf {(D) } 4 \qquad \textbf {(E) } 5 </math>
 
<math> \textbf {(A) } 1 \qquad \textbf {(B) } 2 \qquad \textbf {(C) } 3 \qquad \textbf {(D) } 4 \qquad \textbf {(E) } 5 </math>
 +
.
  
−
==Solution==
+
==Solution 1==
  
−
We see that there are <math>5!</math> total ways to arrange the numbers. However, we can always rotate these numbers so that, for example, the number 1 is always at the top of the circle. Thus, there are only <math>4!</math> ways under rotation, which is not difficult to list out. We systematically list out all <math>24</math> cases.  
+
We see that there are <math>5!</math> total ways to arrange the numbers. However, we can always rotate these numbers so that, for example, the number <math>1</math> is always at the top of the circle. Thus, there are only <math>4!</math> ways under rotation. Every case has exactly <math>1</math> reflection, so that gives us only <math>4!/2</math>, or <math>12</math> cases, which is not difficult to list out. We systematically list out all <math>12</math> cases.  
  
−
Now, we must examine if they satisfy the conditions. We can see that by choosing one number at a time, we can always obtain subsets with sums 1, 2, 3, 4, and 5. By choosing the full circle, we can obtain 15. By choosing everything except for 1, 2, 3, 4, and 5, we can obtain subsets with sums of 10, 11, 12, 13, and 14.  
+
Now, we must examine if they satisfy the conditions. We can see that by choosing one number at a time, we can always obtain subsets with sums <math>1, 2, 3, 4,</math> and <math>5</math>. By choosing the full circle, we can obtain <math>15</math>. By choosing everything except for <math>1, 2, 3, 4,</math> and <math>5</math>, we can obtain subsets with sums of <math>10, 11, 12, 13,</math> and <math>14</math>.  
  
−
This means that we now only need to check for 6, 7, 8, and 9. However, once we have found a set summing to 6, we can choose everything else and obtain a set summing to 9, and similarly for 7 and 8. Thus, we only need to check each case for whether or not we can obtain 6 or 7.  
+
This means that we now only need to check for <math>6, 7, 8,</math> and <math>9</math>. However, once we have found a set summing to <math>6</math>, we can choose all remaining numbers and obtain a set summing to <math>15-6=9</math>, and similarly for <math>7</math> and <math>8</math>. Thus, we only need to check each case for whether or not we can obtain <math>6</math> or <math>7</math>.  
  
−
We find that there are only 4 arrangements that satisfy these conditions. However, each of these is a reflection of another. We divide by 2 for these reflections to obtain a final answer of <math>\boxed{\textbf {(B) }2}</math>.
+
We can make <math>6</math> by having <math>4, 2</math>, or <math>3, 2, 1</math>, or <math>5, 1</math>. We can start with the group of three. To separate <math>3, 2, 1</math> from each other, they must be grouped two together and one separate, like this.
 +
 
 +
<asy>
 +
draw(circle((0, 0), 5));
 +
pair O, A, B, C, D, E;
 +
O=origin;
 +
A=(0, 5);
 +
B=rotate(72)*A;
 +
C=rotate(144)*A;
 +
D=rotate(216)*A;
 +
E=rotate(288)*A;
 +
label("$x$", A, N);
 +
label("$y$", C, SW);
 +
label("$z$", D, SE);
 +
</asy>
 +
 
 +
Now, we note that <math>x</math> is next to both blank spots, so we can't have a number from one of the pairs. So since we can't have <math>1</math>, because it is part of the <math>5, 1</math> pair, and we can't have <math>2</math> there, because it's part of the <math>4, 2</math> pair, we must have <math>3</math> inserted into the <math>x</math> spot. We can insert <math>1</math> and <math>2</math> in <math>y</math> and <math>z</math> interchangeably, since reflections are considered the same.
 +
 
 +
<asy>
 +
draw(circle((0, 0), 5));
 +
pair O, A, B, C, D, E;
 +
O=origin;
 +
A=(0, 5);
 +
B=rotate(72)*A;
 +
C=rotate(144)*A;
 +
D=rotate(216)*A;
 +
E=rotate(288)*A;
 +
label("$3$", A, N);
 +
label("$2$", C, SW);
 +
label("$1$", D, SE);
 +
</asy>
 +
 
 +
We have <math>4</math> and <math>5</math> left to insert. We can't place the <math>4</math> next to the <math>2</math> or the <math>5</math> next to the <math>1</math>, so we must place <math>4</math> next to the <math>1</math> and <math>5</math> next to the <math>2</math>.
 +
 
 +
<asy>
 +
draw(circle((0, 0), 5));
 +
pair O, A, B, C, D, E;
 +
O=origin;
 +
A=(0, 5);
 +
B=rotate(72)*A;
 +
C=rotate(144)*A;
 +
D=rotate(216)*A;
 +
E=rotate(288)*A;
 +
label("$3$", A, N);
 +
label("$5$", B, NW);
 +
label("$2$", C, SW);
 +
label("$1$", D, SE);
 +
label("$4$", E, NE);
 +
</asy>
 +
 
 +
This is the only solution to make <math>6</math> "bad."
 +
 
 +
Next we move on to <math>7</math>, which can be made by <math>3, 4</math>, or <math>5, 2</math>, or <math>4, 2, 1</math>. We do this the same way as before. We start with the three group. Since we can't have <math>4</math> or <math>2</math> in the top slot, we must have one there, and <math>4</math> and <math>2</math> are next to each other on the bottom. When we have <math>3</math> and <math>5</math> left to insert, we place them such that we don't have the two pairs adjacent.
 +
 
 +
<asy>
 +
draw(circle((0, 0), 5));
 +
pair O, A, B, C, D, E;
 +
O=origin;
 +
A=(0, 5);
 +
B=rotate(72)*A;
 +
C=rotate(144)*A;
 +
D=rotate(216)*A;
 +
E=rotate(288)*A;
 +
label("$1$", A, N);
 +
label("$3$", B, NW);
 +
label("$2$", C, SW);
 +
label("$4$", D, SE);
 +
label("$5$", E, NE);
 +
</asy>
 +
 
 +
This is the only solution to make <math>7</math> "bad."
 +
 
 +
We've covered all needed cases, and the two examples we found are distinct, therefore the answer is <math>\boxed{\textbf {(B) }2}</math>.
 +
 
 +
==Solution 2==
 +
Note that any ordering satisfies the following numbers:
 +
 
 +
<math>1</math> through <math>5:</math> choose the number
 +
 
 +
<math>10</math> through <math>14:</math> choose all numbers excluding a specific one (such as <math>1, 2, 3, 4</math> in some order for <math>10</math>)
 +
 
 +
<math>15:</math> choose all the numbers.
 +
 
 +
Now, the pairs <math>7, 8</math> and <math>6, 9</math> are the same cases, since if a sequence satisfies a number, we can choose all the remaining numbers to make the other number. (<math>1, 2, 3</math> for <math>6</math>, then <math>4, 5</math> for <math>9</math>.)
 +
 
 +
Thus, we have two cases, whether a sequence doesn't make <math>6</math> or whether a sequence doesn't make <math>7.</math>
 +
 
 +
<math>6</math> can be made by <math>(1,2,3), (1, 5), (2, 4).</math> We can put <math>1, 2, 3</math> around the circle. <math>4</math> and <math>5</math> now need to go in <math>2</math> of the <math>3</math> spots in between <math>1, 2, 3.</math> Also keeping in mind the other two ways to make <math>6,</math> <math>4</math> has to go in the spot opposite of <math>2</math> and <math>5</math> has to go in the spot opposite of <math>1.</math> Thus the only ordering that works is <math>1, 4, 3, 5, 2</math> (ignore rotations and reflections).
 +
 
 +
Similarly, for the case with <math>7,</math> the only ordering that works is <math>1, 5, 4, 3, 2</math> with gives the answer of <math>\mathbf{(B) }2.</math>
 +
 
 +
==Solution 3 (Minimal Casework)==
 +
Note that <math>\{1,2,3,4,5,10,11,12,13,14,15\}</math> will always be there. Thus, we need to prevent either the <math>(6,9)</math> or the <math>(7,8)</math> pair. We consider the neighbors of 5.
 +
 
 +
Case 1: No 7s. Then we have <math>1-5-4</math>, and the neighbor of 4 cannot be 3 so the full config must be <math>3-1-5-4-2</math>.
 +
 
 +
Case 2: No 6s. Then we have <math>2-5-3</math>, and the neighbor of 2 cannot be 4, so the full config must be <math>1-2-5-3-4</math>.
 +
 
 +
Both of these are bad, and they're the only bads, so the answer is <math>\textbf{(B)} \text{ }2</math>.
 +
 
 +
==Solution 4 (Maximal Casework)==
 +
Like all previous solutions, we only need to find an arrangement where a sum of <math>6</math> or <math>7</math> isn't achievable. Reflections and rotations are considered the same, so there are actually only <math>\frac{5!}{5} \cdot \frac{1}{2} = 12</math> distinct arrangements. We can simply draw all <math>12</math> arrangements and cross out the ones that aren't bad, leaving us with <math>\boxed{2}</math> bad arrangements.
 +
 
 +
==Video Solution by icematrix==
 +
https://youtu.be/45TQEV8OjRk
  
 
==See Also==
 
==See Also==

Latest revision as of 20:24, 3 November 2024

The following problem is from both the 2014 AMC 12B #18 and 2014 AMC 10B #24, so both problems redirect to this page.

Problem

The numbers $1, 2, 3, 4, 5$ are to be arranged in a circle. An arrangement is $\textit{bad}$ if it is not true that for every $n$ from $1$ to $15$ one can find a subset of the numbers that appear consecutively on the circle that sum to $n$. Arrangements that differ only by a rotation or a reflection are considered the same. How many different bad arrangements are there?

$\textbf {(A) } 1 \qquad \textbf {(B) } 2 \qquad \textbf {(C) } 3 \qquad \textbf {(D) } 4 \qquad \textbf {(E) } 5$ .

Solution 1

We see that there are $5!$ total ways to arrange the numbers. However, we can always rotate these numbers so that, for example, the number $1$ is always at the top of the circle. Thus, there are only $4!$ ways under rotation. Every case has exactly $1$ reflection, so that gives us only $4!/2$, or $12$ cases, which is not difficult to list out. We systematically list out all $12$ cases.

Now, we must examine if they satisfy the conditions. We can see that by choosing one number at a time, we can always obtain subsets with sums $1, 2, 3, 4,$ and $5$. By choosing the full circle, we can obtain $15$. By choosing everything except for $1, 2, 3, 4,$ and $5$, we can obtain subsets with sums of $10, 11, 12, 13,$ and $14$.

This means that we now only need to check for $6, 7, 8,$ and $9$. However, once we have found a set summing to $6$, we can choose all remaining numbers and obtain a set summing to $15-6=9$, and similarly for $7$ and $8$. Thus, we only need to check each case for whether or not we can obtain $6$ or $7$.

We can make $6$ by having $4, 2$, or $3, 2, 1$, or $5, 1$. We can start with the group of three. To separate $3, 2, 1$ from each other, they must be grouped two together and one separate, like this.

[asy] draw(circle((0, 0), 5)); pair O, A, B, C, D, E; O=origin; A=(0, 5); B=rotate(72)*A; C=rotate(144)*A; D=rotate(216)*A; E=rotate(288)*A; label("$x$", A, N); label("$y$", C, SW); label("$z$", D, SE); [/asy]

Now, we note that $x$ is next to both blank spots, so we can't have a number from one of the pairs. So since we can't have $1$, because it is part of the $5, 1$ pair, and we can't have $2$ there, because it's part of the $4, 2$ pair, we must have $3$ inserted into the $x$ spot. We can insert $1$ and $2$ in $y$ and $z$ interchangeably, since reflections are considered the same.

[asy] draw(circle((0, 0), 5)); pair O, A, B, C, D, E; O=origin; A=(0, 5); B=rotate(72)*A; C=rotate(144)*A; D=rotate(216)*A; E=rotate(288)*A; label("$3$", A, N); label("$2$", C, SW); label("$1$", D, SE); [/asy]

We have $4$ and $5$ left to insert. We can't place the $4$ next to the $2$ or the $5$ next to the $1$, so we must place $4$ next to the $1$ and $5$ next to the $2$.

[asy] draw(circle((0, 0), 5)); pair O, A, B, C, D, E; O=origin; A=(0, 5); B=rotate(72)*A; C=rotate(144)*A; D=rotate(216)*A; E=rotate(288)*A; label("$3$", A, N); label("$5$", B, NW); label("$2$", C, SW); label("$1$", D, SE); label("$4$", E, NE); [/asy]

This is the only solution to make $6$ "bad."

Next we move on to $7$, which can be made by $3, 4$, or $5, 2$, or $4, 2, 1$. We do this the same way as before. We start with the three group. Since we can't have $4$ or $2$ in the top slot, we must have one there, and $4$ and $2$ are next to each other on the bottom. When we have $3$ and $5$ left to insert, we place them such that we don't have the two pairs adjacent.

[asy] draw(circle((0, 0), 5)); pair O, A, B, C, D, E; O=origin; A=(0, 5); B=rotate(72)*A; C=rotate(144)*A; D=rotate(216)*A; E=rotate(288)*A; label("$1$", A, N); label("$3$", B, NW); label("$2$", C, SW); label("$4$", D, SE); label("$5$", E, NE); [/asy]

This is the only solution to make $7$ "bad."

We've covered all needed cases, and the two examples we found are distinct, therefore the answer is $\boxed{\textbf {(B) }2}$.

Solution 2

Note that any ordering satisfies the following numbers:

$1$ through $5:$ choose the number

$10$ through $14:$ choose all numbers excluding a specific one (such as $1, 2, 3, 4$ in some order for $10$)

$15:$ choose all the numbers.

Now, the pairs $7, 8$ and $6, 9$ are the same cases, since if a sequence satisfies a number, we can choose all the remaining numbers to make the other number. ($1, 2, 3$ for $6$, then $4, 5$ for $9$.)

Thus, we have two cases, whether a sequence doesn't make $6$ or whether a sequence doesn't make $7.$

$6$ can be made by $(1,2,3), (1, 5), (2, 4).$ We can put $1, 2, 3$ around the circle. $4$ and $5$ now need to go in $2$ of the $3$ spots in between $1, 2, 3.$ Also keeping in mind the other two ways to make $6,$ $4$ has to go in the spot opposite of $2$ and $5$ has to go in the spot opposite of $1.$ Thus the only ordering that works is $1, 4, 3, 5, 2$ (ignore rotations and reflections).

Similarly, for the case with $7,$ the only ordering that works is $1, 5, 4, 3, 2$ with gives the answer of $\mathbf{(B) }2.$

Solution 3 (Minimal Casework)

Note that $\{1,2,3,4,5,10,11,12,13,14,15\}$ will always be there. Thus, we need to prevent either the $(6,9)$ or the $(7,8)$ pair. We consider the neighbors of 5.

Case 1: No 7s. Then we have $1-5-4$, and the neighbor of 4 cannot be 3 so the full config must be $3-1-5-4-2$.

Case 2: No 6s. Then we have $2-5-3$, and the neighbor of 2 cannot be 4, so the full config must be $1-2-5-3-4$.

Both of these are bad, and they're the only bads, so the answer is $\textbf{(B)} \text{ }2$.

Solution 4 (Maximal Casework)

Like all previous solutions, we only need to find an arrangement where a sum of $6$ or $7$ isn't achievable. Reflections and rotations are considered the same, so there are actually only $\frac{5!}{5} \cdot \frac{1}{2} = 12$ distinct arrangements. We can simply draw all $12$ arrangements and cross out the ones that aren't bad, leaving us with $\boxed{2}$ bad arrangements.

Video Solution by icematrix

https://youtu.be/45TQEV8OjRk

See Also

2014 AMC 10B (Problems • Answer Key • Resources)
Preceded by
Problem 23 		Followed by
Problem 25
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 10 Problems and Solutions
2014 AMC 12B (Problems • Answer Key • Resources)
Preceded by
Problem 17 		Followed by
Problem 19
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 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=2014_AMC_10B_Problems/Problem_24&oldid=231436"