2019 IMO Problems/Problem 4: Difference between revisions
Phoenixfire (talk | contribs) |
Jchang0313 (talk | contribs) |
||
| Line 20: | Line 20: | ||
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> | 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) = | <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> | 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> | ||
Revision as of 00:09, 3 August 2020
Problem
Find all pairs 
of positive integers such that
![\[k!=(2^n-1)(2^n-2)(2^n-4)\dots(2^n-2^{n-1}).\]](http://latex.artofproblemsolving.com/7/c/a/7ca521b92d40def7f320702893c01502439174e8.png)
Solution 1
(when 
), 
(when 
), 
(when 
)
(when 
), (when 
)
Hence, 
, 
satisfy
For 
is strictly increasing, and will never satisfy 
= 2 for integer n since 
when .
![\[k!=(2^n-1)(2^n-2)(2^n-4)\dots(2^n-2^{n-1}) ... (1)\]](http://latex.artofproblemsolving.com/f/e/1/fe15ab3fe2677e301243a84519e0cf2bce085008.png)
In all solutions, for any prime 
and positive integer 
, we will denote by ![\[v_p(N)\]](http://latex.artofproblemsolving.com/3/0/b/30b50b283b8928a5eddfe5c228ad3d7dad58f03c.png)
the exponent of the largest power of that divides . The right-hand side of 
will be denoted by ![\[L_n;\]](http://latex.artofproblemsolving.com/1/0/2/1023c270a3e6299d9db4f0f7860ba6d9f4c67536.png)
that is, ![\[L_n = (2^n-1)(2^n-2)(2^n-4)\dots(2^n-2^{n-1})\]](http://latex.artofproblemsolving.com/5/8/6/58616a5783e4d04469be697ef2fd0143e9ed3315.png)
![\[(2^{1+2+3+\dots+(n-1)})(2^n-1)(2^{n-1}-1)(2^{n-2}-1)\dots(2^1-1)\]](http://latex.artofproblemsolving.com/3/d/1/3d12297fdb0c968bbded8b407d93db3647e9660a.png)
= ![\[v_2(L_n) = {\frac{n(n-1)}{2}}\]](http://latex.artofproblemsolving.com/4/5/6/456451fe90b72fb25eebe3f7bacbc23c407f8b20.png)
On the other hand, ![\[v_2(k!)\]](http://latex.artofproblemsolving.com/4/f/b/4fb4e6a276892ffef24ce71d96dd736e5d548216.png)
is expressed by the 
as ![\[v_2(k!) < \sum_{i=1}^{\infty} (\frac{k}{2^i})) = k\]](http://latex.artofproblemsolving.com/3/7/6/3766c4a5100a45997f34daff45fea4db5c653fd9.png)
Thus, 
implies the inequality ![\[\frac{n(n-1)}{2} < k ... (2)\]](http://latex.artofproblemsolving.com/1/9/6/196397ae9df44be1f0a28e6c5c7141bdca330d00.png)
In order to obtain an opposite estimate, observe that
We claim that ![\[2^{n^2} < (\frac{n(n-1)}{2})! ... (3)\]](http://latex.artofproblemsolving.com/a/c/d/acd929ebfc430f4d979c962e3b7b3940ed186818.png)
for all 
For the estimate (3) is true because ![\[2^{6^2} < (6.9)(10^{10})\]](http://latex.artofproblemsolving.com/f/6/6/f66262261f57a0fe5f69c55585c46eafb976c742.png)
and ![\[(\frac{n(n-1)}{2})! = 15! > (1.3)(10^{12})\]](http://latex.artofproblemsolving.com/e/e/b/eebc618460734b25f3a2e68918eb06ec3862fd9b.png)
~flamewavelight and ~phoenixfire
