Difference between revisions of "1991 AIME Problems/Problem 13"
Gabiloncho (talk | contribs) (→Solution) |
|||
(25 intermediate revisions by 10 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | A drawer contains a mixture of red socks and blue socks, at most 1991 in all. It so happens that, when two socks are selected randomly without replacement, there is a probability of exactly <math> | + | A drawer contains a mixture of red socks and blue socks, at most <math>1991</math> in all. It so happens that, when two socks are selected randomly without replacement, there is a probability of exactly <math>\frac{1}{2}</math> that both are red or both are blue. What is the largest possible number of red socks in the drawer that is consistent with this data? |
− | == Solution == | + | == Solutions == |
− | Let <math>r</math> and <math>b</math> denote the number of red and blue socks, respectively. Also, let <math>t=r+b</math>. The probability <math>P</math> that when two socks are drawn without replacement, both are red or both are blue is given by | + | === Solution 1 === |
+ | Let <math>r</math> and <math>b</math> denote the number of red and blue socks, respectively. Also, let <math>t=r+b</math>. The probability <math>P</math> that when two socks are drawn randomly, without replacement, both are red or both are blue is given by | ||
− | < | + | <cmath> |
− | + | \frac{r(r-1)}{(r+b)(r+b-1)}+\frac{b(b-1)}{(r+b)(r+b-1)}=\frac{r(r-1)+(t-r)(t-r-1)}{t(t-1)}=\frac{1}{2}. | |
− | </ | + | </cmath> |
Solving the resulting quadratic equation <math>r^{2}-rt+t(t-1)/4=0</math>, for <math>r</math> in terms of <math>t</math>, one obtains that | Solving the resulting quadratic equation <math>r^{2}-rt+t(t-1)/4=0</math>, for <math>r</math> in terms of <math>t</math>, one obtains that | ||
− | < | + | <cmath> |
r=\frac{t\pm\sqrt{t}}{2}\, . | r=\frac{t\pm\sqrt{t}}{2}\, . | ||
− | </ | + | </cmath> |
− | Now, since <math>r</math> and <math>t</math> are positive integers, it must be the case that <math>t=n^{2}</math>, with <math>n\in\mathbb{N}</math>. Hence, <math>r=n(n\pm 1)/2</math> would correspond to the general solution. For the present case | + | Now, since <math>r</math> and <math>t</math> are positive integers, it must be the case that <math>t=n^{2}</math>, with <math>n\in\mathbb{N}</math>. Hence, <math>r=n(n\pm 1)/2</math> would correspond to the general solution. For the present case <math>t\leq 1991</math>, and so one easily finds that <math>n=44</math> is the largest possible integer satisfying the problem conditions. |
− | In summary, the solution is that the maximum number of red socks is <math>r=990</math>. | + | In summary, the solution is that the maximum number of red socks is <math>r=\boxed{990}</math>. |
+ | === Solution 2 === | ||
+ | Let <math>r</math> and <math>b</math> denote the number of red and blue socks such that <math>r+b\le1991</math>. Then by complementary counting, the number of ways to get a red and a blue sock must be equal to <math>1-\frac12=\frac12=\frac{2rb}{(r+b)(r+b-1)}\implies4rb=(r+b)(r+b-1)</math> | ||
+ | <math>=(r+b)^2-(r+b)\implies r^2+2rb+b^2-r-b=4rb\implies r^2-2rb+b^2</math> | ||
+ | <math>=(r-b)^2=r+b</math>, so <math>r+b</math> must be a perfect square <math>k^2</math>. Clearly, <math>r=\frac{k^2+k}2</math>, so the larger <math>k</math>, the larger <math>r</math>: <math>k^2=44^2</math> is the largest perfect square below <math>1991</math>, and our answer is <math>\frac{44^2+44}2=\frac12\cdot44(44+1)=22\cdot45=11\cdot90=\boxed{990}</math>. | ||
+ | |||
+ | |||
+ | ===Solution 3=== | ||
+ | |||
+ | Let <math>r</math> and <math>b</math> denote the number of red and blue socks, respectively. In addition, let <math>t = r + b</math>, the total number of socks in the drawer. | ||
+ | |||
+ | From the problem, it is clear that <math>\frac{r(r-1)}{t(t-1)} + \frac{b(b-1)}{t(t-1)} = \frac{1}{2}</math> | ||
+ | |||
+ | Expanding, we get <math>\frac{r^2 + b^2 - r - b}{t^2 - t} = \frac{1}{2}</math> | ||
+ | |||
+ | Substituting <math>t</math> for <math>r + b</math> and cross multiplying, we get <math>2r^2 + 2b^2 - 2r - 2b = r^2 + 2br + b^2 - r - b</math> | ||
+ | |||
+ | Combining terms, we get <math>b^2 - 2br + r^2 - b - r = 0</math> | ||
+ | |||
+ | To make this expression factorable, we add <math>2r</math> to both sides, resulting in <math>(b - r)^2 - 1(b-r) = (b - r - 1)(b - r) = 2r</math> | ||
+ | |||
+ | From this equation, we can test values for the expression <math>(b - r - 1)(b - r)</math>, which is the multiplication of two consecutive integers, until we find the highest value of <math>b</math> or <math>r</math> such that <math>b + r \leq 1991</math>. | ||
+ | |||
+ | By testing <math>(b - r - 1) = 43</math> and <math>(b - r) = 44</math>, we get that <math>r = 43(22) = 946</math> and <math>b = 990</math>. Testing values one integer higher, we get that <math>r = 990</math> and <math>b = 1035</math>. Since <math>990 + 1035 = 2025</math> is greater than <math>1991</math>, we conclude that <math>(946, 990)</math> is our answer. | ||
+ | |||
+ | Since it doesn't matter whether the number of blue or red socks is <math>990</math>, we take the lower value for <math>r</math>, thus the maximum number of red socks is <math>r=\boxed{990}</math>. | ||
+ | |||
+ | === Solution 4 === | ||
+ | As above, let <math>r</math>, <math>b</math>, and <math>t</math> denote the number of red socks, the number of blue socks, and the total number of socks, respectively. We see that <math>\frac{r(r-1)}{t(t-1)}+\frac{b(b-1)}{t(t-1)}=\frac{1}{2}</math>, so <math>r^2+b^2-r-b=\frac{t(t-1)}{2}=r^2+b^2-t=\frac{t^2}{2}-\frac{t}{2}</math>. | ||
+ | |||
+ | Seeing that we can rewrite <math>r^2+b^2</math> as <math>(r+b)^2-2rb</math>, and remembering that <math>r+b=t</math>, we have <math>\frac{t^2}{2}-\frac{t}{2}=t^2-2rb-t</math>, so <math>2rb=\frac{t^2}{2}-\frac{t}{2}</math>, which equals <math>r^2+b^2-t</math>. | ||
+ | |||
+ | We now have <math>r^2+b^2-t=2rb</math>, so <math>r^2-2rb+b^2=t</math> and <math>r-b=\pm\sqrt{t}</math>. Adding this to <math>r+b=t</math>, we have <math>2r=t\pm\sqrt{t}</math>. To maximize <math>r</math>, we must use the positive square root and maximize <math>t</math>. The largest possible value of <math>t</math> is the largest perfect square less than 1991, which is <math>1936=44^2</math>. Therefore, <math>r=\frac{t+\sqrt{t}}{2}=\frac{1936+44}{2}=\boxed{990}</math>. | ||
+ | |||
+ | Solution by Zeroman | ||
+ | |||
+ | ===Solution 5=== | ||
+ | Let <math>r</math> be the number of socks that are red, and <math>t</math> be the total number of socks. We get: | ||
+ | |||
+ | <math>2(r(r-1)+(t-r)(t-r-1))=t(t-1)</math> | ||
+ | Expanding the left hand side and the right hand side, we get: | ||
+ | <math>4r^2-4rt+2t^2-2t = t^2-t</math> | ||
+ | |||
+ | And, moving terms, we will get that: | ||
+ | <math>4r^2-4rt+t^2 = t</math> | ||
+ | |||
+ | We notice that the left side is a perfect square. | ||
+ | <math>(2r-t)^2 = t</math> | ||
+ | |||
+ | Thus <math>t</math> is a perfect square. And, the higher <math>t</math> is, the higher <math>r</math> will be. So, we should set <math>t = 44^2 = 1936</math> | ||
+ | |||
+ | And, we see, <math>2r-1936 = \pm44</math> We will use the positive root, to get that <math>2r-1936 = 44</math>, <math>2r = 1980</math>, and <math>r = \boxed{990}</math>. | ||
+ | |||
+ | - AlexLikeMath | ||
+ | |||
+ | ==Solution 6== | ||
+ | Let <math>r</math> and <math>b</math> denote the red socks and blue socks, respectively. Thus the equation in question is: | ||
+ | |||
+ | <math>\frac{r(r-1)+b(b-1)}{(r+b)(r+b-1)}=\frac{1}{2}</math> | ||
+ | |||
+ | <math>\Rightarrow 2r^2-2r+2b^2-2b=r^2+2rb+b^2-r-b</math> | ||
+ | |||
+ | <math>\Rightarrow r^2+b^2-r-b-2rb=0</math> | ||
+ | |||
+ | <math>\Rightarrow (r-b)^2=r+b\le 1991</math> | ||
+ | |||
+ | Because we wish to maximize <math>r</math>, we have <math>r\ge b</math> and thus <math>r-b\le 44</math> as both <math>r</math> and <math>b</math> must be integers and <math>{44}^2=1936</math> is the largest square less than or equal to <math>1991</math>. We now know that the maximum difference between the number of socks is <math>44</math>. Now we return to an earlier equation: | ||
+ | |||
+ | <math>r^2+b^2-r-b-2rb=0</math> | ||
+ | |||
+ | <math>\Rightarrow r^2-(2b+1)r+(b^2-b)=0</math> | ||
+ | |||
+ | Solving by the [[Quadratic formula]], we have: | ||
+ | |||
+ | <math>r=\frac{2b+1\pm\sqrt{4b^2+4b+1-4b^2+4b}}{2}</math> | ||
+ | |||
+ | <math>\Rightarrow r=\frac{2b+1\pm\sqrt{8b+1}}{2}</math> | ||
+ | |||
+ | <math>\Rightarrow r-b=\frac{1\pm\sqrt{8b+1}}{2}</math> | ||
+ | |||
+ | <math>\Rightarrow 44\ge r-b=\frac{1\pm\sqrt{8b+1}}{2}</math> | ||
+ | |||
+ | <math>\Rightarrow 44\ge\frac{1\pm\sqrt{8b+1}}{2}</math> | ||
+ | |||
+ | <math>\Rightarrow \pm\sqrt{8b+1}\le 87</math> | ||
+ | |||
+ | <math>\Rightarrow b\le 946</math> (Here we use the positive sign to maximize <math>r</math>.) | ||
+ | |||
+ | Thus the optimal case would be <math>b=946</math> as <math>r</math> increases only when <math>b</math> increases. In addition, <math>\sqrt{8b+1}=87</math> as we are using the equality case. We then plug back in: | ||
+ | |||
+ | <math>r=\frac{2b+1\pm\sqrt{8b+1}}{2}</math> | ||
+ | |||
+ | <math>\Rightarrow r=\frac{1893+87}{2}</math> (using the established <math>\sqrt{8b+1}=87</math>) | ||
+ | |||
+ | <math>\Rightarrow r=\frac{1980}{2}</math> | ||
+ | |||
+ | <math>\Rightarrow r=\boxed{990}</math> | ||
+ | |||
+ | ~eevee9406 | ||
== See also == | == See also == | ||
− | {{AIME box|year=1991|num-b=12|num-a=14}} | + | {{AIME box|year=1991|num-b=12|num-a=14}} |
+ | |||
+ | [[Category:Intermediate Combinatorics Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 19:24, 5 February 2024
Contents
[hide]Problem
A drawer contains a mixture of red socks and blue socks, at most in all. It so happens that, when two socks are selected randomly without replacement, there is a probability of exactly that both are red or both are blue. What is the largest possible number of red socks in the drawer that is consistent with this data?
Solutions
Solution 1
Let and denote the number of red and blue socks, respectively. Also, let . The probability that when two socks are drawn randomly, without replacement, both are red or both are blue is given by
Solving the resulting quadratic equation , for in terms of , one obtains that
Now, since and are positive integers, it must be the case that , with . Hence, would correspond to the general solution. For the present case , and so one easily finds that is the largest possible integer satisfying the problem conditions.
In summary, the solution is that the maximum number of red socks is .
Solution 2
Let and denote the number of red and blue socks such that . Then by complementary counting, the number of ways to get a red and a blue sock must be equal to , so must be a perfect square . Clearly, , so the larger , the larger : is the largest perfect square below , and our answer is .
Solution 3
Let and denote the number of red and blue socks, respectively. In addition, let , the total number of socks in the drawer.
From the problem, it is clear that
Expanding, we get
Substituting for and cross multiplying, we get
Combining terms, we get
To make this expression factorable, we add to both sides, resulting in
From this equation, we can test values for the expression , which is the multiplication of two consecutive integers, until we find the highest value of or such that .
By testing and , we get that and . Testing values one integer higher, we get that and . Since is greater than , we conclude that is our answer.
Since it doesn't matter whether the number of blue or red socks is , we take the lower value for , thus the maximum number of red socks is .
Solution 4
As above, let , , and denote the number of red socks, the number of blue socks, and the total number of socks, respectively. We see that , so .
Seeing that we can rewrite as , and remembering that , we have , so , which equals .
We now have , so and . Adding this to , we have . To maximize , we must use the positive square root and maximize . The largest possible value of is the largest perfect square less than 1991, which is . Therefore, .
Solution by Zeroman
Solution 5
Let be the number of socks that are red, and be the total number of socks. We get:
Expanding the left hand side and the right hand side, we get:
And, moving terms, we will get that:
We notice that the left side is a perfect square.
Thus is a perfect square. And, the higher is, the higher will be. So, we should set
And, we see, We will use the positive root, to get that , , and .
- AlexLikeMath
Solution 6
Let and denote the red socks and blue socks, respectively. Thus the equation in question is:
Because we wish to maximize , we have and thus as both and must be integers and is the largest square less than or equal to . We now know that the maximum difference between the number of socks is . Now we return to an earlier equation:
Solving by the Quadratic formula, we have:
(Here we use the positive sign to maximize .)
Thus the optimal case would be as increases only when increases. In addition, as we are using the equality case. We then plug back in:
(using the established )
~eevee9406
See also
1991 AIME (Problems • Answer Key • Resources) | ||
Preceded by Problem 12 |
Followed by Problem 14 | |
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.