Non-Dividing Sets

I am asked to find the largest number of elements that a set of integers from 1 through 100 can have so that no one element in the set is divisible by another. I was told a "hint:" Imagine all the numbers 1--100 in the form 2^k m where k \ge 0 and m is odd. I have DONE this for nearly all the integers 1--100 but cannot see a viable pattern. I don't want the answer to this question just help interpreting the hint or maybe some insight into another way to solve it. Any help would be great. Thanks!

Need a hint? Click here.

Click here for the complete solution.

Hint 1

Work on the following more general problem: Among the set of integers from 1 through 2n, what is the largest subset such that no element divides another element? The reason this is a better problem is that

• you can practice on smaller examples, such as n = 1, n = 2, n = 3;
• there's a very strong pattern in the answers, which you should be able to figure out from the small cases before you have to tackle the big case of n = 50.

Hint 2

Experimentally the top half of the numbers is such a set; that is, no one of these numbers divides another:

But adding any number to this set loses the property, because any additional number k is in the range 1, ..., n and therefore divides the 2k that is already in the set. Can you prove the following two statements?

1. No element of A divides another element. (This one is easy, don't work too hard!)
2. Among any n + 1 numbers in the range 1, ..., 2n there is one that divides another. (This one is harder!)

Hint 3

Part (1) is easy. Let a and b be two elements of A , with a < b . Can b/a be an integer? No, because it is greater than 1 and less than 2!

Here's another hint for the toughie. The example of adding an element to A suggests that in this problem there is some special relation between a number and its double. If we have a set B with more than n elements, group the elements into subsets such that a number and its double go together if both are in B . More specifically, for each odd number m define the subset B_m as all numbers of B of the form 2^k m where k \ge 0.

The Rest of the Solution

If one of the B_m contains more than one element, we are done, because the smaller element divides the larger one (in the quotient of the two elements, the m cancels out, and the smaller power of 2 divides the larger power of 2. So we want to show there is a B_m with more than one element. And this is easy, because there are n such B_m (one for each odd number 1, 3, ..., 2n - 1), while there are at least n + 1 elements in B . The pigeonhole principle tells us that some B_m has more than one element.

The Pigeonhole Principle

We used a simple but very important idea called the pigeonhole principle (also called the box principle, drawer principle, or in German Schubfachprinzip). It is attributed to Peter Gustav Lejeune Dirichlet, who used the principle in number theory problems. It has several equivalent statements, such as:

• If n + 1 items are placed in n pigeonholes, then some pigeonhole contains at least two items.
• If n items are placed in n pigeonholes, such that no pigeonhole contains more than one item, then each pigeonhole has exactly one item.

There are even infinite versions:

• If infinitely many items are placed in finitely many pigeonholes, some pigeonhole contains infinitely many items.
• If uncountably many items are placed in countably many pigeonholes, some pigeonhole contains uncountably many items.

The pigeonhole principle is useful in many number theory and combinatorics problems. Here are a couple of problems for you to practice on:

• If p is a prime number and a is an integer not divisible by p , then there is an integer x such that ax is congruent to 1 modulo p . In other words, a has a reciprocal mod p . (Hint: consider all the possible values for ax , namely 0, a, 2a, ..., (p-1)a ).
• Here's another non-divisible set problem. For a positive integer n , consider the set of (n + 1)^2 integers of the form 2^a 3^b where 0 \le a, b \le n . What is the largest subset of this set with the property that no element of the subset divides another element?

References

• You can read Geoff's original question here.
• Martin Aigner and Günter M. Ziegler, Proofs From The Book , 4th edition, Springer-Verlag, 2010. Chapter 25, "Pigeon-hole and double counting" (pp. 161-171) gives several intricate examples of the pigeonhole principle, including Geoff's question.
• Wikipedia has an article, with examples, on the pigeonhole principle.