Difference between revisions of "2019 IMO Problems/Problem 4"

Revision as of 13:02, 18 January 2020

Problem

Find all pairs $(k,n)$ of positive integers such that

$k!=(2^n-1)(2^n-2)(2^n-4)\dots(2^n-2^{n-1}).$

Solution 1

$LHS$

$k$ ! = 1(when $k = 1$ ), 2 (when $k = 2$ ), 6(when $k = 3$ )

$RHS = 1$ (when $n = 1$ ), $6$ (when $n = 2$ )

Hence, $(1,1)$ , $(3,2)$ satisfy

For $k = 2: RHS$ is strictly increasing, and will never satisfy $k$ = 2 for integer n since $RHS = 6$ when $n = 2$ .

$k!=(2^n-1)(2^n-2)(2^n-4)\dots(2^n-2^{n-1}) ... (1)$

In all solutions, for any prime $p$ and positive integer $N$ , we will denote by $v_p(N)$ the exponent of the largest power of $p$ that divides $N$ . The right-hand side of $(1)$ will be denoted by $L_n;$ that is, $L_n = (2^n-1)(2^n-2)(2^n-4)\dots(2^n-2^{n-1})$

$(2^{1+2+3+\dots+(n-1)})(2^n-1)(2^{n-1}-1)(2^{n-2}-1)\dots(2^1-1)$ = $v_2(L_n) = (2^{\frac{n(n-1)}{2}})$

On the other hand, $v_2(k!)$ is expressed by the $Legendre$ $\text{[math]}$ as $v_2(k!) < \sum_{i=1}^{\infty} (\frac{k}{2^i})) = k$

Thus, $k! = L_n$ implies the inequality $\frac{n(n-1)}{2} < k ... (2)$ In order to obtain an opposite estimate, observe that $L_n = (2^n-1)(2^n-2)(2^n-4)\dots(2^n-2^{n-1})$ We claim that $2^{n^2} < (\frac{n(n-1)}{2})! ... (3)$ for all $n \geq 6$

For $n \geq 6$ the estimate (3) is true because $2^{6^2} < (6.9)(10^{10})$ and $(\frac{n(n-1)}{2})! = 15! > (1.3)(10^{12})$ ~flamewavelight and phoenixfire

@@ Line 6: / Line 6: @@
 ==Solution 1==
-<math>LHS</math> <math>k</math>! = 1(when <math>k</math> = 1), 2 (when <math>k</math> = 2), 6(when <math>k</math> = 3)
+<math>LHS</math>
-<math>RHS = 1</math>(when <math>n</math> = 1), 6 (when <math>n</math> = 2)
+<math>k</math>! = 1(when <math>k = 1</math>), 2 (when <math>k = 2</math>), 6(when <math>k = 3</math>)
-Hence, (1,1), (3,2) satisfy
+<math>RHS = 1</math>(when <math>n = 1</math>), <math>6</math> (when <math>n = 2</math>)
-For <math>k</math> = 2: RHS is strictly increasing, and will never satisfy <math>k</math> = 2 for integer n since RHS = 6 when <math>n</math> = 2.
+Hence, <math>(1,1)</math>, <math>(3,2)</math> satisfy
-It remains to prove that these are the only pairs that 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>.
+<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) = (2^{\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

Page

Toolbox

Search

Difference between revisions of "2019 IMO Problems/Problem 4"

Revision as of 13:02, 18 January 2020

Problem

Solution 1