#### Got a credit card? use our Credit Card & Finance Calculators

Thanks to ErroneousBee,GSVsowhat,Shelford,Hypster,Wasron, for Donating to support the site

## Select

cinelli
Lemon Slice
Posts: 352
Joined: November 9th, 2016, 11:33 am
Has thanked: 118 times
Been thanked: 68 times

### Select

Can you select 101 numbers from 1, 2, 3, ..., 200 so that no number divides evenly (i.e. without a remainder) into another? If you think this is impossible, can you prove that it’s impossible?

Cinelli

UncleEbenezer
Lemon Half
Posts: 5884
Joined: November 4th, 2016, 8:17 pm
Has thanked: 787 times
Been thanked: 1289 times

### Re: Select

cinelli wrote:Can you select 101 numbers from 1, 2, 3, ..., 200 so that no number divides evenly (i.e. without a remainder) into another? If you think this is impossible, can you prove that it’s impossible?

Cinelli

Got a bit carried away ... made a mountain of a molehill ...

If you'd asked for 100 numbers it becomes trivial: 101-200. Let's call this our base camp set.

That needs us needing to find at least one more number in 1-100. But every number in that range divides something in 101-200, so we're losing one or more of our existing numbers. Only the 21 primes in 101-200 are immune. Intuitively we're reducing our solution space and cannot hope to recover it.
Looks like we might want to prove that 100 is indeed a ceiling.

Damn, we need a name for numbers satisfying your conditions. Let's call it a weakly coprime or WC set.

OK, generalise Given a number N, can we find N+1 WCs in [1 .. 2N]? For small N it's trivial by enumeration that we can find exactly N, but no more - just as we can find exactly 100 in [1..200]. For example, for N=2, our maximal subset is [2,3] or [3,4]; for N=3 it's [2,3,5], [3,4,5] or [4,5,6]. If there is any N for which we can make it work, there must be a minimum such N.

OK, we're looking for NMIN+1 WCs in [1..2NMIN], knowing that it's impossible to pick (NMIN-1)+1 WCs in [1..2(NMIN-1)]. That implies a set comprising (NMIN-1) WCs in [1..2(NMIN-1)] together with both 2NMIN and 2NMIN-1. So it's sufficient to show inductively that any WC set of N in [1..2N] includes a factor of either (or both) of 2N+1 or 2N+2. Again, we can see this is true for small N by enumeration, but a general inductive proof isn't obvious.

OK, try another tack. Properties of WC sets? The only WC set that contains 1 is {1} itself. No WC set containing 2 can contain another even number, so including 2 immediately reduces us to odd numbers in [3 .. 2N-1], of which there are N-1. So we've eliminated 1 and 2 from any potential solution. Similarly 3, 4, 5, ... each reduce solution space. But we're not there yet.

Damn, a mathematically satisfying proof is eluding me. Time for a blunt instrument.

Every number in [1 .. 100] disqualifies at least one number in [101 .. 200]. More precisely, any N in [1..100] disqualifies 100/N (rounded down) numbers in [101..200], and indeed 200/N in [1..200]. It is sufficient to show that, starting from [101..200], every new number in [1..100] we introduce disqualifies at least one number that is not already disqualified by a previous selection in [1..100]. Or that introducing a new number can never increase the number of WCs.

Any number in x in [51 .. 100] disqualifies 2x from base camp. There is no overlap. Introducing numbers in this range can never bring us to more than 100 WCs.

A number x in [41 .. 50] disqualifies both 3x and 4x from [101..200]. That's two numbers lost, making up for the overlap with 2x in [51..100] (which is also eliminated). The argument extends to x in [26 .. 50] excluding 2x in [51..100] and at least two numbers from base camp. These can never bring us above 100 WCs.

Now we have it: this line obviously converges with our existing elimination of 1 or 2 from any WC set of NMIN+1 numbers. QED.

cinelli
Lemon Slice
Posts: 352
Joined: November 9th, 2016, 11:33 am
Has thanked: 118 times
Been thanked: 68 times

### Re: Select

Well solved, UncleEbenezer. I admire your perseverance. I have a shorter, 3 line, proof. I wonder if anyone can match it.

Cinelli

UncleEbenezer
Lemon Half
Posts: 5884
Joined: November 4th, 2016, 8:17 pm
Has thanked: 787 times
Been thanked: 1289 times

### Re: Select

cinelli wrote:Well solved, UncleEbenezer. I admire your perseverance. I have a shorter, 3 line, proof. I wonder if anyone can match it.

Cinelli

pfft. Mine's not long, it's just the stream-of-thought. Discard the false starts that led nowhere, and the remainder is about three lines.

But I expect yours has the elegance that eluded me.

cinelli
Lemon Slice
Posts: 352
Joined: November 9th, 2016, 11:33 am
Has thanked: 118 times
Been thanked: 68 times

### Re: Select

Here is my solution.

Proof by contradiction. Suppose we have found 101 numbers which satisfy the condition. Express each selected number as 2^r(i) * q(i) where q(i) is odd, possibly 1. 0 < q(i) < 200 for each i. Then we have 101 odd q(i) and, since there are only 100 odd numbers in the range, two of them must be equal, = q. So two numbers are 2^s * q and 2^t * q. One divides into the other.

Cinelli