All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 26 out of 50 (Posted on 2016-11-25)
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.

Comments: ( Back to comment list | You must be logged in to post comments.)
 re(2): @ Steve - toward reasonable proof | Comment 9 of 10 |
(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.

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
 Posted by Ady TZIDON on 2016-11-28 23:06:14

 Search: Search body:
Forums (0)