Difference between revisions of "2025 AIME II Problems/Problem 10"
(Created page with "== 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...") |
(→Solution) |
||
| 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 == | + | == Solution 1: Caseworks== |
| + | |||
| + | We split into few cases: | ||
| + | |||
| + | Case 1: 8 people are all by single: 8C0 * 9C1 = 9 | ||
| + | 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. | ||
| + | |||
| + | (Feel free to correct any format/latex problems) | ||
| + | |||
| + | ~Mitsuihisashi14 | ||
Revision as of 22:51, 13 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: Caseworks
We split into few cases:
Case 1: 8 people are all by single: 8C0 * 9C1 = 9 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.
(Feel free to correct any format/latex problems)
~Mitsuihisashi14
