2019 AIME II Problems/Problem 5

Problem

Four ambassadors and one advisor for each of them are to be seated at a round table with $12$ chairs numbered in order $1$ to $12$ . Each ambassador must sit in an even-numbered chair. Each advisor must sit in a chair adjacent to his or her ambassador. There are $N$ ways for the $8$ people to be seated at the table under these conditions. Find the remainder when $N$ is divided by $1000$ .

Solution

There are $4$ ambassadors and there are $6$ seats for them. So we consider the position of the blank seats. There are $15$ kinds of versions: If the two seats are adjacent to each other, there are $6$ options, and the ambassadors are sitting in four adjacent seats, and there are five seats that their advisors can sit. Choose any of them and the advisors’ seats are fixed, so there are $5$ kinds of solutions for the advisors to sit. And that’s a $6\cdot5$ if we don’t consider the order of the ambassadors. We can also get that if the blank seats are opposite, it will be $3\cdot9$ , if they are not adjacent and not opposite, it will be $6\cdot8$ . So the total is $24\cdot(6\cdot5+6\cdot8+3\cdot9)=2520$ And the remainder is $\boxed{520}$

Solution 2

File:Ambassador Table.png\200px In the diagram, the seats are numbered 1...12. Rather than picking seats for each person, however, each ambassador/assistant team picks a gap between the seats (A...L) and the ambassador sits in the odd seat while the assistant sits in the even seat. For example, if team 1 picks gap C then Ambassador 1 will sit in seat 3 while assistant 1 will sit in seat 2. No two teams can pick adjacent gaps. For example, if team 1 chooses gap C then team 2 cannot pick gaps B or D. In the diagram, the teams have picked gaps C, F, H and J. Note that the gap-gaps - distances between the chosen gaps - (in the diagram, 2, 1, 1, 4) must sum to 8. So, to get the number of seatings, we: 1. Choose a gap for team 1 ( $12$ options) 2. Choose 3 other gaps around the table with positive gap-gaps. The number of ways to do this is the number of ways to partition 8 with 4 positive integers. This is the same as partitioning 4 with 4 non-negative integers, and using stars-and-bars, this is $7 choose 3 = 35$ 3. Place the other 3 teams in the chosen gaps ( $6$ permutations) So the total is $12\cdot35\cdot6=2520$ And the remainder is $\boxed{520}$

2019 AIME II (Problems • Answer Key • Resources)
Preceded by Problem 4	Followed by Problem 6
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search

2019 AIME II Problems/Problem 5

Contents

Problem

Solution

Solution 2

See Also