Skip to main content
Message Font: Serif | Sans-Serif
 
No. of Recommendations: 3
My son, a sophomore in college taking his first proof-based course, was able to prove the following. I was both impressed and proud of him. Can you prove this statement?

Choose n+1 positive integers, all of them less than or equal to 2n. Prove that at least one of your choices must divide another of your choices.

It's easy to see that n integers isn't sufficient. Make your choices all of the numbers from n+1 to 2n, and none of your choices divide any of the others. But can you prove that any set of n+1 choices must contain a pair, one of which divides the other? --Bob
Print the post  

Announcements

What was Your Dumbest Investment?
Share it with us -- and learn from others' stories of flubs.
When Life Gives You Lemons
We all have had hardships and made poor decisions. The important thing is how we respond and grow. Read the story of a Fool who started from nothing, and looks to gain everything.
Contact Us
Contact Customer Service and other Fool departments here.
Work for Fools?
Winner of the Washingtonian great places to work, and Glassdoor #1 Company to Work For 2015! Have access to all of TMF's online and email products for FREE, and be paid for your contributions to TMF! Click the link and start your Fool career.