2009 AIME I Problems/Problem 10

Revision as of 21:12, 16 February 2015 by Drywood (talk | contribs) (Solution)

Problem

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 $1$ to $15$ in clockwise order. Committee rules state that a Martian must occupy chair $1$ and an Earthling must occupy chair $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$. Find $N$.

Solution

Since the 5 members of each plant committee are distinct we get that the number of arrangement of sittings is in the form $N*(5!)^3$ because for each M,V,E sequence we have $5!$ arrangements within the Ms, Vs, and Es.

Pretend the table only sits 3 "people", with 1 "person" from each planet. Counting clockwise, only the arrangement M, V, E satisfies the given constraints. Therefore, in the actual problem, the members must sit in cycles of M, V, E, but not necessarily with one M, one V, and one E in each cycle(for example, MMVVVE, MVVVEEE, MMMVVVEE all count as cycles). These cycles of MVE must start at seat 1, since a M is at seat 1. We simply count the number of arrangements through casework.

1. The entire arrangement is one cycle- There is only one way to arrange this, MMMMMVVVVVEEEEE

2. Two cycles - There are 3 Ms, Vs and Es left to distribute among the existing MVEMVE. Using sticks and stones(stars and bars), we get C(4,1)=4 ways for the members of each planet. Therefore, there are $4^3=64$ ways in total.

3. Three cycles - 2 Ms, Vs, Es left, so C(4,2)=6 and 216 ways total. 4. Four cycles - 1 M, V, E left, each M can go to any of the four MVE cycles and likewise for V and E, 64 ways total

5. Five cycles - MVEMVEMVEMVEMVE=1 way

Combining all these cases, we get $1+1+64+64+216= \boxed{346}$

See also

2009 AIME I (ProblemsAnswer KeyResources)
Preceded by
Problem 9
Followed by
Problem 11
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