How do I prove that each number is in a pigeonhole? (Edit: figured it out, thanks!) Consider a set of $n+1$ positive integers, each less than or equal to $2n$. Show there must always exist a pair of integers in the set, one dividing the other.
We use pigeonhole principle. For $1 \leq k \leq n$, let the $$k\text{th pigeonhole} = \{(2k-1)*2^t \mid t \text{ is a nonnegative integer, } 1 \leq (2k-1)*2^t \leq 2n\}$$ Since there are n "pigeonholes" and we must choose $n+1$ integers, there must be two integers, $i=(2k-1)*2^t$ and $j=(2k-1)*2^u$ such that $i<j$, that are in the same pigeonhole. Thus, $i | j$ since $j=i*2^{u-t}$, where $u-t$ is a positive integer.
(Edit: I've been told to use unique prime factorization, but I'm having trouble. On a gap year self-studying so any help would be great!)
(Edit 2: Essentially, I've placed numbers 1..2n into n pigeonholes, but do I prove that each number 1..2n is IN a pigeonhole? In other words, how do I prove that each number 1..2n can be expressed in the form (2k-1)*2^t. I'm not sure if I need to prove this but regardless, I'm curious.)
 A: Factor out the largest number of twos that you can from $n$. If you factor out $t$ twos, then you've factored out $t^2$. Whatever's left is odd (if it were even, you could factor out another two), so it's in the form $2k+1$. For instance, take $56$. Is it odd? No, so divide by two. We now have $28$. Is that odd? No, so divided by two again. We now have $14$, which isn't odd. We divide by two again and get $7$, which is odd, so we can stop. Since $7$ is odd, we can express it as $2*3+1$. We divided by two three times, so we factored out an eight. $56 = (2*3+1)*2^3=7*8$
Another way of doing it: write $n$ in binary. Underline the rightmost 1. Let $t$ be the number of 0s to the right of that one, and let $k$ be the number that the digits to the left of that 1 represent (note that $t$ and $k$ can be zero). Then $n = (2k+1)*2^t$. Example: 56 in binary is 111000. Underline the rightmost 1:
$11\underline 1000$
There are three 0s to the right of the underline, so $t=3$. We take the digits to the left of the underline, which are $11$. That's $3$ in binary, so $k=3$.
$56 = (2k+1)*2^t = (2*3+1)*2^3 = 7*8$
The reason this works is that just as multiplying things by ten in base ten appends a 0, multiplying things in base two by two appends a 0. So when we multiply $11$ by two, we get $110$. Then when we add $1$, we get $111$, which gets us the original digits back. But then we also have to append some 0s, and doing this means multiplying by two. There are $t$ zeros, so we're multiply by two $t$ times, which is the same as multiplying by $2^t$.
