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

Home > Just Math
26 out of 50 (Posted on 2016-11-25) Difficulty: 3 of 5
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.


No Solution Yet Submitted by Ady TZIDON    
Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
re: @ Steve - toward reasonable proof | Comment 8 of 10 |
(In reply to @ Steve - toward reasonable proof by Ady TZIDON)


(21,48) was in fact a typo.  I have corrected it to (21,42) in the original post.  Thanks.

After the typo is corrected, my proof (using the pigeonhole principle) is correct.  It is not possible to pick 26 numbers without picking more than one from at least one of the sets,  and that means than any set of 26 has at least one number that divides another.

The set (1,2,4,8,16,32) is correct and intentional.  The point is that I cannot pick two of those without having one divide another.  I am not claiming (and I do not need to claim) that I can get a valid set of 25 by taking the 10 that are not in any of my 15 subsets and then picking any one from each set.  Obviously, 1 and 2 are not present in any valid set of 25.  

  Posted by Steve Herman on 2016-11-28 17:24:31
Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2019 by Animus Pactum Consulting. All rights reserved. Privacy Information