Prove the following statement:
In any set of 26 integers chosen from the set of (1,2,3, ...50) there must be at least a pair of numbers such that one of them divides the other.
Generalize.
(In reply to
re: @ Steve - toward reasonable proof by Steve Herman)
Steve, you are preaching the converted. I fully understand your use of pigeon principle, but what you proved that for this particular partition the 26-choice is impossible- leaving open the question of finding another exclusive say 16 subsets with 10 "unused numbers".Beside this point some statements, even true, are misleading and not clear to other readers.
How about : <begin>
We can create 15 exclusive subsets out of 40 pre-selected numbers, such that it will be possible to choose one number from each of those subsets, creating a new set of 15 numbers, none of them being divisor of any other.
One possible partition is:
(1,2,4,8,16,32)
(3,27)... etc
The 40 numbers were selected leaving 10 numbers not used.
They can be added to the 15 chosen, no other can be added - therefore we have proven that we cannot pick 26 numbers out of 50 such that no two divide each other.
Example:
Chose the last member of each subset , add the 10 that did not appear in the 40 and you have 25 numbers, - and no additional can be added. <end>
You will see that the above selection is isomorphic to choosing the upper part of the full set i.e. 26-50, leaving all prime numbers intact and replacing some of the composite numbers by a lower-part not-contradicting divisors.
That bring us to the generic solution (see broll) with allowable changes, that can be easily defined.
IMHO this might be a solid proof.
Edited on November 28, 2016, 11:08 pm
re(2): @ Steve - toward reasonable proof
