Difference between revisions of "2014 AIME I Problems/Problem 12"
(Created page with "== Problem 12 == == Solution ==") |
m (WHY DOES THIS SOLUTION WORK) |
||
(29 intermediate revisions by 9 users not shown) | |||
Line 1: | Line 1: | ||
== Problem 12 == | == Problem 12 == | ||
+ | Let <math>A=\{1,2,3,4\}</math>, and <math>f</math> and <math>g</math> be randomly chosen (not necessarily distinct) functions from <math>A</math> to <math>A</math>. The probability that the range of <math>f</math> and the range of <math>g</math> are disjoint is <math>\tfrac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m</math>. | ||
− | == Solution == | + | ==Solution 1 (casework)== |
+ | The natural way to go is casework. And the natural process is to sort <math>f</math> and <math>g</math> based on range size! Via Pigeonhole Principle, we see that the only real possibilities are: <math>f 1 g 1; f 1 g 2; f 1 g 3; f 2 g 2</math>. Note that the <math>1, 2</math> and <math>1, 3</math> cases are symmetrical and we need just a <math>*2</math>. Note also that the total number of cases is <math>4^4*4^4=4^8</math>. | ||
+ | |||
+ | <math>f 1 g 1</math>: clearly, we choose one number as the range for <math>f</math>, one for <math>g</math>, yielding <math>12</math> possibilities. | ||
+ | |||
+ | <math>f 1 g 2</math> with symmetry (WLOG <math>f</math> has 1 element): start by selecting numbers for the ranges. This yields <math>4</math> for the one number in <math>f</math>, and <math>3</math> options for the two numbers for <math>g</math>. Afterwards, note that the function with 2 numbers in the range can have <math>4+6+4=14</math> arrangements of these two numbers (1 of one, 3 of the other *2 and 2 of each). Therefore, we have <math>2*12*14</math> possibilities, the 2 from symmetry. | ||
+ | |||
+ | <math>f 2 g 2</math>: no symmetry, still easy! Just note that we have <math>6</math> choices of which numbers go to <math>f</math> and <math>g</math>, and within each, <math>14*14=196</math> choices for the orientation of each of the two numbers. That's <math>6*196</math> possibilities. | ||
+ | |||
+ | <math>f 1 g 3</math>: again, symmetrical (WLOG <math>f</math> has one element): <math>4</math> ways to select the single element for <math>f</math>, and then find the number of ways to distribute the <math>3</math> distinct numbers in the range for <math>g</math>. The only arrangement for the frequency of each number is <math>{1, 1, 2}</math> in some order. Therefore, we have <math>3</math> ways to choose which number is the one represented twice, and then note that there are <math>12</math> ways to arrange these! The number of possibilities in this situation is <math>2 * 4 * 3 * 12</math>. | ||
+ | |||
+ | Total, divided by <math>4^8</math>, gets <math>\frac{3 * (1 + 2 * 7^2 + 2^2 * 7 + 2^3 * 3)}{4^7}</math>, with numerator <math>\boxed{453}</math>. | ||
+ | |||
+ | ==Solution 2 (casework)== | ||
+ | We note there are <math>4^4 = 256</math> possibilities for each of <math>f</math> and <math>g</math> from <math>A</math> to <math>A</math> since the input of the four values of each function has four options each for an output value. | ||
+ | |||
+ | We proceed with casework to determine the number of possible <math>f</math> with range 1, 2, etc. | ||
+ | *Range 1: | ||
+ | |||
+ | There are 4 possibilities: all elements output to 1, 2, 3, or 4. | ||
+ | |||
+ | *Range 2: | ||
+ | |||
+ | We have <math>{{4}\choose {2}} = 6</math> ways to choose the two output elements for <math>f</math>. At this point we have two possibilities: either <math>f</math> has 3 of 1 element and 1 of the other, or 2 of each element. In the first case, there are 2 ways to pick the element which there are 3 copies of, and <math>{{4}\choose {1}} = 4</math> ways to rearrange the 4 elements, for a total of <math>6 * 4 * 2 = 48</math> ways for this case. For the second case, there are <math>{{4}\choose {2}} = 6</math> ways to rearrange the 4 elements, for a total of <math>6 * 6 = 36</math> ways for this case. Adding these two, we get a total of <math>36 + 48 = 84</math> total possibilities. | ||
+ | |||
+ | *Range 3: | ||
+ | |||
+ | We have <math>{{4}\choose {3}} = 4</math> ways to choose the three output elements for <math>f</math>. We know we must have 2 of 1 element and 1 of each of the others, so there are 3 ways to pick this element. Finally, there are <math>{{4}\choose{1}}*{{3}\choose{1}} = 12</math> ways to rearrange these elements (since we can pick the locations of the 2 single elements in this many ways), and our total is <math>4 * 3 * 12 = 144</math> ways. | ||
+ | |||
+ | *Range 4: | ||
+ | |||
+ | Since we know the elements present, we have <math>4!</math> ways to arrange them, or 24 ways. | ||
+ | |||
+ | (To check, <math>4 + 84 + 144 + 24 = 256</math>, which is the total number of possibilities). | ||
+ | |||
+ | We now break <math>f</math> down by cases, and count the number of <math>g</math> whose ranges are disjoint from <math>f</math>'s. | ||
+ | |||
+ | *Case 1: <math>f</math>'s range contains 1 element | ||
+ | We know that there are 3 possibilities for <math>g</math> with 1 element. Since half the possibilities for <math>g</math> with two elements will contain the element in <math>f</math>, there are <math>84/2 = 42</math> possibilities for <math>g</math> with 2 elements. Since <math>3/4</math> the possibilities for <math>g</math> with 3 elements will contain the element in <math>f</math>, there are <math>144/4 = 36</math> possibilities for <math>g</math> with 3 elements. Clearly, no 4-element range for <math>g</math> is possible, so the total number of ways for this case to happen is <math>4(3 + 42 + 36) = 324</math>. | ||
+ | |||
+ | *Case 2: <math>f</math>'s range contains 2 elements | ||
+ | We know that there are 2 possibilities for <math>g</math> with 1 element. If <math>g</math> has 2 elements in its range, they are uniquely determined, so the total number of sets with a range of 2 elements that work for <math>g</math> is <math>84/6 = 14</math>. No 3-element or 4-element ranges for <math>g</math> are possible. Thus, the total number of ways for this to happen is <math>84(2 + 14) = 1344</math>. | ||
+ | |||
+ | |||
+ | *Case 3: <math>f</math>'s range contains 3 elements | ||
+ | In this case, there is only 1 possibility for <math>g</math> - all the output values are the element that does not appear in <math>f</math>'s range. Thus, the total number of ways for this to happen is <math>144</math>. | ||
+ | |||
+ | *Summing the cases | ||
+ | |||
+ | We find that the probability of <math>f</math> and <math>g</math> having disjoint ranges is equal to: | ||
+ | |||
+ | <math>\dfrac{324 + 1344 + 144}{256^2}=\dfrac{1812}{2^{16}}= \dfrac{453}{2^{14}}</math> | ||
+ | |||
+ | Thus, our final answer is <math>\boxed{453}</math>. | ||
+ | |||
+ | === Solution 3 (simplification of Solution 2) === | ||
+ | As before, there are 4 functions with a range of size 1, 84 with a range of size 2, and 144 with a range of size 3. If the range of <math>f</math> has size <math>k</math>, the codomain of <math>g</math> is restricted to a set of size <math>4 - k</math>. Any function from <math>A</math> into this codomain will do, so there are <math>(4 - k)^4</math> possibilities for <math>g</math> given a function <math>f</math>. The probability of <math>f</math> and <math>g</math> having disjoint ranges is then | ||
+ | <cmath>\frac{4\cdot 3^4 + 84\cdot 2^4 + 144\cdot 1^4}{(4^4)^2} = \frac{\boxed{453}}{2^{14}}.</cmath> | ||
+ | |||
+ | |||
+ | ==Video Solution== | ||
+ | https://youtu.be/VFj6JesV93M?si=cDAOday30X0O__4T | ||
+ | |||
+ | ~MathProblemSolvingSkills.com | ||
+ | |||
+ | |||
+ | == See also == | ||
+ | {{AIME box|year=2014|n=I|num-b=11|num-a=13}} | ||
+ | {{MAA Notice}} |
Latest revision as of 21:31, 13 October 2023
Contents
Problem 12
Let , and
and
be randomly chosen (not necessarily distinct) functions from
to
. The probability that the range of
and the range of
are disjoint is
, where
and
are relatively prime positive integers. Find
.
Solution 1 (casework)
The natural way to go is casework. And the natural process is to sort and
based on range size! Via Pigeonhole Principle, we see that the only real possibilities are:
. Note that the
and
cases are symmetrical and we need just a
. Note also that the total number of cases is
.
: clearly, we choose one number as the range for
, one for
, yielding
possibilities.
with symmetry (WLOG
has 1 element): start by selecting numbers for the ranges. This yields
for the one number in
, and
options for the two numbers for
. Afterwards, note that the function with 2 numbers in the range can have
arrangements of these two numbers (1 of one, 3 of the other *2 and 2 of each). Therefore, we have
possibilities, the 2 from symmetry.
: no symmetry, still easy! Just note that we have
choices of which numbers go to
and
, and within each,
choices for the orientation of each of the two numbers. That's
possibilities.
: again, symmetrical (WLOG
has one element):
ways to select the single element for
, and then find the number of ways to distribute the
distinct numbers in the range for
. The only arrangement for the frequency of each number is
in some order. Therefore, we have
ways to choose which number is the one represented twice, and then note that there are
ways to arrange these! The number of possibilities in this situation is
.
Total, divided by , gets
, with numerator
.
Solution 2 (casework)
We note there are possibilities for each of
and
from
to
since the input of the four values of each function has four options each for an output value.
We proceed with casework to determine the number of possible with range 1, 2, etc.
- Range 1:
There are 4 possibilities: all elements output to 1, 2, 3, or 4.
- Range 2:
We have ways to choose the two output elements for
. At this point we have two possibilities: either
has 3 of 1 element and 1 of the other, or 2 of each element. In the first case, there are 2 ways to pick the element which there are 3 copies of, and
ways to rearrange the 4 elements, for a total of
ways for this case. For the second case, there are
ways to rearrange the 4 elements, for a total of
ways for this case. Adding these two, we get a total of
total possibilities.
- Range 3:
We have ways to choose the three output elements for
. We know we must have 2 of 1 element and 1 of each of the others, so there are 3 ways to pick this element. Finally, there are
ways to rearrange these elements (since we can pick the locations of the 2 single elements in this many ways), and our total is
ways.
- Range 4:
Since we know the elements present, we have ways to arrange them, or 24 ways.
(To check, , which is the total number of possibilities).
We now break down by cases, and count the number of
whose ranges are disjoint from
's.
- Case 1:
's range contains 1 element
We know that there are 3 possibilities for with 1 element. Since half the possibilities for
with two elements will contain the element in
, there are
possibilities for
with 2 elements. Since
the possibilities for
with 3 elements will contain the element in
, there are
possibilities for
with 3 elements. Clearly, no 4-element range for
is possible, so the total number of ways for this case to happen is
.
- Case 2:
's range contains 2 elements
We know that there are 2 possibilities for with 1 element. If
has 2 elements in its range, they are uniquely determined, so the total number of sets with a range of 2 elements that work for
is
. No 3-element or 4-element ranges for
are possible. Thus, the total number of ways for this to happen is
.
- Case 3:
's range contains 3 elements
In this case, there is only 1 possibility for - all the output values are the element that does not appear in
's range. Thus, the total number of ways for this to happen is
.
- Summing the cases
We find that the probability of and
having disjoint ranges is equal to:
Thus, our final answer is .
Solution 3 (simplification of Solution 2)
As before, there are 4 functions with a range of size 1, 84 with a range of size 2, and 144 with a range of size 3. If the range of has size
, the codomain of
is restricted to a set of size
. Any function from
into this codomain will do, so there are
possibilities for
given a function
. The probability of
and
having disjoint ranges is then
Video Solution
https://youtu.be/VFj6JesV93M?si=cDAOday30X0O__4T
~MathProblemSolvingSkills.com
See also
2014 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 11 |
Followed by Problem 13 | |
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.