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)
(→‎Solution 1 (Recursion))
 
(34 intermediate revisions by 7 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== 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 <math>N</math> be the number of subsets of <math>16</math> chairs that could be selected. Find the remainder when <math>N</math> is divided by <math>1000</math>.
 
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 <math>N</math> be the number of subsets of <math>16</math> chairs that could be selected. Find the remainder when <math>N</math> is divided by <math>1000</math>.
  
−
== Solution 1: Caseworks==
+
== 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 '<math>1</math>': otherwise, we fill in the corresponding space with a '<math>0</math>'. 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 <math>0</math>'s and <math>1</math>'s of length <math>16</math>, <math>8</math> of which will be <math>1</math> and <math>8</math> of which will be <math>0</math>. This string cannot have three consecutive <math>1</math>'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 <math>16</math> and <math>8</math> are relatively big numbers (the upper bound is <math>16</math> choose <math>8</math> which is over <math>12000</math>!) 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 <math>S(n,k)</math> to be the number of ways to create a string of length <math>n</math> with <math>k</math> <math>1</math>'s and <math>n-k</math> <math>0</math>'s such that we can't have three consecutive <math>1</math>'s. We need to find <math>S(16,8)</math>.
 +
 
 +
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 <math>n-b</math> and <math>b</math>. Also suppose that in the string of length <math>b</math> there are <math>i</math> <math>1</math>'s (which means that in the string of length <math>n-b</math>, there are <math>k-i</math> <math>1</math>'s. Now consider the first two digits in the string of length <math>b</math>: we do casework on them.
 +
 
 +
<math>\textbf{Case 1: 00}</math>
 +
 
 +
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 <math>S(n-b, k-i)</math> ways since there are <math>n-b</math> spaces and <math>k-i</math> <math>1</math>'s to place there. To the right of the <math>0</math>, there are <math>b-2</math> spaces and we still have to place <math>i</math> <math>1's</math>, so this can be done in <math>S(b-2,i)</math> ways. Now choosing the left string and the right string are independent, so the number of ways in this case is <cmath>S(n-b, k-i)S(b-2, i)</cmath>.
 +
 
 +
<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>
 +
 
 +
Now the split string looks something like _ _ _ _ ... _ _ | 1 0 _ _ ... _ _ . Now the number of ways to fill in the empty slots to the right is unconstrained as it's following a <math>0</math>: there are <math>b-2</math> spaces and <math>i-1</math> <math>1</math>'s to allocate, so this gives <math>S(b-2, i-1)</math> ways. Now for the left, we overcount just like in the previous case: filling <math>k-i</math> <math>1</math>'s in <math>n-b</math> slots can be done in <math>S(n-b, k-i)</math> ways. However any way ending with 0 1 1 violates the three <math>1</math>'s in a row rule since in the center we have 0 1 1 1 0. The number of violations is the number of ways to fill in the empty slots to the left of _ _ _ ... _ _ 0 1 1 |, which can be done in <math>S(n-b-3, k-i-2)</math> ways since we've already allocated <math>2</math> <math>1</math>'s and used up <math>3</math> spaces. Therefore the total in this case is:
 +
 
 +
<cmath>S(b-2, i-1) \cdot (S(n-b, k-i)-S(n-b-3, k-i-2))</cmath>
 +
 
 +
<math>\textbf{Case 4: 11}</math>
 +
 
 +
In this case, we have something like _ _ _ _ ... _ _ | 1 1 _ _ ... _ _ . Since we can't have three <math>1</math>'s in a row, we can automatically fill <math>0</math>'s in: _ _ _ _ ... _ 0 | 1 1 0 _ ... _ _ . Now the number of ways to fill in the spaces on the left is <math>S(n-b-1, k-i)</math> and the number of ways to fill in the spaces on the right is <math>S(b-3, i-2)</math>. So the number of ways for this case is
 +
 
 +
<cmath>S(n-b-1,k-i)S(b-3,i-2)</cmath>
 +
 
 +
 
 +
 
 +
Now that we've finished casework, note that <math>i</math> can be anything: at minimum <math>i</math> can be zero, meaning that the string on the right has <math>0</math> <math>1</math>'s, and at maximum <math>i</math> can be <math>b</math>: the string is filled with <math>1</math>'s. To encapsulate all of the cases of <math>i</math>, we sum over the values of <math>i</math>:
 +
 
 +
<cmath>S(n,k) = \sum_{i = 0}^{b} S(n-b, k-i)S(b-2, i) + S(n-b,k-i) \cdot (S(b-2, i-1)-S(b-5, i-3))</cmath>
 +
<cmath> + S(b-2, i-1) \cdot (S(n-b, k-i)-S(n-b-3, k-i-2)) + S(n-b-1,k-i)S(b-3,i-2) </cmath>
 +
 
 +
 
 +
This is our recurrence relationship. But where do we make the split? The above formula works for any <math>b</math>, but 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 <math>15</math> and <math>1</math>, we'll have to compute <math>S(15,8)</math>, <math>S(14,8)</math>, etc. which could end up being a lot of work. We want to choose the best <math>b</math> 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 <math>n</math> less than <math>8</math>.
 +
 
 +
So suppose <math>b = 8</math> and plug in <math>n=16</math>, <math>k=8</math>. Then the above recurrence relation becomes
 +
 
 +
<cmath>S(16,8) = \sum_{i = 0}^{8} S(8, 8-i)S(6, i) + S(8,8-i) \cdot (S(6, i-1)-S(3, i-3))</cmath>
 +
<cmath> + S(6, i-1) \cdot (S(8, 8-i)-S(5, 6-i)) + S(7,8-i)S(5,i-2) </cmath>
 +
 
 +
 
 +
Before we start with computations, let's state our base cases for recursion. Note that if <math>n<0</math> and <math> k = 0</math>, <math>S(n,k) = 1</math>. Otherwise if <math>n<0</math> or <math>k<0</math> or <math>k>n</math>, <math>S(n,k) = 0</math>. Also, <math>S(x,0) = 1</math>, <math>S(x,1) = x</math>, <math>S(x,2) = \binom{x}{2}</math>, <math>S(x,3) = \binom{x}{3}-x+2</math> (the last one subtracting <math>x-2</math> for the number of three <math>1</math>'s in a row possible). Finally, for other cases of <math>S(n,k)</math> we don't want to use the earlier large recursive formula since we'll have to break those into many small components. Instead, we modify the formula so that <math>b=2</math>. This should be fine as <math>n</math> has already been broken down to at most <math>8</math>, so these computations shouldn't balloon. Using <math>b=2</math>, we get <math>S(n,k) = S(n-2,k) + 2S(n-2,k-1) - S(n-5,k-3)+S(n-3,k-2)</math>.
 +
 
 +
 
 +
Let's start the computation through the earlier cases.
 +
 
 +
<math>\textbf{Case 1}</math>
 +
 
 +
<cmath>\sum_{i = 0}^{8} S(8,8-i)S(6,i) = \sum_{i = 2}^{4} S(8,8-i)S(6,i)</cmath>
 +
 
 +
This is because for <math>i = 5</math>, <math>S(6,5) = 0</math> since the best we can do without three in a row is 1 1 0 1 1 0, which is four <math>1</math>'s, and it's impossible to achieve <math>5</math> <math>1</math>'s without three back to back. Also if <math>i=5</math> makes <math>S(6,i)</math> <math>0</math>, then <math>i \geq 5</math> makes <math>S(6,i)</math> <math>0</math>. Similarly we can't fit <math>7</math> <math>1</math>'s in <math>8</math> slots without three back-to-back, so <math>i</math> can't be <math>0</math> or <math>1</math>. So <math>i</math> must go from <math>2</math> to <math>4</math>. In future cases, I'll skip the explanation of why we tighten our bounds on <math>i</math> since the reasoning is the same as here.
 +
 
 +
<cmath>\implies \sum_{i = 0}^{8} S(8,8-i)S(6,i) = S(8,6)S(6,2) + S(8,5)S(6,3) + S(8,4)S(6,4)</cmath>
 +
 
 +
Applying the modified recurrence relation for <math>b=2</math>, <math>S(8,6) = S(6,6) + 2S(6,5)-S(3,3)+S(5,4) = 0+0-0+S(5,4)</math>
 +
<math> = S(3,4)+2S(3,3)-S(0,1)+S(2,2) = 0+0-0+1 = 1</math>. Let's remember these for future computations: <math>S(8,6) = S(5,4) = 1</math>.
 +
 
 +
<math>S(8,5) = S(6,5)+2S(6,4)-S(3,2)+S(5,3) = 0+2S(6,4)-3+7</math>. <math>S(6,4) = S(4,4) + 2S(4,3)-S(1,1)+S(3,2) = 0+2 \cdot 2 - 1 + 3 = 6 \implies S(8,5) = 2 \cdot 6 + 4 = 16</math>. We'll remember <math>S(6,4) = 6</math>, <math>S(8,5) = 16</math>.
 +
 
 +
Lastly <math>S(8,4) = S(6,4) + 2S(6,3)-S(3,1)+S(5,2) = 6+2 \cdot 16 - 3 + 10 = 45</math>
 +
 
 +
Therefore <cmath>\sum_{i = 0}^{8} S(8,8-i)S(6,i) = S(8,6)S(6,2) + S(8,5)S(6,3) + S(8,4)S(6,4)</cmath>
 +
<cmath> = 1 \cdot 15 + 16 \cdot 16 + 45 \cdot 6 = 541</cmath>
 +
 
 +
 
 +
<math>\textbf{Cases 2 and 3}</math>
 +
 
 +
Rewrite <cmath>\sum_{i = 0}^{8} S(8,8-i) \cdot (S(6, i-1)-S(3, i-3)) + S(6, i-1) \cdot (S(8, 8-i)-S(5, 6-i))</cmath>
 +
<cmath> = \sum_{i = 0}^{8} 2S(8,8-i)S(6,i-1) - S(8,8-i)S(3,i-3) - S(6,i-1)S(5,6-i)</cmath>
 +
<cmath> = 2 \sum_{i=2}^{5} S(8,8-i)S(6,i-1) - \sum_{i=3}^{5} S(8,8-i)S(3,i-3) - \sum_{i=2}^{5} S(6,i-1)S(5,6-i)</cmath>
 +
 
 +
<math>\textbf{Case 2 and 3 a.}</math>
 +
 
 +
<cmath>\sum_{i=2}^{5} S(8,8-i)S(6,i-1) = S(8,6)S(6,1) + S(8,5)S(6,2) + S(8,4)S(6,3) + S(8,3)S(6,4)</cmath>
 +
<cmath> = 1 \cdot 6 + 16 \cdot 15 + 45 \cdot 16 + 50 \cdot 6 = 1266</cmath>
 +
 
 +
<math>\textbf{Case 2 and 3 b.}</math>
 +
 
 +
<cmath>\sum_{i=3}^{5} S(8,8-i)S(3,i-3) = S(8,5)S(3,0) + S(8,4)S(3,1)+S(8,3)S(3,2)</cmath>
 +
<cmath> = 16 \cdot 1 + 45 \cdot 3 + 50 \cdot 3 = 301</cmath>
 +
 
 +
<math>\textbf{Case 2 and 3 c.}</math>
  
−
We split into few cases:
+
<cmath>\sum_{i=2}^{5} S(6,i-1)S(5,6-i) = S(6,1)S(5,4) + S(6,2)S(5,3) + S(6,3)S(5,2) + S(6,4)S(5,1)</cmath>
 +
<cmath> = 6 \cdot 1 + 15 \cdot 7 + 16 \cdot 10 + 6 \cdot 5 = 301</cmath>
  
−
Case 1: 8 people are all by single: 8C0 * 9C1 = 9
+
Putting it all together, in this case we have
−
Case 2: 6 people are by single, 2 people sits next to each other (so each person sits next to either 0 or 1 other person): 7C1 * 9C2 = 7 * 36 = 252
 
−
Case 3: 4 people are by single, 2 people sits next to each other and 2 other people sits 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): 6C2 * 9C3 = 1260
 
−
Case 4: 2 people are by single, 6 people are split into 3 groups of 2 people, and no 2 groups sit next to each other: 5C3 * 9C4 = 10 * 126 = 1260
 
−
Case 5: 4 groups of 2, no groups are sitting next to each other: 4C4 * 9C5 = 126
 
  
−
Answer: 9 + 252 + 1260 + 1260 + 126 = 2907, so the answer is 907.
+
<cmath>\sum_{i = 0}^{8} S(8,8-i)S(6,i-1) = 2 \cdot 1266 - 301 - 301 = 2 \cdot 965 = 1930</cmath>
  
−
(Feel free to correct any format/latex problems)
+
<math>\textbf{Case 4}</math>
 +
 
 +
Finally, <cmath>\sum_{i=0}^{8} S(7,8-i)S(5,i-2) = \sum_{i=3}^{6} S(7,8-i)S(5,i-2)</cmath>
 +
<cmath> = S(7,5)S(5,1)+S(7,4)S(5,2)+S(7,3)S(5,3)+S(7,2)S(5,4)</cmath>
 +
 
 +
Now <math>S(7,5) = S(5,5)+2S(5,4)-S(2,2)+S(4,3) = 0+2-1+2 = 3</math> and
 +
<math>S(7,4) = S(5,4)+2S(5,3)-S(2,1)+S(4,2) = 1+2 \cdot 7 - 2 + 6 = 19</math>.
 +
 
 +
Therefore, <cmath>\sum_{i=0}^{8} S(7,8-i)S(5,i-2) = 3 \cdot 5 + 19 \cdot 10 + 30 \cdot 7 + 21 \cdot 1 = 436</cmath>
 +
 
 +
 
 +
 
 +
 
 +
Finally,
 +
 
 +
<cmath>S(16,8) = \sum_{i = 0}^{8} S(8, 8-i)S(6, i) + S(8,8-i) \cdot (S(6, i-1)-S(3, i-3))</cmath>
 +
<cmath> + S(6, i-1) \cdot (S(8, 8-i)-S(5, 6-i)) + S(7,8-i)S(5,i-2) </cmath>
 +
 
 +
<cmath> = \sum_{i = 2}^{4} S(8,8-i)S(6,i) + (2 \sum_{i=2}^{5} S(8,8-i)S(6,i-1) - \sum_{i=3}^{5} S(8,8-i)S(3,i-3) - \sum_{i=2}^{5} S(6,i-1)S(5,6-i)) + \sum_{i=3}^{6} S(7,8-i)S(5,i-2)</cmath>
 +
 
 +
<cmath> = 541 + 1930 + 436 = 2907</cmath>
 +
 
 +
Thus the answer is <cmath>\boxed{907}</cmath>
 +
 
 +
 
 +
 
 +
~KingRavi
 +
 
 +
== Solution 2 (Casework) ==
 +
 
 +
Let's split the problem into a few cases:
 +
 
 +
Case 1: All <math>8</math> people are sitting isolated (no person sits next to any of them): <math>^8C_0 \cdot ^9C_1 = 9</math>
 +
 
 +
Case 2: <math>6</math> people are isolated, <math>2</math> people sit next to each other (such that each person sits next to either <math>0</math> or <math>1</math> other person): <math>^7C_1 \cdot ^9C_2 = 7 \cdot 36 = 252</math>
 +
 
 +
Case 3: <math>4</math> people are isolated, <math>2</math> people sit next to each other and <math>2</math> other people sit next to each other with the <math>2</math> groups of <math>2</math> people not sitting next to each other (so each person still sits next to either <math>0</math> or <math>1</math> other person): <math>^6C_2 \cdot ^9C_3 = 1260</math>
 +
 
 +
Case 4: <math>2</math> people are isolated, <math>6</math> people are split into <math>3</math> groups of <math>2</math> people, and no <math>2</math> groups sit next to each other: <math>^5C_3 \cdot ^9C_4 = 10 \cdot 126 = 1260</math>
 +
 
 +
Case 5: <math>4</math> groups of <math>2</math>, no groups are sitting next to each other: <math>^4C_4 \cdot ^9C_5 = 126</math>
 +
 
 +
We have <math>N = 9 + 252 + 1260 + 1260 + 126 = 2907</math>
 +
 
 +
<math>2907 \equiv \boxed{907} \pmod{1000}</math>
  
 
~Mitsuihisashi14
 
~Mitsuihisashi14
 +
 +
== Solution 3 (Stars-and-bars) ==
 +
 +
Let <math>n</math> be the number of groups of adjacent people.
 +
 +
Clearly, there will be <math>8-n</math> groups with <math>2</math> people, and there are <math>\binom{n}{8-n}</math> ways to select these groups.
 +
 +
Now, we use the [[Ball-and-urn|stars-and-bars technique]] to find the number of ways to distribute the <math>8</math> remaining chairs around the <math>8</math> people. Since the <math>n</math> groups are separated, we must choose <math>n-1</math> chairs to place in between beforehand, leaving <math>9-n</math> chairs to distribute among <math>n+1</math> spots. Using stars-and-bars, we find that the number of ways to do this is <math>\binom{9}{9-n}</math>.
 +
 +
Thus, the total number of arrangements is <math>\binom{n}{8-n} \binom{9}{9-n}</math>. Summing this from <math>n=4</math> to <math>n=8</math> yields <math>\sum_{n=4}^{8} \binom{n}{8-n} \binom{9}{9-n} = 2907 \equiv \boxed{907} \pmod{1000}</math>.
 +
 +
~[{{SERVER}}/community/user/1096232 Pengu14]
 +
 +
== See Also ==
 +
 +
{{AIME box|year=2025|num-b=9|num-a=11|n=II}}
 +
{{MAA Notice}}

Latest revision as of 10:26, 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}$

Now the split string looks something like _ _ _ _ ... _ _ | 1 0 _ _ ... _ _ . Now the number of ways to fill in the empty slots to the right is unconstrained as it's following a $0$: there are $b-2$ spaces and $i-1$ $1$'s to allocate, so this gives $S(b-2, i-1)$ ways. Now for the left, we overcount just like in the previous case: filling $k-i$ $1$'s in $n-b$ slots can be done in $S(n-b, k-i)$ ways. However any way ending with 0 1 1 violates the three $1$'s in a row rule since in the center we have 0 1 1 1 0. The number of violations is the number of ways to fill in the empty slots to the left of _ _ _ ... _ _ 0 1 1 |, which can be done in $S(n-b-3, k-i-2)$ ways since we've already allocated $2$ $1$'s and used up $3$ spaces. Therefore the total in this case is:

\[S(b-2, i-1) \cdot (S(n-b, k-i)-S(n-b-3, k-i-2))\]

$\textbf{Case 4: 11}$

In this case, we have something like _ _ _ _ ... _ _ | 1 1 _ _ ... _ _ . Since we can't have three $1$'s in a row, we can automatically fill $0$'s in: _ _ _ _ ... _ 0 | 1 1 0 _ ... _ _ . Now the number of ways to fill in the spaces on the left is $S(n-b-1, k-i)$ and the number of ways to fill in the spaces on the right is $S(b-3, i-2)$. So the number of ways for this case is

\[S(n-b-1,k-i)S(b-3,i-2)\]


Now that we've finished casework, note that $i$ can be anything: at minimum $i$ can be zero, meaning that the string on the right has $0$ $1$'s, and at maximum $i$ can be $b$: the string is filled with $1$'s. To encapsulate all of the cases of $i$, we sum over the values of $i$:

\[S(n,k) = \sum_{i = 0}^{b} S(n-b, k-i)S(b-2, i) + S(n-b,k-i) \cdot (S(b-2, i-1)-S(b-5, i-3))\] \[+ S(b-2, i-1) \cdot (S(n-b, k-i)-S(n-b-3, k-i-2)) + S(n-b-1,k-i)S(b-3,i-2)\]


This is our recurrence relationship. But where do we make the split? The above formula works for any $b$, but 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 choose the best $b$ 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$.

So suppose $b = 8$ and plug in $n=16$, $k=8$. Then the above recurrence relation becomes

\[S(16,8) = \sum_{i = 0}^{8} S(8, 8-i)S(6, i) + S(8,8-i) \cdot (S(6, i-1)-S(3, i-3))\] \[+ S(6, i-1) \cdot (S(8, 8-i)-S(5, 6-i)) + S(7,8-i)S(5,i-2)\]


Before we start with computations, let's state our base cases for recursion. Note that if $n<0$ and $k = 0$, $S(n,k) = 1$. Otherwise if $n<0$ or $k<0$ or $k>n$, $S(n,k) = 0$. Also, $S(x,0) = 1$, $S(x,1) = x$, $S(x,2) = \binom{x}{2}$, $S(x,3) = \binom{x}{3}-x+2$ (the last one subtracting $x-2$ for the number of three $1$'s in a row possible). Finally, for other cases of $S(n,k)$ we don't want to use the earlier large recursive formula since we'll have to break those into many small components. Instead, we modify the formula so that $b=2$. This should be fine as $n$ has already been broken down to at most $8$, so these computations shouldn't balloon. Using $b=2$, we get $S(n,k) = S(n-2,k) + 2S(n-2,k-1) - S(n-5,k-3)+S(n-3,k-2)$.


Let's start the computation through the earlier cases.

$\textbf{Case 1}$

\[\sum_{i = 0}^{8} S(8,8-i)S(6,i) = \sum_{i = 2}^{4} S(8,8-i)S(6,i)\]

This is because for $i = 5$, $S(6,5) = 0$ since the best we can do without three in a row is 1 1 0 1 1 0, which is four $1$'s, and it's impossible to achieve $5$ $1$'s without three back to back. Also if $i=5$ makes $S(6,i)$ $0$, then $i \geq 5$ makes $S(6,i)$ $0$. Similarly we can't fit $7$ $1$'s in $8$ slots without three back-to-back, so $i$ can't be $0$ or $1$. So $i$ must go from $2$ to $4$. In future cases, I'll skip the explanation of why we tighten our bounds on $i$ since the reasoning is the same as here.

\[\implies \sum_{i = 0}^{8} S(8,8-i)S(6,i) = S(8,6)S(6,2) + S(8,5)S(6,3) + S(8,4)S(6,4)\]

Applying the modified recurrence relation for $b=2$, $S(8,6) = S(6,6) + 2S(6,5)-S(3,3)+S(5,4) = 0+0-0+S(5,4)$ $= S(3,4)+2S(3,3)-S(0,1)+S(2,2) = 0+0-0+1 = 1$. Let's remember these for future computations: $S(8,6) = S(5,4) = 1$.

$S(8,5) = S(6,5)+2S(6,4)-S(3,2)+S(5,3) = 0+2S(6,4)-3+7$. $S(6,4) = S(4,4) + 2S(4,3)-S(1,1)+S(3,2) = 0+2 \cdot 2 - 1 + 3 = 6 \implies S(8,5) = 2 \cdot 6 + 4 = 16$. We'll remember $S(6,4) = 6$, $S(8,5) = 16$.

Lastly $S(8,4) = S(6,4) + 2S(6,3)-S(3,1)+S(5,2) = 6+2 \cdot 16 - 3 + 10 = 45$

Therefore \[\sum_{i = 0}^{8} S(8,8-i)S(6,i) = S(8,6)S(6,2) + S(8,5)S(6,3) + S(8,4)S(6,4)\] \[= 1 \cdot 15 + 16 \cdot 16 + 45 \cdot 6 = 541\]


$\textbf{Cases 2 and 3}$

Rewrite \[\sum_{i = 0}^{8} S(8,8-i) \cdot (S(6, i-1)-S(3, i-3)) + S(6, i-1) \cdot (S(8, 8-i)-S(5, 6-i))\] \[= \sum_{i = 0}^{8} 2S(8,8-i)S(6,i-1) - S(8,8-i)S(3,i-3) - S(6,i-1)S(5,6-i)\] \[= 2 \sum_{i=2}^{5} S(8,8-i)S(6,i-1) - \sum_{i=3}^{5} S(8,8-i)S(3,i-3) - \sum_{i=2}^{5} S(6,i-1)S(5,6-i)\]

$\textbf{Case 2 and 3 a.}$

\[\sum_{i=2}^{5} S(8,8-i)S(6,i-1) = S(8,6)S(6,1) + S(8,5)S(6,2) + S(8,4)S(6,3) + S(8,3)S(6,4)\] \[= 1 \cdot 6 + 16 \cdot 15 + 45 \cdot 16 + 50 \cdot 6 = 1266\]

$\textbf{Case 2 and 3 b.}$

\[\sum_{i=3}^{5} S(8,8-i)S(3,i-3) = S(8,5)S(3,0) + S(8,4)S(3,1)+S(8,3)S(3,2)\] \[= 16 \cdot 1 + 45 \cdot 3 + 50 \cdot 3 = 301\]

$\textbf{Case 2 and 3 c.}$

\[\sum_{i=2}^{5} S(6,i-1)S(5,6-i) = S(6,1)S(5,4) + S(6,2)S(5,3) + S(6,3)S(5,2) + S(6,4)S(5,1)\] \[= 6 \cdot 1 + 15 \cdot 7 + 16 \cdot 10 + 6 \cdot 5 = 301\]

Putting it all together, in this case we have

\[\sum_{i = 0}^{8} S(8,8-i)S(6,i-1) = 2 \cdot 1266 - 301 - 301 = 2 \cdot 965 = 1930\]

$\textbf{Case 4}$

Finally, \[\sum_{i=0}^{8} S(7,8-i)S(5,i-2) = \sum_{i=3}^{6} S(7,8-i)S(5,i-2)\] \[= S(7,5)S(5,1)+S(7,4)S(5,2)+S(7,3)S(5,3)+S(7,2)S(5,4)\]

Now $S(7,5) = S(5,5)+2S(5,4)-S(2,2)+S(4,3) = 0+2-1+2 = 3$ and $S(7,4) = S(5,4)+2S(5,3)-S(2,1)+S(4,2) = 1+2 \cdot 7 - 2 + 6 = 19$.

Therefore, \[\sum_{i=0}^{8} S(7,8-i)S(5,i-2) = 3 \cdot 5 + 19 \cdot 10 + 30 \cdot 7 + 21 \cdot 1 = 436\]



Finally,

\[S(16,8) = \sum_{i = 0}^{8} S(8, 8-i)S(6, i) + S(8,8-i) \cdot (S(6, i-1)-S(3, i-3))\] \[+ S(6, i-1) \cdot (S(8, 8-i)-S(5, 6-i)) + S(7,8-i)S(5,i-2)\]

\[= \sum_{i = 2}^{4} S(8,8-i)S(6,i) + (2 \sum_{i=2}^{5} S(8,8-i)S(6,i-1) - \sum_{i=3}^{5} S(8,8-i)S(3,i-3) - \sum_{i=2}^{5} S(6,i-1)S(5,6-i)) + \sum_{i=3}^{6} S(7,8-i)S(5,i-2)\]

\[= 541 + 1930 + 436 = 2907\]

Thus the answer is \[\boxed{907}\]


~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=243333"