From the numbers 1 to 100, what is the largest subset you can choose in which no element divides another? Prove that your bound cannot be beaten.

From the numbers 1 to 100, what is the largest subset you can choose in which no element divides another? Prove that your bound cannot be beaten.

Approach: Exhibit a large set where division is impossible for size reasons, then partition all 100 numbers into chains in which each element divides the next and count the chains.

50. The 50 numbers from 51 to 100 work, since for a < b in that range b/a < 2, so a cannot divide b. For the upper bound write each number as 2^k * m with m odd. There are exactly 50 odd values of m in 1 to 100, and each generates the chain m, 2m, 4m and so on inside the range, in which every element divides the next. Any two numbers sharing an odd part lie in one chain, so one divides the other. By pigeonhole any 51 numbers include two with the same odd part, giving a dividing pair, so 50 cannot be beaten and the largest antichain under divisibility has size 50. The same pairing shows any 51 of the numbers also contain two consecutive integers, which are coprime.

Follow-up: What is the largest subset of 1 to 100 in which no element is three times another?

Key concepts: antichain, odd part decomposition, pigeonhole.