Prove that it is possible to choose only up to a set of 100 integers (and no more) from the first 200 positive integers - that is 1, 2,....,200; so that no integer in the set divides any other.

Well, if we exclude 100, 200 is less than twice any of the numbers in the range 101-200; a fortiori as between those numbers themselves, so that's 100 numbers. On the other hand, every number between 1 and 100 must perforce have at least one multiple (ie twice that number) in the range 101 to 200.

 More generally, for any series of positive integers 1 to n, where n is even, the numbers from n/2+1 to n will not divide each other, since n/2+1 is more than n/2: while every number from 1 to n/2 will be a divisor of at least one member of the series from n/2+1 to n, namely itself multiplied by 2, for those numbers in the range n/3+1 to n/2, or some greater multiple for those numbers that are smaller than that.

Posted by broll on 2010-04-22 15:35:59