2019 AIME II Problem 5

Below is the professionally curated solution for Problem 5 of the 2019 AIME II, from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2019 AIME II solutions, or check the answer key.

All of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:circular arrangementsarrangements with restrictionscasework

Difficulty rating: 2650

5.

Four ambassadors and one advisor for each of them are to be seated at a round table with 1212 chairs numbered in order 11 to 12.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 NN ways for the 88 people to be seated at the table under these conditions. Find the remainder when NN is divided by 1000.1000.

Solution:

The six even chairs form a cycle (chair 1212 is adjacent to chair 11), and each odd chair lies between two consecutive even chairs. The ambassadors occupy 44 of the 66 even chairs, and each advisor must take one of the two odd chairs flanking their ambassador, with all choices distinct. For a maximal block of kk consecutive occupied even chairs, the kk occupants choose among the k+1k + 1 odd chairs touching the block; recording each choice as left or right, a conflict occurs exactly when someone picks right and their neighbor picks left, so the valid patterns are the strings of LLs followed by RRs: k+1k + 1 of them.

Now case on the two empty even chairs among the six positions. If they are adjacent (66 ways), the occupied chairs form one block of 4,4, giving 55 patterns. If they are separated by one chair (66 ways), the blocks have sizes 11 and 3,3, giving 24=82 \cdot 4 = 8 patterns. If they are opposite (33 ways), the blocks have sizes 22 and 2,2, giving 33=93 \cdot 3 = 9 patterns. The number of seat configurations is 65+68+39=105.6 \cdot 5 + 6 \cdot 8 + 3 \cdot 9 = 105.

Finally, the four ambassador-advisor pairs can be assigned to the four chosen even chairs in 4!=244! = 24 ways, so N=10524=2520,N = 105 \cdot 24 = 2520, and the remainder modulo 10001000 is 520.520.

← Problem 4Full ExamProblem 6

Problem 5 in Other Years