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 2: Stars-and-bars)
(Formatting)
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: Casework==
+
== Solution 1 (Casework) ==
  
 
Let's split the problem into a few cases:
 
Let's split the problem into a few cases:
Line 16: Line 17:
 
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>
 
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>
  
−
Answer: <math>9 + 252 + 1260 + 1260 + 126 = 2907</math>
+
We have <math>N = 9 + 252 + 1260 + 1260 + 126 = 2907</math>
  
−
<math>2907 \equiv 907 \pmod{1000} \Longrightarrow \boxed{907}</math>.
+
<math>2907 \equiv \boxed{907} \pmod{1000}
  
−
(Feel free to correct any format/latex problems)
+
~Mitsuihisashi14
  
−
~Mitsuihisashi14
+
== Solution 2 (Stars-and-bars) ==
−
~Small latex fixes by Marcus :)
 
  
−
== Solution 2: Stars-and-bars ==
+
Let </math>n<math> be the number of groups of adjacent people.
  
−
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.
  
−
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>.
  
−
Now, we use the [https://artofproblemsolving.com/wiki/index.php/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}$.
  
−
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} \ (\text{mod} \ 1000)</math>.
+
~ [{{SERVER}}/community/user/1096232 Pengu14]
  
−
~ [https://artofproblemsolving.com/community/user/1096232 Pengu14]
+
== See Also ==
  
−
==See also==
 
 
{{AIME box|year=2025|num-b=9|num-a=11|n=II}}
 
{{AIME box|year=2025|num-b=9|num-a=11|n=II}}
−
 
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 16:48, 18 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 (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 2 (Stars-and-bars) ==

Let$ (Error compiling LaTeX. Unknown error_msg)n$be the number of groups of adjacent people.

Clearly, there will be$ (Error compiling LaTeX. Unknown error_msg)8-n$groups with$2$people, and there are$\binom{n}{8-n}$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$ (Error compiling LaTeX. Unknown error_msg)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$ (Error compiling LaTeX. Unknown error_msg)\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=243122"