Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(→‎Solution 1)
(→‎See Also)
 
(17 intermediate revisions by 4 users not shown)
Line 6: Line 6:
  
 
==Solution 1==
 
==Solution 1==
−
LHS = <math>k</math>! = 1(when <math>k</math> = 1), 2 (when <math>k</math> = 2), 6(when <math>k</math> = 3)
+
<math>LHS</math>  
  
−
RHS = 1(when <math>n</math> = 1), 6 (when <math>n</math> = 2)
+
<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>)
  
−
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:
+
Hence, <math>(1,1)</math>, <math>(3,2)</math> satisfy
  
−
RHS is strictly increasing, and will never satisfy <math>k</math> = 2 for integer n since RHS = 6 when <math>n</math> = 2.
+
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>.
  
−
For <math>k</math> > 3, <math>n</math> > 2:
+
<cmath>k!=(2^n-1)(2^n-2)(2^n-4)\dots(2^n-2^{n-1})  ...                                                                      (1)</cmath>
  
−
LHS: Minimum two odd terms other than 1.
+
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>
  
−
RHS: 1st term odd. No other term will be odd.
+
<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>
−
By parity, LHS not equal to RHS.
 
  
−
Hence, (1,1), (3,2) are the only two pairs that satisfy.
+
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>
  
−
~flamewavelight and phoenixfire
+
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 $(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) = {\frac{n(n-1)}{2}}\]

On the other hand, \[v_2(k!)\] is expressed by the $Legendre$ $formula$ 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

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2019_IMO_Problems/Problem_4&oldid=204595"