2009 AIME I Problem 10

Below is the professionally curated solution for Problem 10 of the 2009 AIME I, from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2009 AIME I 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:arrangements with restrictionspartitions and compositionsstars and bars

Difficulty rating: 2990

10.

The Annual Interplanetary Mathematics Examination (AIME) is written by a committee of five Martians, five Venusians, and five Earthlings. At meetings, committee members sit at a round table with chairs numbered from 11 to 1515 in clockwise order. Committee rules state that a Martian must occupy chair 11 and an Earthling must occupy chair 15.15. Furthermore, no Earthling can sit immediately to the left of a Martian, no Martian can sit immediately to the left of a Venusian, and no Venusian can sit immediately to the left of an Earthling. The number of possible seating arrangements for the committee is N(5!)3.N \cdot (5!)^3. Find N.N.

Solution:

First choose which planet sits in each chair; the individuals from each planet can then be assigned to their chairs in 5!5! ways apiece, so NN counts the planet patterns. The adjacency rules say exactly that, reading clockwise, each maximal block of Martians must be followed by a block of Venusians and then a block of Earthlings before Martians can appear again. Since chair 11 holds a Martian and chair 1515 holds an Earthling, the chairs from 11 to 1515 consist of the pattern (Martian block, Venusian block, Earthling block) repeated kk times, for some 1k5.1 \le k \le 5.

For a given k,k, each planet's five members are distributed into kk nonempty blocks in order, and the number of ways to write 55 as an ordered sum of kk positive integers is (4k1).\binom{4}{k-1}. The three planets' block sizes are independent, so N=k=15(4k1)3=13+43+63+43+13=346.N = \sum_{k=1}^{5} \binom{4}{k-1}^3 = 1^3 + 4^3 + 6^3 + 4^3 + 1^3 = 346.

← Problem 9Full ExamProblem 11

Problem 10 in Other Years