Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2009 AIME I Problems/Problem 10"

m (→‎Solution)
(→‎Note)
(18 intermediate revisions by 12 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== 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 <math>1</math> to <math>15</math> in clockwise order.  Committee rules state that a Martian must occupy chair <math>1</math> and an Earthling must occupy chair <math>15</math>,  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 <math>N(5!)^3</math>.  Find <math>N</math>.
+
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 <math>1</math> to <math>15</math> in clockwise order.  Committee rules state that a Martian must occupy chair <math>1</math> and an Earthling must occupy chair <math>15</math>,  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 <math>N \cdot (5!)^3</math>.  Find <math>N</math>.
  
−
== Solution ==
+
== Solution 1 ==
 +
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.
  
−
Since after each planet, only members of another planet can follow, we simply count the lengths of the blocks adding up to ten. These blocks must be of the form MVE with a certain number of M's,V's,and E's,we consider a few different cases:
+
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. One block of five people- There is only one way to arrange this so <math>{1^3}=1</math>.
+
1. The entire arrangement is one cycle- There is only one way to arrange this, MMMMMVVVVVEEEEE
  
−
2. Five blocks of one person - There is also only one way to arrange this so we get <math>{1^3}=1</math>.
+
2. Two cycles - There are 3 Ms, Vs and Es left to distribute among the existing MVEMVE. Using 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. Two blocks - There are two cases: <math>4+1</math> and <math>3+2</math>. Each of these can be arranged two ways so we get <math>{(2+2)^3}=64</math>.
+
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. Three blocks - There are also two cases: <math>3+1+1</math> and <math>2+2+1</math>.Each of these can be arranged three ways giving us <math>{(3+3)^3}=216</math>.
+
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 is the only possibility, so there is just <math>1</math> way.
  
−
5. Four blocks - There is only one case: <math>2+1+1+1</math>. This can be arranged four ways giving us <math>{4^3}=64</math>.
+
Combining all these cases, we get <math>1+1+64+64+216= \boxed{346}</math>
 +
 
 +
== Solution 2 ==
 +
The arrangements must follow the pattern MVEMVE....... where each MVE consists of some Martians followed by some Venusians followed by some Earthlings, for <math>1, 2, 3, 4,</math> or <math>5</math> MVE's. If there are <math>k</math> MVE's, then by stars and bars, there are <math>{4 \choose k-1}</math> choices for the Martians in each block, and the same goes for the Venusians and the Earthlings. Thus, we have <math>N = 1^3+4^3+6^3+4^3+1^3 = \boxed{346}</math> - aops5234
 +
 
 +
== Note ==
 +
You are probably confused by the solutions. I was too when I first read them. Here is the intuition:
 +
Consider the the arrangement of the <math>M</math>'s <math>V</math>'s and <math>E</math>'s: <math>MMMMM</math> | <math>VVVVV</math> | <math>EEEEE</math>. Now, we can place a bar in the first Martian's section in <math>4</math> spots, and same with the Venusians and Earthlings.
 +
Now for instance, <math>MM|M|MM</math>    ||    <math>V|V|VVV</math>    ||    <math>EEE|E|E</math> would represent the table ordering MMVEEE MVE MMVVVE, which is a valid ordering. Hence we proceed with the solution and we are done.
  
−
Combining all these cases, we get <math>1+1+64+64+216= \boxed{346}</math>
+
~th1nq3r
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=2009|n=I|num-b=9|num-a=11}}
 
{{AIME box|year=2009|n=I|num-b=9|num-a=11}}
 +
[[Category: Intermediate Combinatorics Problems]]
 +
{{MAA Notice}}

Revision as of 13:46, 29 November 2021

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 \cdot (5!)^3$. Find $N$.

Solution 1

Since the 5 members of each planet 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 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 an 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 stars and bars, we get $\binom{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 $\binom{4}{2}=6$, making there $6^3=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, $4^3=64$ ways total

5. Five cycles - MVEMVEMVEMVEMVE is the only possibility, so there is just $1$ way.

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

Solution 2

The arrangements must follow the pattern MVEMVE....... where each MVE consists of some Martians followed by some Venusians followed by some Earthlings, for $1, 2, 3, 4,$ or $5$ MVE's. If there are $k$ MVE's, then by stars and bars, there are ${4 \choose k-1}$ choices for the Martians in each block, and the same goes for the Venusians and the Earthlings. Thus, we have $N = 1^3+4^3+6^3+4^3+1^3 = \boxed{346}$ - aops5234

Note

You are probably confused by the solutions. I was too when I first read them. Here is the intuition: Consider the the arrangement of the $M$'s $V$'s and $E$'s: $MMMMM$ | $VVVVV$ | $EEEEE$. Now, we can place a bar in the first Martian's section in $4$ spots, and same with the Venusians and Earthlings. Now for instance, $MM|M|MM$ || $V|V|VVV$ || $EEE|E|E$ would represent the table ordering MMVEEE MVE MMVVVE, which is a valid ordering. Hence we proceed with the solution and we are done.

~th1nq3r

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2009_AIME_I_Problems/Problem_10&oldid=167012"