A number Theory question on reaching 100,000 points

Find the least positive integer n n for which there exists a set { s 1 , s 2 , . . . , s n } \{\ s_{1}, s_{2}, . . . , s_{n}\} consisting of n n distinct positive integers such that

( 1 1 s 1 ) ( 1 1 s 2 ) ( 1 1 s n ) = 42 2010 \large{\left( 1-\frac { 1 }{ { s }_{ 1 } } \right) \left( 1-\frac { 1 }{ { s }_{ 2 } } \right) \cdots \cdots \left( 1-\frac { 1 }{ { s }_{ n } } \right) =\frac { 42 }{ 2010 } }

Bonus:- Prove it's unique


The answer is 48.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Patrick Corn
Feb 9, 2018

First we show that n 48. n \le 48. For this, it suffices to exhibit a set of 48 48 positive integers with the desired property.

So let s 1 = 2 , s 2 = 3 , , s 44 = 45 ; s 45 = 64 , s 46 = 65 , s 47 = 66 , s 48 = 67. s_1 = 2, s_2 = 3, \ldots, s_{44} = 45; s_{45} = 64, s_{46} = 65, s_{47} = 66, s_{48} = 67. Then i = 1 48 ( 1 1 s i ) = 1 45 63 67 = 63 3015 = 42 2010 , \prod_{i=1}^{48} \left( 1-\frac1{s_i}\right) = \frac1{45} \cdot \frac{63}{67} = \frac{63}{3015} = \frac{42}{2010}, as desired.

Now we want to give a lower bound for n . n. The idea is that 42 2010 \frac{42}{2010} is so small that we need a lot of terms in the product.

Suppose without loss of generality that the s i s_i are in ascending order. Note that s i i + 1 s_i \ge i+1 (since s 1 = 1 s_1=1 is impossible). Then i = 1 n ( 1 1 s i ) i = 1 n ( 1 1 i + 1 ) = 1 2 2 3 n n + 1 = 1 n + 1 . \prod_{i=1}^n \left( 1-\frac1{s_i} \right) \ge \prod_{i=1}^n \left( 1-\frac1{i+1} \right) = \frac12 \cdot \frac23 \cdots \frac{n}{n+1} = \frac1{n+1}.

Since 42 2010 1 n + 1 , \frac{42}{2010} \ge \frac1{n+1}, this already shows that n 46.85... n \ge 46.85... This bound is not quite good enough.

We can tighten this a bit in our case because one of the s i s_i must be divisible by the prime 67 67 since the denominator of the product is. The minimum of the product with respect to this requirement is clearly when s i = i + 1 s_i = i+1 for 1 i n 1 1 \le i \le n-1 and s n = 67. s_n = 67. So i = 1 n ( 1 1 s i ) 1 n 66 67 . \prod_{i=1}^n \left( 1-\frac1{s_i} \right) \ge \frac1{n} \cdot \frac{66}{67}. So 42 2010 66 67 n , \frac{42}{2010} \ge \frac{66}{67n}, which gives n 30 66 42 = 47.14... n \ge \frac{30 \cdot 66}{42} = 47.14...

Putting the lower and upper bounds together shows that n = 48 . n=\fbox{48}.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...