Difference between revisions of "2019 AIME II Problems/Problem 5"

m (Solution 2)
(reworked the solution due to poor wording and lack of explanation in original)
 
Line 1: Line 1:
 
==Problem==
 
==Problem==
 
Four ambassadors and one advisor for each of them are to be seated at a round table with <math>12</math> chairs numbered in order <math>1</math> to <math>12</math>. Each ambassador must sit in an even-numbered chair. Each advisor must sit in a chair adjacent to his or her ambassador. There are <math>N</math> ways for the <math>8</math> people to be seated at the table under these conditions. Find the remainder when <math>N</math> is divided by <math>1000</math>.
 
Four ambassadors and one advisor for each of them are to be seated at a round table with <math>12</math> chairs numbered in order <math>1</math> to <math>12</math>. Each ambassador must sit in an even-numbered chair. Each advisor must sit in a chair adjacent to his or her ambassador. There are <math>N</math> ways for the <math>8</math> people to be seated at the table under these conditions. Find the remainder when <math>N</math> is divided by <math>1000</math>.
==Solution==
+
==Solution 1==
There are <math>4</math> ambassadors and there are <math>6</math> seats for them.
+
Let us first consider the <math>4</math> ambassadors and the <math>6</math> even-numbered chairs. If we consider only their relative positions, they can sit in one of <math>3</math> distinct ways: Such that the <math>2</math> empty even-numbered chairs are adjacent, such that they are separated by one occupied even-numbered chair, and such that they are opposite each other. For each way, there are <math>4!=24</math> ways to assign the <math>4</math> ambassadors to the <math>4</math> selected seats.
So we consider the position of the blank seats.
+
 
There are <math>15</math> kinds of versions:
+
In the first way, there are <math>6</math> distinct orientations. The <math>4</math> advisors can be placed in any of the <math>5</math> odd-numbered chairs adjacent to the ambassadors, and for each placement, there is exactly one way to assign them to the ambassadors. This means that there are <math>24\cdot6\cdot\binom{5}{4}=720</math> total seating arrangements for this way.
If the two seats are adjacent to each other, there are <math>6</math> 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 <math>5</math> kinds of solutions for the advisors to sit. And that’s a <math>6\cdot5</math> if we don’t consider the order of the ambassadors.
+
 
We can also get that if the blank seats are opposite, it will be <math>3\cdot9</math>, if they are not adjacent and not opposite, it will be <math>6\cdot8</math>.
+
In the second way, there are <math>6</math> distinct orientations. <math>3</math> advisors can be placed in any of the <math>4</math> chairs adjacent to the "chunk" of <math>3</math> ambassadors, and <math>1</math> advisor can be placed in either of the <math>2</math> chairs adjacent to the "lonely" ambassador. Once again, for each placement, there is exactly one way to assign the advisors to the ambassadors. This means that there are <math>24\cdot6\cdot\binom{4}{3}\cdot\binom{2}{1}=1152</math> total seating arrangements for this way.
So the total is <math>24\cdot(6\cdot5+6\cdot8+3\cdot9)=2520</math>
+
 
And the remainder is <math>\boxed{520}</math>
+
In the third way, there are <math>3</math> distinct orientations. For both "chunks" of <math>2</math> ambassadors, <math>2</math> advisors can be placed in any of the <math>3</math> chairs adjacent to them, and once again, there is exactly one way to assign them for each placement. This means that there are <math>24\cdot3\cdot\binom{3}{2}\cdot\binom{3}{2}=648</math> total seating arrangements for this way.
 +
 
 +
Totalling up the arrangements, there are <math>720+1152+648=2520</math> total ways to seat the people, and the remainer when <math>2520</math> is divided by <math>1000</math> is <math>\boxed{520}</math>. ~[[User:emerald_block|emerald_block]]
  
 
==Solution 2==
 
==Solution 2==

Latest revision as of 00:03, 4 June 2020

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 1

Let us first consider the $4$ ambassadors and the $6$ even-numbered chairs. If we consider only their relative positions, they can sit in one of $3$ distinct ways: Such that the $2$ empty even-numbered chairs are adjacent, such that they are separated by one occupied even-numbered chair, and such that they are opposite each other. For each way, there are $4!=24$ ways to assign the $4$ ambassadors to the $4$ selected seats.

In the first way, there are $6$ distinct orientations. The $4$ advisors can be placed in any of the $5$ odd-numbered chairs adjacent to the ambassadors, and for each placement, there is exactly one way to assign them to the ambassadors. This means that there are $24\cdot6\cdot\binom{5}{4}=720$ total seating arrangements for this way.

In the second way, there are $6$ distinct orientations. $3$ advisors can be placed in any of the $4$ chairs adjacent to the "chunk" of $3$ ambassadors, and $1$ advisor can be placed in either of the $2$ chairs adjacent to the "lonely" ambassador. Once again, for each placement, there is exactly one way to assign the advisors to the ambassadors. This means that there are $24\cdot6\cdot\binom{4}{3}\cdot\binom{2}{1}=1152$ total seating arrangements for this way.

In the third way, there are $3$ distinct orientations. For both "chunks" of $2$ ambassadors, $2$ advisors can be placed in any of the $3$ chairs adjacent to them, and once again, there is exactly one way to assign them for each placement. This means that there are $24\cdot3\cdot\binom{3}{2}\cdot\binom{3}{2}=648$ total seating arrangements for this way.

Totalling up the arrangements, there are $720+1152+648=2520$ total ways to seat the people, and the remainer when $2520$ is divided by $1000$ is $\boxed{520}$. ~emerald_block

Solution 2

                                         Ambassador Table.png

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 even seat while the assistant sits in the odd seat. For example, if team 1 picks gap C then Ambassador 1 will sit in seat 2 while assistant 1 will sit in seat 3. 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 $\dbinom{4+4-1}{4-1}=\dbinom{7}{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}$

Solution 3

There are $360\cdot16$ total ways to let everyone sit. However this may lead to advisors sitting in the same chair, leading to awkward situations. So we find how many ways this happens. There are 6 ways to choose which advisors end up sitting together, times 12 ways to find neighboring even seats and sitting down, 12 ways for the rest of the ambassador to sit, and 4 ways for their advisors to sit to get 3456 ways for this to happen. However we overcounted the case when two pairs of advisors run out of room to sit, where there are $6\cdot9\cdot4=216$ ways to happen. So 5760-3456+216=$2\boxed{520}$.

See Also

2019 AIME II (ProblemsAnswer KeyResources)
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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Invalid username
Login to AoPS