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 4 (Maximal Casework))
 
(33 intermediate revisions by 23 users not shown)
Line 2: Line 2:
  
 
==Problem==
 
==Problem==
−
The numbers <math>1, 2, 3, 4, 5</math> 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 <math>1</math> 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 <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>.  
 
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 <math>6, 7, 8,</math> and <math>9</math>. However, once we have found a set summing to <math>6</math>, we can choose everything else and obtain a set summing to <math>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>.  
+
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 <math>4</math> arrangements that satisfy these conditions. However, each of these is a reflection of another. We divide by <math>2</math> 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"