This was one of the exercises in my textbook and I've been working on it for well over 10 hours over the span of 3 days without much progress. I don't think that it's even supposed to be a hard problem so I just give up at this point. (If it were a hard problem then I would have been more motivated knowing it's supposed to be a challenge). It asks
Assume that $n$ is a positive integer. Prove that if one chooses $n+1$ distinct odd integers from $\{1, 2, 3, \dots, 3n\}$ then at least one of these numbers will divide another.
This was on a section on the pigeonhole principle so I've used that in my failed attempts below.
My goal was to find a formula for the $m$th box such every box included all the primes and composite numbers in the set. Earlier in the book, there was an example of a problem that asked something similar. It was about choosing 101 numbers from the set of numbers between 1 and 200. And there it was easy to consider the primes, after all, there were a known number of them. But in this problem, there is no way to accurately determine the number of primes between $0$ and $3n$, at least with my current knowledge.
Attempt 1
I first thought that you could simply put $n$ and $3n$ in the same box. But where do prime numbers greater than $n$ go? Where do multiples of $5$ go? They can't be a multiple of $3$, so this won't work.
Attempt 2
What if we considered the first $n$ odd numbers in the list? Every number greater than $n$ must be a product of these numbers. Oh, but what about the primes greater than $n$ again?
Attempt 3
At this point I realized something. Formulas for groups of numbers in the $m$th box can't have prime numbers. So what if the $m$th box contained the $m$th prime number? Then the rest of the numbers in the box could be multiples of this prime. Or they could be this prime times some other number to the $k$th power ($p_m \cdot c^k$). But where do numbers like $15$ and $25$ go? If $15$ goes into the box, then $25$ can't go in the same box because $15$ doesn't divide $25$. If $25$ goes in the box, then where does $15$ go?
Details I noticed while working on the exercise
Some of these may be repeats of what I've mentioned throughout the post.
- Conjecture (could be wrong): One must choose at least one prime number. Then if this were true if we had the boxes containing the $m$th prime number then all we would have to do is prove that one other number had this prime number in its prime factorization.
- Notice that $abc$ divides $abcd$. What if we used this property to our advantage? If some box had some number, then the other boxes could be a multiple of this number.
- Again, since we don't know how many primes are in the set, then the boxes must be based on the primes. Right?
- All odd numbers in $[2n-1, 3n]$ must be expressed as the products of numbers in $[1, 2n-1]$.
Best Answer
Your attempt 1 is actually a correct approach.
Assume that for an odd integer $k$ not divisible by 3, box $k$ contains all the odd numbers from $\{1,2,\ldots, 3n\}$ that are of the form $3^ik$, where $i$ is a non-negative integer. Then among any two numbers in a box $k$, one divides the other.
For example box 1 contains all the numbers of form $3^i$ and box 5 all the numbers of form $5\cdot 3^i$
Now, you have box 1, box 5, box 7, box 11, box 13, box 17, etc, so the number of boxes is the number of odd integers in $\{1,\ldots, 3n\}$ that are not divisible by 3.
In case when $n$ is even, the number of odd integers is $3n/2$ and $n/2$ of them are divisible by 3, so the number of boxes is $n$.
In case when $n$ is odd the number of odd integers is $(3n+1)/2$ and $(n+1)/2$ of them are divisible by 3, so the number of boxes is again $n$.
So among your $n+1$ numbers at least two belong to the same box, say box $k$. Then one of the numbers is $3^ik$, another is $3^jk$, so clearly one divides another.