One Must Divide Another

Question

Pick any 6 distinct integers from the set 1, 2, 3, dots, 10. Show that, no matter which 6 you choose, there must be two of them where one divides the other.

Accepted Answer

Pigeonhole on the odd part. Every positive integer m factors uniquely as m = 2^a cdot b, qquad b text odd. For m in 1, dots, 10, the odd part b lies in 1, 3, 5, 7, 9, only 5 possible odd parts. These are the pigeonholes; the 6 chosen numbers are the pigeons. Since 6 > 5, two of the chosen numbers, say m_1 = 2^a_1 b and m_2 = 2^a_2 b, must share the same odd part b. But then one divides the other: if a_1 le a_2, then m_2 / m_1 = 2^a_2 - a_1 is a (positive integer) power of 2, so m_1 mid m_2. blacksquare Why 6 is the threshold. Five numbers can avoid the conclusion: 6, 7, 8, 9, 10 has no pair where one divides another (check: none of these divides another). So the bound is tight, with 5 numbers it can fail, with 6 it never does. This matches the count of odd parts exactly: 5 "safe" slots, so a sixth number is forced to collide. The named idea: the clever step is choosing the right pigeonhole. Numbers themselves are not the holes; their odd parts are, because sharing an odd part is precisely what forces a divisibility chain. Picking a good invariant to map onto is the entire art of pigeonhole arguments. Why interviewers ask: this is a clean test of whether you can construct the pigeon

One Must Divide Another

Problem

Your answer

Hints