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 ≥ 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 a nother way to solve it. Any help would be great. Thanks!

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:

A = {n + 1, n + 2, ..., 2n}

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?

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

Need another hint? Click here.

Click here for the complete solution.