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.

Generalize.

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(3): @ Steve - toward reasonable proof Comment 10 of 10 |
(In reply to re(2): @ Steve - toward reasonable proof by Ady TZIDON)

Ady:


We are not quite on the same page.  My "inelegant" proof is already solid.  I have shown that it is impossible to pick 26 numbers without picking more than once from one of my sets.  That is all that is needed for a solid proof.

I am not claiming, and I do not need to claim that "it is 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."

As a small bonus, it follows that any valid set of 25 numbers must contain the 10 numbers that are not in any of my sets, namely (29,31,33,35,37,39,43,45,47).  If I had constructed my sets differently I could have come up with more numbers that must be in a valid set of 25.  For instance, if my sets included (14,42) and (13,39) instead of  (14,28) and (13,26) instead of then it would follow that that 26 and 28 must be in any valid set.  So there are at least 12 numbers that must be in any valid set, namely (26, 28,29,31,33,35,37,39,43,45,47).  I would not be surprised if there were more.

  Posted by Steve Herman on 2016-11-29 08:18:48
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
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

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information