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.)
 Inelegant proof? | Comment 5 of 10 |
We can pick at most one number from each of the following sets:
(1,2,4,8,16,32)
(3,27)
(5,25,50)
(6,12,24,48)
(7,49)
(9,18,36)
(10,20,40)
(11,22,44)
(13,26)
(14,28)
(15,30)
(17,34)
(19,38)
(21,42)
(23,46)
These 15 sets are mutually exclusive and contain 40 numbers, so 25 numbers are necessarily unused.  And, therefore we have proven that we cannot pick 26 numbers out of 50 such that no two divide each other.

However, this inelegant proof does permit generalization.

Edited on November 28, 2016, 5:11 pm
 Posted by Steve Herman on 2016-11-27 16:34:11

 Search: Search body:
Forums (0)