Difference between revisions of "2009 AIME I Problems/Problem 10"
(→Solution) |
(→Solution) |
||
Line 4: | Line 4: | ||
== Solution == | == Solution == | ||
− | Since the 5 members of each planet committee are distinct we get that the number of arrangement of sittings is in the form <math>N*(5!)^3</math> because for each M,V,E sequence we have <math>5!</math> arrangements within the Ms, Vs, and Es. | + | Since the 5 members of each planet committee are distinct we get that the number of arrangement of sittings is in the form <math>N*(5!)^3</math> because for each <math>M, V, E</math> sequence we have <math>5!</math> arrangements within the Ms, Vs, and Es. |
− | Pretend the table only seats 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 | + | Pretend the table only seats <math>3</math> "people", with <math>1</math> "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 <math>1</math>, since an M is at seat <math>1</math>. 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 | 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 | + | 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 <math>\binom{4}{1}=4</math> ways for the members of each planet. Therefore, there are <math>4^3=64</math> ways in total. |
− | 3. Three cycles - 2 Ms, Vs, Es left, so | + | 3. Three cycles - 2 Ms, Vs, Es left, so <math>\binom{4}{2}=6</math>, making there <math>6^3=216</math> 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 | + | 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, <math>4^3=64</math> ways total |
− | + | ||
− | 5. Five cycles - MVEMVEMVEMVEMVE | + | 5. Five cycles - MVEMVEMVEMVEMVE is the only possibility, so there is just <math>1</math> way. |
Combining all these cases, we get <math>1+1+64+64+216= \boxed{346}</math> | Combining all these cases, we get <math>1+1+64+64+216= \boxed{346}</math> |
Revision as of 16:23, 17 March 2018
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 to in clockwise order. Committee rules state that a Martian must occupy chair and an Earthling must occupy chair , 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 . Find .
Solution
Since the 5 members of each planet committee are distinct we get that the number of arrangement of sittings is in the form because for each sequence we have arrangements within the Ms, Vs, and Es.
Pretend the table only seats "people", with "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 , since an M is at seat . 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 ways for the members of each planet. Therefore, there are ways in total.
3. Three cycles - 2 Ms, Vs, Es left, so , making there 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, ways total
5. Five cycles - MVEMVEMVEMVEMVE is the only possibility, so there is just way.
Combining all these cases, we get
See also
2009 AIME I (Problems • Answer Key • Resources) | ||
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.