Tessellate S.T.E.M.S (2019) - Mathematics - Category C - Set 1 - Objective Problem 2

Consider the set A = { 1 + 2 t k : k , t = 1 , 2 , 3 , 4 , } . A = \left\{1+\frac{2^t}{k} : k,t=1,2,3,4,\cdots \right\}. Calculate the density of the set of elements that are representable as finite products of elements in A A . That is, if we choose an arbitrary natural number, what is the probability of having the chosen natural number, being a finite product of elements in A A .

1 e \dfrac{1}{e} 1 2 \dfrac{1}{2} 0 1

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
Dec 28, 2018

In fact, any positive integer can be written as a finite product of elements of A A (if we allow 1 1 to be the empty product).

The proof proceeds by induction. The base case is N = 1 , N=1, which is representable via the empty product; you can also use 2 = 1 + 2 2 , 2 = 1+\frac22, 3 = 1 + 2 1 , 3 = 1+\frac21, and 4 = ( 1 + 2 2 ) ( 1 + 2 2 ) 4 = (1+\frac22)(1+\frac22) as small examples if it helps.

Now suppose that every integer in [ 1 , 2 a ] [1,2^a] is representable, where a 1. a \ge 1. We will show that any integer in ( 2 a , 2 a + 1 ] (2^a,2^{a+1}] is representable. This is easy enough: suppose 2 a < N 2 a + 1 2^a < N \le 2^{a+1} ; then N = ( 1 + 2 a N 2 a ) ( N 2 a ) , N = \left( 1 + \frac{2^a}{N-2^a} \right) (N-2^a), and N 2 a N-2^a is representable by the hypothesis, so N N is representable. So if every integer in [ 1 , 2 a ] [1,2^a] is representable, then every integer in [ 1 , 2 a + 1 ] [1,2^{a+1}] is representable. This shows by induction that every positive integer is representable, so the density is 1 . \fbox{1}.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...