Difference between revisions of "1976 IMO Problems/Problem 4"
m (→Solution 3) |
|||
(4 intermediate revisions by 3 users not shown) | |||
Line 3: | Line 3: | ||
== Solution == | == Solution == | ||
− | {{solution}} | + | === Solution 1 === |
+ | Since <math>3*3=2*2*2+1</math>, 3's are more efficient than 2's. We try to prove that 3's are more efficient than anything: | ||
+ | |||
+ | Let there be a positive integer <math>x</math>. If <math>3</math> is more efficient than <math>x</math>, then <math>x^3<3^x</math>. We try to prove that all integers greater than 3 are less efficient than 3: | ||
+ | |||
+ | When <math>x</math> increases by 1, then the RHS is multiplied by 3. The other side is multiplied by <math>\dfrac{(x+1)^3}{x^3}</math>, and we must prove that this is less than 3 for all <math>x</math> greater than 3. | ||
+ | |||
+ | <math>\dfrac{(x+1)^3}{x^3}<3\Rightarrow \dfrac{x+1}{x}<\sqrt[3]{3}\Rightarrow 1<(\sqrt[3]{3}-1)x</math> | ||
+ | |||
+ | <math>\dfrac{1}{\sqrt[3]{3}-1}<x</math> | ||
+ | |||
+ | Thus we need to prove that <math>\dfrac{1}{\sqrt[3]{3}-1}<4</math>. Simplifying, we get <math>5<4\sqrt[3]{3}\Rightarrow 125<64*3=192</math>, which is true. Working backwards, we see that all <math>x</math> greater than 3 are less efficient than 3, so we try to use the most 3's as possible: | ||
+ | |||
+ | <math>\dfrac{1976}{3}=658.6666</math>, so the greatest product is <math>\boxed{3^{658}\cdot 2}</math>. | ||
+ | |||
+ | ===Solution 2=== | ||
+ | We demonstrate heuristically that 3's are the most efficient. | ||
+ | As we know that the chosen numbers must be equal, by the AM-GM inequality, we wish to maximize <cmath> f(x) = \left(\frac{1976}{x}\right)^{x} </cmath> | ||
+ | Simple logarithmic differentiation shows that <math>\frac{S}{x} = e</math> maximizes the given function. As <math>e</math> is approximately 2.71828, we use 2's and 3's only. 3's are optimal, but we must use one 2. | ||
+ | |||
+ | === Solution 3 === | ||
+ | |||
+ | ''Note: This solution uses the same strategy as Solution 1 (that having the largest possible number of three's is good), but approaches the proof in a different manner.'' | ||
+ | |||
+ | Let <math>f(S) \triangleq \prod_{x \in S} x</math>, and <math>g(S) = \sum_{x\in S} x</math>, where <math>S</math> is a multiset. We fix <math>g(S) = 1976</math>, and aim to maximize <math>f(S)</math>. Since <math>3(x-3) > x</math> for <math>x \geq 5</math>, we notice that <math>S</math> must only contain the integers <math>1,2,3</math> and <math>4</math>. We can replace any occurrences of <math>4</math> in <math>S</math> by replacing it with a couple of <math>2</math>'s, without changing <math>f(S)</math> or <math>g(S)</math>, so we may assume that <math>S</math> only contains the integers <math>1,2</math> and <math>3</math>. We may further assume that <math>S</math> contains at most one <math>1</math>, since any two <math>1</math>'s can be replaced by a <math>2</math> without changing <math>g(S)</math>, but with an increase in <math>f(S)</math>. If <math>S</math> contains exactly one <math>1</math>, then it must also contain at least one <math>2</math> (since <math>1976 \equiv 2\;(\mathrm{mod }\;3)</math>). We can then replace this pair of a <math>1</math> and a <math>2</math> with a <math>3</math>, thus keeping <math>g(S)</math> constant, and increasing <math>f(S)</math>. Now we may assume that <math>S</math> contains only <math>2</math>'s and <math>3</math>'s. | ||
+ | |||
+ | Now, as observed in the last solution, any triplet of <math>2</math>'s can be replaced by a couple of <math>3</math>'s, with <math>g(S)</math> constant, and an increase in <math>f(S)</math>. Thus, after repeating this operation, we will be left with at most two <math>2</math>'s. Since <math>g(S) = 1976</math>, and <math>1976 \equiv 2\;(\mathrm{mod }\;3)</math>, we therefore get that <math>S</math> must have exactly one <math>2</math> (since we already showed it consists only of <math>2</math>'s and <math>3</math>'s). Thus, we get <math>\boxed{f(S) = 2\cdot 3^{658}}</math>. | ||
+ | |||
== See also == | == See also == | ||
{{IMO box|year=1976|num-b=3|num-a=5}} | {{IMO box|year=1976|num-b=3|num-a=5}} | ||
+ | |||
+ | [[Category:Intermediate Number Theory Problems]] |
Latest revision as of 22:53, 24 May 2014
Problem
Determine the greatest number, who is the product of some positive integers, and the sum of these numbers is
Solution
Solution 1
Since , 3's are more efficient than 2's. We try to prove that 3's are more efficient than anything:
Let there be a positive integer . If is more efficient than , then . We try to prove that all integers greater than 3 are less efficient than 3:
When increases by 1, then the RHS is multiplied by 3. The other side is multiplied by , and we must prove that this is less than 3 for all greater than 3.
Thus we need to prove that . Simplifying, we get , which is true. Working backwards, we see that all greater than 3 are less efficient than 3, so we try to use the most 3's as possible:
, so the greatest product is .
Solution 2
We demonstrate heuristically that 3's are the most efficient. As we know that the chosen numbers must be equal, by the AM-GM inequality, we wish to maximize Simple logarithmic differentiation shows that maximizes the given function. As is approximately 2.71828, we use 2's and 3's only. 3's are optimal, but we must use one 2.
Solution 3
Note: This solution uses the same strategy as Solution 1 (that having the largest possible number of three's is good), but approaches the proof in a different manner.
Let , and , where is a multiset. We fix , and aim to maximize . Since for , we notice that must only contain the integers and . We can replace any occurrences of in by replacing it with a couple of 's, without changing or , so we may assume that only contains the integers and . We may further assume that contains at most one , since any two 's can be replaced by a without changing , but with an increase in . If contains exactly one , then it must also contain at least one (since ). We can then replace this pair of a and a with a , thus keeping constant, and increasing . Now we may assume that contains only 's and 's.
Now, as observed in the last solution, any triplet of 's can be replaced by a couple of 's, with constant, and an increase in . Thus, after repeating this operation, we will be left with at most two 's. Since , and , we therefore get that must have exactly one (since we already showed it consists only of 's and 's). Thus, we get .
See also
1976 IMO (Problems) • Resources | ||
Preceded by Problem 3 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 5 |
All IMO Problems and Solutions |