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 "2025 AIME II Problems/Problem 10"

(→‎Solution 1 (Recursion))
(→‎Solution 1 (Recursion))
Line 18: Line 18:
  
 
<math>\textbf{Case 2: 01}</math>
 
<math>\textbf{Case 2: 01}</math>
 +
 +
Now the split string looks something like _ _ _ _ ... _ _ | 0 1 _ _ ... _ _ . The number of ways to choose the string to the left remains unchanged: <math>S(n-b, k-i)</math> ways. Similarly, it would seem that the number of ways to choose the remainder of the string on the right is <math>S(b-2, i-1)</math> (just as in the previous case but we've used up one of the <math>i</math> <math>1</math>'s already). However we're overcounting, since if the remainder of the string on the right starts with 1 1 0 _ _ ... it makes a valid string by itself, but together with the 0 1 at the start, it makes 0 1 1 1 0, which is not allowed. Therefore we subtract the number of ways that we start with 0 1 1 1 0: there are <math>b-5</math> spaces left and <math>i-3</math> <math>1</math>'s left to allocate, so we subtract <math>S(b-5, i-3)</math>. So the total in this case is <cmath>S(n-b,k-i) \cdot (S(b-2, i-1)-S(b-5, i-3))</cmath>
 +
 +
<math>\textbf{Case 3: 10}</math>
 +
  
 
   
 
   

Revision as of 01:58, 20 February 2025

Problem

Sixteen chairs are arranged in a row. Eight people each select a chair in which to sit so that no person sits next to two other people. Let $N$ be the number of subsets of $16$ chairs that could be selected. Find the remainder when $N$ is divided by $1000$.

Solution 1 (Recursion)

Notice that we can treat each chair as an empty space. If a person selects a chair, we fill in the corresponding space with a '$1$': otherwise, we fill in the corresponding space with a '$0$'. Since no person can sit to two other people (and two other people means having a person to your left and your right), that means that we can't have three people sitting in a row). So now the problem boils down to the following: we have a string of $0$'s and $1$'s of length $16$, $8$ of which will be $1$ and $8$ of which will be $0$. This string cannot have three consecutive $1$'s in a row. We need to find the number of ways to construct this string.

Let's try recursion. The motivation for recursion is that $16$ and $8$ are relatively big numbers (the upper bound is $16$ choose $8$ which is over $12000$!) Also, many problems involving strings and counting with restrictions like 'three in a row' can usually be solved by breaking it up into smaller problems.

Define $S(n,k)$ to be the number of ways to create a string of length $n$ with $k$ $1$'s and $n-k$ $0$'s such that we can't have three consecutive $1$'s. We need to find $S(16,8)$.

So now we're going to take our recursive step, which usually involves splitting the string into two smaller strings. Suppose we split the string into two strings of length $n-b$ and $b$. Also suppose that in the string of length $b$ there are $i$ $1$'s (which means that in the string of length $n-b$, there are $k-i$ $1$'s. Now consider the first two digits in the string of length $b$: we do casework on them.

$\textbf{Case 1: 00}$

In this case, we can imagine the string as _ _ _ _ ... _ _ | 0 0 _ _ ... _ _ where the vertical line | shows the split. To the left of the split, we can choose the string without constraints in $S(n-b, k-i)$ ways since there are $n-b$ spaces and $k-i$ $1$'s to place there. To the right of the $0$, there are $b-2$ spaces and we still have to place $i$ $1's$, so this can be done in $S(b-2,i)$ ways. Now choosing the left string and the right string are independent, so the number of ways in this case is \[S(n-b, k-i)S(b-2, i)\].

$\textbf{Case 2: 01}$

Now the split string looks something like _ _ _ _ ... _ _ | 0 1 _ _ ... _ _ . The number of ways to choose the string to the left remains unchanged: $S(n-b, k-i)$ ways. Similarly, it would seem that the number of ways to choose the remainder of the string on the right is $S(b-2, i-1)$ (just as in the previous case but we've used up one of the $i$ $1$'s already). However we're overcounting, since if the remainder of the string on the right starts with 1 1 0 _ _ ... it makes a valid string by itself, but together with the 0 1 at the start, it makes 0 1 1 1 0, which is not allowed. Therefore we subtract the number of ways that we start with 0 1 1 1 0: there are $b-5$ spaces left and $i-3$ $1$'s left to allocate, so we subtract $S(b-5, i-3)$. So the total in this case is \[S(n-b,k-i) \cdot (S(b-2, i-1)-S(b-5, i-3))\]

$\textbf{Case 3: 10}$







But where do we make the split? If we make the split too close to the end, we could end up having to make lots of computations: if we split the string into $15$ and $1$, we'll have to compute $S(15,8)$, $S(14,8)$, etc. which could end up being a lot of work. We want to minimize the number of computations to save time. If we split the string unequally, one side will be larger and that side will require more computations. Therefore, we split the string in half so we just need to compute values of $n$ less than $8$. Solution in progress

~KingRavi

Solution 2 (Casework)

Let's split the problem into a few cases:

Case 1: All $8$ people are sitting isolated (no person sits next to any of them): $^8C_0 \cdot ^9C_1 = 9$

Case 2: $6$ people are isolated, $2$ people sit next to each other (such that each person sits next to either $0$ or $1$ other person): $^7C_1 \cdot ^9C_2 = 7 \cdot 36 = 252$

Case 3: $4$ people are isolated, $2$ people sit next to each other and $2$ other people sit next to each other with the $2$ groups of $2$ people not sitting next to each other (so each person still sits next to either $0$ or $1$ other person): $^6C_2 \cdot ^9C_3 = 1260$

Case 4: $2$ people are isolated, $6$ people are split into $3$ groups of $2$ people, and no $2$ groups sit next to each other: $^5C_3 \cdot ^9C_4 = 10 \cdot 126 = 1260$

Case 5: $4$ groups of $2$, no groups are sitting next to each other: $^4C_4 \cdot ^9C_5 = 126$

We have $N = 9 + 252 + 1260 + 1260 + 126 = 2907$

$2907 \equiv \boxed{907} \pmod{1000}$

~Mitsuihisashi14

Solution 3 (Stars-and-bars)

Let $n$ be the number of groups of adjacent people.

Clearly, there will be $8-n$ groups with $2$ people, and there are $\binom{n}{8-n}$ ways to select these groups.

Now, we use the stars-and-bars technique to find the number of ways to distribute the $8$ remaining chairs around the $8$ people. Since the $n$ groups are separated, we must choose $n-1$ chairs to place in between beforehand, leaving $9-n$ chairs to distribute among $n+1$ spots. Using stars-and-bars, we find that the number of ways to do this is $\binom{9}{9-n}$.

Thus, the total number of arrangements is $\binom{n}{8-n} \binom{9}{9-n}$. Summing this from $n=4$ to $n=8$ yields $\sum_{n=4}^{8} \binom{n}{8-n} \binom{9}{9-n} = 2907 \equiv \boxed{907} \pmod{1000}$.

~Pengu14

See Also

2025 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 9 		Followed by
Problem 11
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=2025_AIME_II_Problems/Problem_10&oldid=243293"