Difference between revisions of "2019 IMO Problems/Problem 4"
(→Solution 1) |
(→See Also) |
||
(5 intermediate revisions by 3 users not shown) | |||
Line 6: | Line 6: | ||
==Solution 1== | ==Solution 1== | ||
− | <math>LHS</math> | + | <math>LHS</math> |
− | <math> | + | <math>k! = 1</math> (when <math>k = 1</math>), <math>2</math> (when <math>k = 2</math>), <math>6</math> (when <math>k = 3</math>) |
− | + | <math>RHS = 1</math>(when <math>n = 1</math>), <math>6</math> (when <math>n = 2</math>) | |
− | + | Hence, <math>(1,1)</math>, <math>(3,2)</math> satisfy | |
− | + | For <math>k = 2: RHS</math> is strictly increasing, and will never satisfy <math>k</math> = 2 for integer n since <math>RHS = 6</math> when <math>n = 2</math>. | |
− | ~flamewavelight and phoenixfire | + | <cmath>k!=(2^n-1)(2^n-2)(2^n-4)\dots(2^n-2^{n-1}) ... (1)</cmath> |
+ | |||
+ | In all solutions, for any prime <math>p</math> and positive integer <math>N</math>, we will denote by <cmath>v_p(N)</cmath> the exponent of the largest power of <math>p</math> that divides <math>N</math>. The right-hand side of <math>(1)</math> will be denoted by <cmath>L_n;</cmath> that is, <cmath>L_n = (2^n-1)(2^n-2)(2^n-4)\dots(2^n-2^{n-1})</cmath> | ||
+ | |||
+ | <cmath>(2^{1+2+3+\dots+(n-1)})(2^n-1)(2^{n-1}-1)(2^{n-2}-1)\dots(2^1-1)</cmath> = <cmath>v_2(L_n) = {\frac{n(n-1)}{2}} </cmath> | ||
+ | |||
+ | On the other hand, <cmath>v_2(k!)</cmath> is expressed by the <math>Legendre</math> <math>formula</math> as <cmath>v_2(k!) < \sum_{i=1}^{\infty} (\frac{k}{2^i})) = k</cmath> | ||
+ | |||
+ | Thus, <math>k! = L_n</math> implies the inequality <cmath>\frac{n(n-1)}{2} < k ... (2)</cmath> | ||
+ | In order to obtain an opposite estimate, observe that <cmath>L_n = (2^n-1)(2^n-2)(2^n-4)\dots(2^n-2^{n-1})</cmath> | ||
+ | We claim that <cmath>2^{n^2} < (\frac{n(n-1)}{2})! ... (3)</cmath> for all <math>n \geq 6</math> | ||
+ | |||
+ | For <math>n \geq 6</math> the estimate (3) is true because <cmath>2^{6^2} < (6.9)(10^{10})</cmath> | ||
+ | and <cmath>(\frac{n(n-1)}{2})! = 15! > (1.3)(10^{12})</cmath> | ||
+ | ~flamewavelight and ~phoenixfire | ||
+ | |||
+ | ==See Also== | ||
+ | |||
+ | {{IMO box|year=2019|num-b=3|num-a=5}} |
Latest revision as of 00:51, 19 November 2023
Problem
Find all pairs of positive integers such that
Solution 1
(when ), (when ), (when )
(when ), (when )
Hence, , satisfy
For is strictly increasing, and will never satisfy = 2 for integer n since when .
In all solutions, for any prime and positive integer , we will denote by the exponent of the largest power of that divides . The right-hand side of will be denoted by that is,
=
On the other hand, is expressed by the as
Thus, implies the inequality In order to obtain an opposite estimate, observe that We claim that for all
For the estimate (3) is true because and ~flamewavelight and ~phoenixfire
See Also
2019 IMO (Problems) • Resources | ||
Preceded by Problem 3 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 5 |
All IMO Problems and Solutions |