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 credit card? use our Credit Card & Finance Calculators
Thanks to MrFahrenheit,SalvorHardin,Anonymous,johnhemming,Anonymous, for Donating to support the site
Select

 Lemon Quarter
 Posts: 4972
 Joined: November 4th, 2016, 8:17 pm
 Has thanked: 620 times
 Been thanked: 985 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: 101200. Let's call this our base camp set.
That needs us needing to find at least one more number in 1100. But every number in that range divides something in 101200, so we're losing one or more of our existing numbers. Only the 21 primes in 101200 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 (NMIN1)+1 WCs in [1..2(NMIN1)]. That implies a set comprising (NMIN1) WCs in [1..2(NMIN1)] together with both 2NMIN and 2NMIN1. 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 .. 2N1], of which there are N1. 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.

 Lemon Slice
 Posts: 319
 Joined: November 9th, 2016, 11:33 am
 Has thanked: 100 times
 Been thanked: 55 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
Cinelli

 Lemon Quarter
 Posts: 4972
 Joined: November 4th, 2016, 8:17 pm
 Has thanked: 620 times
 Been thanked: 985 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 streamofthought. Discard the false starts that led nowhere, and the remainder is about three lines.
But I expect yours has the elegance that eluded me.

 Lemon Slice
 Posts: 319
 Joined: November 9th, 2016, 11:33 am
 Has thanked: 100 times
 Been thanked: 55 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
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
Return to “Games, Puzzles and Riddles”
Who is online
Users browsing this forum: No registered users and 1 guest