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 "2012 AIME II Problems/Problem 14"
m (typo)
 
(21 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 
== Problem 14 ==
 
== Problem 14 ==
 
In a group of nine people each person shakes hands with exactly two of the other people from the group. Let <math>N</math> be the number of ways this handshaking can occur. Consider two handshaking arrangements different if and only if at least two people who shake hands under one arrangement do not shake hands under the other arrangement. Find the remainder when <math>N</math> is divided by <math>1000</math>.
 
In a group of nine people each person shakes hands with exactly two of the other people from the group. Let <math>N</math> be the number of ways this handshaking can occur. Consider two handshaking arrangements different if and only if at least two people who shake hands under one arrangement do not shake hands under the other arrangement. Find the remainder when <math>N</math> is divided by <math>1000</math>.
−
 
  
 
== Solution 1 ==
 
== Solution 1 ==
Line 17: Line 16:
  
 
== Solution 2 ==
 
== Solution 2 ==
−
Let f(N) be the number of ways a group of N people can shake hands with exactly two of the other people from the group, where N \ge 3.
+
Let <math>f_N</math> be the number of ways a group of <math>N</math> people can shake hands with exactly two of the other people from the group, where <math>N \ge 3</math>.
 +
 
 +
We can easily find that <math>f_3=1</math>.
 +
 
 +
Continuing on, we will label the people as <math>A</math>,<math>B</math>,<math>C</math>,... corresponding with <math>N</math>.
 +
 
 +
<math>f_4</math>: There are <math>\dbinom{3}{2}=3</math> possible ways for person <math>A</math> to shake hands with two others (WLOG assume <math>A</math> shakes hands with <math>B</math> and <math>C</math>), and there is only one possible outcome thereon (<math>B</math> and <math>C</math> both shakes hands with <math>D</math>).
 +
 
 +
Therefore, we can conclude that <math>f_4=3</math>
 +
 
 +
<math>f_5</math>: There are <math>\dbinom{4}{2}=6</math> possible ways for person <math>A</math> to shake hands with two others (WLOG assume they are <math>B</math> and <math>C</math>). Then, <math>B</math> and <math>C</math> must also shake hands with the remaining two people (<math>2</math> ways), and those last <math>2</math> people must shake hands with each other (<math>1</math> way).
 +
Therefore, <math>f_5=\dbinom{4}{2}\ast(2)\ast(1)=12</math>
 +
 
 +
<math>f_6</math>: There are <math>\dbinom{5}{2}=10</math> possible ways for person <math>A</math> to shake hands with two others (WLOG assume they are <math>B</math> and <math>C</math>). However, <math>B</math> and <math>C</math> shake hands with each other, then there are <math>f_3</math> ways for the rest of the people to shake hands. If <math>B</math> and <math>C</math> shake hands with two others out of the three remaining people (3<math>\ast</math>2 ways), those <math>2</math> people must shake hands with the last person (<math>1</math> way).
 +
Therefore, <math>f_6=\dbinom{5}{2}\ast(f_3)+3\ast(2)\ast(1)=70</math>
 +
 
 +
Now we have enough information to find <math>f_9</math>
  
−
We can easily find that f(3)=1.
+
<math>f_9</math>: There are <math>\dbinom{8}{2}=28</math> possible ways for person <math>A</math> to shake hands with two others (WLOG assume they are <math>B</math> and <math>C</math>).
−
Continuing on, we will label the people as A,B,C,... corresponding with N.
 
−
f(4): There are <math>\dbinom{3}{2}=3</math> possible ways for person A to shake hands with two others. The situation is illustrated below (WLOG assume A shakes hands with B and C), with the letters after the semicolon representing the people who shake the person before the semicolon. Note that a person cannot shake more than two hands.
 
−
A: B C    B: A    C: A    D:
 
  
−
The only possible ending of this situation is shown below
+
'''Case 1:''' <math>B</math> and <math>C</math> shake hands with each other
−
A: B C    B: A D    C: A D    D: B C
 
  
−
Therefore, we can conclude that f(4)=3
+
There are <math>f_6</math> ways for <math>D</math>,<math>E</math>,<math>F</math>,<math>G</math>,<math>H</math>, and <math>I</math> to shake hands
  
−
f(5): There are <math>\dbinom{4}{2}=6</math> possible ways for person A to shake hands with two others (WLOG assume they are B and C). Then, B and C must also shake hands with the remaining two people (2 ways), and those last 2 people must shake hands with each other (1 way).
+
'''Case 2:''' <math>B</math> and <math>C</math> shake hands with one of the others out of the <math>6</math> remaining people (<math>6</math> ways)
−
Therefore, f(5)=<math>\dbinom{4}{2}*2*1=12</math>
 
  
−
f(6): There are <math>\dbinom{5}{2}=10</math> possible ways for person A to shake hands with two others (WLOG assume they are B and C). However, B and C shake hands with each other, then there are f(3) ways for the rest of the people to shake hands. If B and C shake hands with two others out of the three remaining people (3 * 2 ways), those 2 people must shake hands with the last person (1 way).
+
There are <math>f_5</math> ways for <math>E</math>,<math>F</math>,<math>G</math>,<math>H</math>, and <math>I</math> to shake hands
−
Therefore, f(5)=<math>\dbinom{5}{2}*(f(3)+3*2*1)=70</math>
 
  
−
Now we have enough information to find f(9)
+
'''Case 3:''' If <math>B</math> and <math>C</math> shake hands with two different people (there are 6<math>\ast</math>5 ways to choose the people but WLOG assume they are <math>D</math> and <math>E</math>). Calculations of Case 3 are in its subcases.
−
f(9): There are <math>\dbinom{8}{2}=28</math> possible ways for person A to shake hands with two others (WLOG assume they are B and C).
 
−
Starting situation:
 
−
A: B C    B: A    C: A    D:    E:    F:    G:    H:    I:
 
  
−
'''Case 1:''' B and C shake hands with each other
+
'''Subcase 3.1:''' <math>D</math> and <math>E</math> shake hands with each other
−
A: B C    B: A C    C: A B    D:    E:    F:    G:    H:    I:
+
There are <math>f_4</math> ways for <math>F</math>,<math>G</math>,<math>H</math>, and <math>I</math> to shake hands
−
There are f(6) ways for D,E,F,G,H, and I to shake hands
 
  
−
'''Case 2:''' B and C shake hands with one of the others out of the 6 remaining people (6 ways)
+
'''Subcase 3.2:''' <math>D</math> and <math>E</math> each shake hands with one other person (there are <math>4</math> ways to choose the person, WLOG let that be <math>F</math>)
−
A: B C    B: A D    C: A D    D: B C    E:    F:    G:    H:    I:
+
There are <math>f_3</math> ways for <math>G</math>,<math>H</math>, and <math>I</math> to shake hands
−
There are f(5) ways for E,F,G,H, and I to shake hands
 
  
−
'''Case 3:''' If B and C shake hands with two different people (there are 6*5 ways to choose the people but WLOG assume they are D and E) Calculations of Case 3 are in its subcases.
 
−
A: B C    B: A D    C: A E    D: B    E: C    F:    G:    H:    I:
 
  
−
'''Subcase 3.1:''' D and E shake hands with each other
+
'''Subcase 3.3:''' <math>D</math> and <math>E</math> each shake hands with two different people (there are 4<math>\ast</math>3 ways, WLOG let that be <math>F</math> and <math>G</math>)
−
A: B C    B: A D    C: A E    D: B E    E: C D    F:    G:    H:    I:
+
There are <math>2\ast1</math> ways for <math>F</math> and <math>G</math> to then shake hands with <math>H</math> and <math>I</math>, and <math>H</math> and <math>I</math> will shake hands with each other.
−
There are f(4) ways for F,G,H, and I to shake hands
 
  
−
'''Subcase 3.2:''' D and E each shake hands with one other person (there are 4 ways to choose the person, WLOG let that be F)
+
We have
−
A: B C    B: A D    C: A E    D: B F    E: C F    F: D E    G:    H:    I:
 
−
There are f(3) ways for G,H, and I to shake hands
 
  
 +
<cmath>
 +
\begin{align*}
 +
28(f_6+6\ast(f_5)+6\ast(5)\ast(f_4)+4\ast(f_3)+4\ast(3)\ast(2)\ast(1) &= 28(70+6\ast(12)+6\ast(5)\ast(3+4\ast(1)+4\ast(3)\ast(2)\ast(1) \\
 +
&= 30016
 +
\end{align*}
 +
</cmath>
  
−
'''Subcase 3.3:''' D and E each shake hands with two different people (there are 4*3 ways, WLOG let that be F and G)
+
which gives us the answer of <math>\boxed{016}</math>
−
A: B C    B: A D    C: A E    D: B F    E: C G    F: D    G: E    H:    I:
 
−
There are 2*1 ways for F and G to then shake hands with H and I, and H and I will shake hands with each other.
 
  
−
We have 28(f(6)+6<math>\ast</math>f(5)+6<math>\ast</math>5<math>\ast</math>(f(4)+4<math>\ast</math>f(3)+4<math>\ast</math>3<math>\ast</math>(2<math>\ast</math>1))) = 28(70+6<math>\ast</math>12+6<math>\ast</math>5<math>\ast</math>(3+4<math>\ast</math>1+4<math>\ast</math>3<math>\ast</math>(2<math>\ast</math>1)))30016, which gives us the answer of \boxed{016}$.
+
~[[Daniel Zhou's Profile|Danielzh]]
  
 
==Video Solution==
 
==Video Solution==

Latest revision as of 23:08, 20 August 2024

Problem 14

In a group of nine people each person shakes hands with exactly two of the other people from the group. Let $N$ be the number of ways this handshaking can occur. Consider two handshaking arrangements different if and only if at least two people who shake hands under one arrangement do not shake hands under the other arrangement. Find the remainder when $N$ is divided by $1000$.

Solution 1

Given that each person shakes hands with two people, we can view all of these through graph theory as 'rings'. This will split it into four cases: Three rings of three, one ring of three and one ring of six, one ring of four and one ring of five, and one ring of nine. (All other cases that sum to nine won't work, since they have at least one 'ring' of two or fewer points, which doesn't satisfy the handshaking conditions of the problem.)

Case 1: To create our groups of three, there are $\dfrac{\dbinom{9}{3}\dbinom{6}{3}\dbinom{3}{3}}{3!}$. In general, the number of ways we can arrange people within the rings to count properly is $\dfrac{(n-1)!}{2}$, since there are $(n-1)!$ ways to arrange items in the circle, and then we don't want to want to consider reflections as separate entities. Thus, each of the three cases has $\dfrac{(3-1)!}{2}=1$ arrangements. Therefore, for this case, there are $\left(\dfrac{\dbinom{9}{3}\dbinom{6}{3}\dbinom{3}{3}}{3!}\right)(1)^3=280$

Case 2: For three and six, there are $\dbinom{9}{6}=84$ sets for the rings. For organization within the ring, as before, there is only one way to arrange the ring of three. For six, there is $\dfrac{(6-1)!}{2}=60$. This means there are $(84)(1)(60)=5040$ arrangements.

Case 3: For four and five, there are $\dbinom{9}{5}=126$ sets for the rings. Within the five, there are $\dfrac{4!}{2}=12$, and within the four there are $\dfrac{3!}{2}=3$ arrangements. This means the total is $(126)(12)(3)=4536$.

Case 4: For the nine case, there is $\dbinom{9}{9}=1$ arrangement for the ring. Within it, there are $\dfrac{8!}{2}=20160$ arrangements.

Summing the cases, we have $280+5040+4536+20160=30016 \to \boxed{016}$.

Solution 2

Let $f_N$ be the number of ways a group of $N$ people can shake hands with exactly two of the other people from the group, where $N \ge 3$.

We can easily find that $f_3=1$.

Continuing on, we will label the people as $A$,$B$,$C$,... corresponding with $N$.

$f_4$: There are $\dbinom{3}{2}=3$ possible ways for person $A$ to shake hands with two others (WLOG assume $A$ shakes hands with $B$ and $C$), and there is only one possible outcome thereon ($B$ and $C$ both shakes hands with $D$).

Therefore, we can conclude that $f_4=3$

$f_5$: There are $\dbinom{4}{2}=6$ possible ways for person $A$ to shake hands with two others (WLOG assume they are $B$ and $C$). Then, $B$ and $C$ must also shake hands with the remaining two people ($2$ ways), and those last $2$ people must shake hands with each other ($1$ way). Therefore, $f_5=\dbinom{4}{2}\ast(2)\ast(1)=12$

$f_6$: There are $\dbinom{5}{2}=10$ possible ways for person $A$ to shake hands with two others (WLOG assume they are $B$ and $C$). However, $B$ and $C$ shake hands with each other, then there are $f_3$ ways for the rest of the people to shake hands. If $B$ and $C$ shake hands with two others out of the three remaining people (3$\ast$2 ways), those $2$ people must shake hands with the last person ($1$ way). Therefore, $f_6=\dbinom{5}{2}\ast(f_3)+3\ast(2)\ast(1)=70$

Now we have enough information to find $f_9$

$f_9$: There are $\dbinom{8}{2}=28$ possible ways for person $A$ to shake hands with two others (WLOG assume they are $B$ and $C$).

Case 1: $B$ and $C$ shake hands with each other

There are $f_6$ ways for $D$,$E$,$F$,$G$,$H$, and $I$ to shake hands

Case 2: $B$ and $C$ shake hands with one of the others out of the $6$ remaining people ($6$ ways)

There are $f_5$ ways for $E$,$F$,$G$,$H$, and $I$ to shake hands

Case 3: If $B$ and $C$ shake hands with two different people (there are 6$\ast$5 ways to choose the people but WLOG assume they are $D$ and $E$). Calculations of Case 3 are in its subcases.

Subcase 3.1: $D$ and $E$ shake hands with each other There are $f_4$ ways for $F$,$G$,$H$, and $I$ to shake hands

Subcase 3.2: $D$ and $E$ each shake hands with one other person (there are $4$ ways to choose the person, WLOG let that be $F$) There are $f_3$ ways for $G$,$H$, and $I$ to shake hands


Subcase 3.3: $D$ and $E$ each shake hands with two different people (there are 4$\ast$3 ways, WLOG let that be $F$ and $G$) There are $2\ast1$ ways for $F$ and $G$ to then shake hands with $H$ and $I$, and $H$ and $I$ will shake hands with each other.

We have

\begin{align*} 28(f_6+6\ast(f_5)+6\ast(5)\ast(f_4)+4\ast(f_3)+4\ast(3)\ast(2)\ast(1) &= 28(70+6\ast(12)+6\ast(5)\ast(3+4\ast(1)+4\ast(3)\ast(2)\ast(1) \\ &= 30016 \end{align*}

which gives us the answer of $\boxed{016}$

~Danielzh

Video Solution

Very Neat solution: https://www.youtube.com/watch?v=lG8N9RuI-8o

Similar Problems

2006 HMMT feb. combo #9.

See Also

2012 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 13 		Followed by
Problem 15
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=2012_AIME_II_Problems/Problem_14&oldid=225455"