Fat Setty
This problem was submitted by Dr. Jason Holland.
Let n be a positive integer. What is the largest number of elements that a set of integers from 1 through 2n can have so that no one element in the set is divisible by another element in the set?
Submit your answers to mathpotw@acu.edu. Details for submissions can be found here.
There was one correct solution to this problem submitted by Wyatt Witemeyer.
Solution to Fat Setty
We show that such a set can have at least n members by giving an example. In the set {n+1, n+2, n+3, … , 2n}, it is clear than no member is a factor of another member, and this set has nmembers.
To show that no larger set can be found, we suppose that we can find a larger set, and argue to a contradiction. So suppose D is a subset of {1, 2, 3, … , 2n} for which no element in D is divisible by another element in D, and suppose D has m members, with m > n. Let r denote the number of elements that are in both D and {1, 2, 3, … , n}. Then r is larger than 0. Now if a is in both D and {1, 2, 3, … , n} then 2a is not in both D and {n+1, n+2, n+3, … , 2n}. So the number of “slots” available in {n+1, n+2, n+3, … , 2n} for the members of D that are not in {1, 2, 3, … , n} is at most n – r. But n – r < m – r, which is the number of members of D that must be in {n+1, n+2, n+3, … , 2n}. This is a contradiction, and the result is proved.
