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"

(Formatting)
(fix)
Line 19: Line 19:
 
We have <math>N = 9 + 252 + 1260 + 1260 + 126 = 2907</math>
 
We have <math>N = 9 + 252 + 1260 + 1260 + 126 = 2907</math>
  
−
<math>2907 \equiv \boxed{907} \pmod{1000}
+
<math>2907 \equiv \boxed{907} \pmod{1000}</math>
  
 
~Mitsuihisashi14
 
~Mitsuihisashi14
Line 25: Line 25:
 
== Solution 2 (Stars-and-bars) ==
 
== 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 [[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} \pmod{1000}</math>.
  
−
~ [{{SERVER}}/community/user/1096232 Pengu14]
+
~[{{SERVER}}/community/user/1096232 Pengu14]
  
 
== See Also ==
 
== See Also ==

Revision as of 16:49, 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 $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=243123"