Difference between revisions of "2025 AIME II Problems/Problem 10"
m (minor LaTeX/readability changes) |
|||
| Line 2: | Line 2: | ||
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: | + | == Solution 1: Casework== |
| − | + | Let's split the problem into a few cases: | |
| − | Case 1: 8 people are | + | 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: 6 people are | + | 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: 4 people are | + | 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: 2 people are | + | 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: 4 groups of 2, no groups are sitting next to each other: | + | 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: 9 + 252 + 1260 + 1260 + 126 = 2907 | + | Answer: <math>9 + 252 + 1260 + 1260 + 126 = 2907</math> |
| + | |||
| + | <math>2907</math> (mod 1000) = <math>\boxed{907}</math>. | ||
(Feel free to correct any format/latex problems) | (Feel free to correct any format/latex problems) | ||
Revision as of 23:17, 14 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 
be the number of subsets of 
chairs that could be selected. Find the remainder when is divided by 
.
Solution 1: Casework
Let's split the problem into a few cases:
Case 1: All 
people are sitting isolated (no person sits next to any of them): 
Case 2: 
people are isolated, 
people sit next to each other (such that each person sits next to either 
or 
other person): 
Case 3: 
people are isolated, people sit next to each other and other people sit next to each other with the groups of people not sitting next to each other (so each person still sits next to either or other person): 
Case 4: people are isolated, people are split into 
groups of people, and no groups sit next to each other: 
Case 5: groups of , no groups are sitting next to each other: 
Answer: 
(mod 1000) = 
.
(Feel free to correct any format/latex problems)
~Mitsuihisashi14
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. 
