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