Skip to main content
Message Font: Serif | Sans-Serif
 
No. of Recommendations: 0
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?


Here's my son's proof. Without loss of generality we can assume the chosen integers are distinct. Proceed by induction on n. If n=1, then your numbers must be 1 and 2, and 1 divides 2, so we've established our base case.

Now assume the result for n and choose n+2 integers from among the first 2n+2. Then either 2 of the integers we chose are 2n+1 and 2n+2, or our set contains at least n+1 of the first 2n integers, in which case by our inductive hypothesis we are done.

In the former case, we have chosen n of the first 2n integers. If any of our choices divides another of our choices, then we're done, so we assume that's not the case. If one of our choices is n+1, then since we know in this case that 2n+2 is also part of our set, then we're done. Thus, we can assume that none of our choices already divide any other choice, and we also can assume that n+1 is not one of our choices.

Here's my son's insight that I'm so impressed by.

Add n+1 to our set of choices. Then our enhanced set of choices includes n+1 of the first 2n integers, so by our inductive hypothesis, one of the members of our enhanced set must divide another at or below 2n. Moreover, by construction, none of the original members of our enhanced set divided one another, so either something divides n+1 or n+1 divides something. But n+1 has no multiples at or below 2n, so one of our original choices must therefore divide n+1.

Recall that by our construction, 2n+2 is one of our choices. We now know that another of our choices is a divisor of n+1, and any divisor of n+1 is necessarily also a divisor of 2n+2, so we are done. --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.