2014 AMC 10B Problems/Problem 24

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 are to be arranged in a circle. An arrangement is if it is not true that for every from to one can find a subset of the numbers that appear consecutively on the circle that sum to . Arrangements that differ only by a rotation or a reflection are considered the same. How many different bad arrangements are there?

.

Solution 1

We see that there are total ways to arrange the numbers. However, we can always rotate these numbers so that, for example, the number is always at the top of the circle. Thus, there are only ways under rotation. Every case has exactly reflection, so that gives us only , or cases, which is not difficult to list out. We systematically list out all 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 and . By choosing the full circle, we can obtain . By choosing everything except for and , we can obtain subsets with sums of and .

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

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

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

We have and left to insert. We can't place the next to the or the next to the , so we must place next to the and next to the .

This is the only solution to make "bad."

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

This is the only solution to make "bad."

We've covered all needed cases, and the two examples we found are distinct, therefore the answer is .

Solution 2 (Complex Compliments)

We can use a clever approach for this problem by finding out how many non-adjacency's exist and subtracting it by the total configurations.

The formula \( C_n(A) = \frac{n}{k} \binom{n-k-1}{k-1} \) represents the Circular Gap Theorem, a crucial formula for finding out how many compliment cases exist where we want \( k \) values to not be adjacent from \( n \) total values.

Considering reflections and rotations are practically the same, we see that we have \( (n-1)!/2 \), \( n=5 \) ways = \( 4!/2 = 24/2 = 12 \) total configurations.

Now, we do some casework. Notice that we have \( n=5 \) values. Our \( k \in \{1,2,3,4,5\} \). We see that the values \( k \in \{3, 4, 5\} \) don't work as they make \( \binom{n-k-1}{k-1} \) invalid (3 gives \( 5-3-1 \choose 3-1 \) = \( 1 \choose 2 \) which doesn't exist, 4 gives \( 0 \choose 3 \) which doesn't exist, and 5 gives \( -1 \choose 4 \) which obviously doesn't exist).

We solve for \( k \in \{1,2\} \). When \( k \in 1 \), we get \( C_n(A) = \frac{5}{1} \binom{5-1-1}{1-1} = 5(1) = 5 \) cases and when \( k \in 2 \), we get \( C_n(A) = \frac{5}{2} \binom{5-2-1}{2-1} = \frac{5}{2}(2) = 5 \). The total cases that lead to a good sum is \( 5+5=10 \).

The answer isn't 10 however, because the theorem finds the compliments of the values, so the number of compliments is 10. We need to find the bad cases, which is \( 12 - 10 \) or

~Pinotation

Circular Gap Theorem Simplification

It is also helpful to note \( C_n(A) = \frac{n}{k} \binom{n-k-1}{k-1} \) = \( \binom{n}{2k} \).

~Pinotation

Solution 3

Note that any ordering satisfies the following numbers:

through choose the number

through choose all numbers excluding a specific one (such as in some order for )

choose all the numbers.

Now, the pairs and are the same cases, since if a sequence satisfies a number, we can choose all the remaining numbers to make the other number. ( for , then for .)

Thus, we have two cases, whether a sequence doesn't make or whether a sequence doesn't make

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

Similarly, for the case with the only ordering that works is with gives the answer of

Solution 4 (Minimal Casework)

Note that will always be there. Thus, we need to prevent either the or the pair. We consider the neighbors of 5.

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

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

Both of these are bad, and they're the only bads, so the answer is .

Solution 5 (Maximal Casework)

Like all previous solutions, we only need to find an arrangement where a sum of or isn't achievable. Reflections and rotations are considered the same, so there are actually only distinct arrangements. We can simply draw all arrangements and cross out the ones that aren't bad, leaving us with bad arrangements.

Video Solution by icematrix

https://youtu.be/45TQEV8OjRk

See Also

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions.