Difference between revisions of "2012 AIME II Problems/Problem 14"
(→Solution 2) |
(→Solution 2) |
||
(One intermediate revision by the same user not shown) | |||
Line 37: | Line 37: | ||
'''Case 1:''' <math>B</math> and <math>C</math> shake hands with each other | '''Case 1:''' <math>B</math> and <math>C</math> shake hands with each other | ||
+ | |||
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 | 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 | ||
'''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) | '''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) | ||
+ | |||
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 | 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 | ||
− | '''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. | + | '''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. |
'''Subcase 3.1:''' <math>D</math> and <math>E</math> shake hands with each other | '''Subcase 3.1:''' <math>D</math> and <math>E</math> shake hands with each other | ||
Line 59: | Line 61: | ||
\begin{align*} | \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) \\ | 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 | + | &= 30016 |
\end{align*} | \end{align*} | ||
</cmath> | </cmath> |
Latest revision as of 14:18, 7 July 2023
Problem 14
In a group of nine people each person shakes hands with exactly two of the other people from the group. Let 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
is divided by
.
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 . In general, the number of ways we can arrange people within the rings to count properly is
, since there are
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
arrangements. Therefore, for this case, there are
Case 2: For three and six, there are 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
. This means there are
arrangements.
Case 3: For four and five, there are sets for the rings. Within the five, there are
, and within the four there are
arrangements. This means the total is
.
Case 4: For the nine case, there is arrangement for the ring. Within it, there are
arrangements.
Summing the cases, we have .
Solution 2
Let be the number of ways a group of
people can shake hands with exactly two of the other people from the group, where
.
We can easily find that .
Continuing on, we will label the people as ,
,
,... corresponding with
.
: There are
possible ways for person
to shake hands with two others (WLOG assume
shakes hands with
and
), and there is only one possible outcome thereon (
and
both shakes hands with
).
Therefore, we can conclude that
: There are
possible ways for person
to shake hands with two others (WLOG assume they are
and
). Then,
and
must also shake hands with the remaining two people (
ways), and those last
people must shake hands with each other (
way).
Therefore,
: There are
possible ways for person
to shake hands with two others (WLOG assume they are
and
). However,
and
shake hands with each other, then there are
ways for the rest of the people to shake hands. If
and
shake hands with two others out of the three remaining people (3
2 ways), those
people must shake hands with the last person (
way).
Therefore,
Now we have enough information to find
: There are
possible ways for person
to shake hands with two others (WLOG assume they are
and
).
Case 1: and
shake hands with each other
There are ways for
,
,
,
,
, and
to shake hands
Case 2: and
shake hands with one of the others out of the
remaining people (
ways)
There are ways for
,
,
,
, and
to shake hands
Case 3: If and
shake hands with two different people (there are 6
5 ways to choose the people but WLOG assume they are
and
). Calculations of Case 3 are in its subcases.
Subcase 3.1: and
shake hands with each other
There are
ways for
,
,
, and
to shake hands
Subcase 3.2: and
each shake hands with one other person (there are
ways to choose the person, WLOG let that be
)
There are
ways for
,
, and
to shake hands
Subcase 3.3: and
each shake hands with two different people (there are 4
3 ways, WLOG let that be
and
)
There are
ways for
and
to then shake hands with
and
, and
and
will shake hands with each other.
We have
which gives us the answer of
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.