# 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, 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.)

• It's not clear what your question is. Are you asking how to prove that each number is in the form $(2k-1)*2t$ for some $k,t$? Commented Sep 20, 2020 at 20:19
• Hello! I'm asking how to prove that each number from 1...2n is in a pigeonhole. I first approached this problem by example (e.g. let n = 5) and realized that each number from 1..2n is in a pigeonhole, but I'm not sure how to prove it for an arbitrary n Commented Sep 20, 2020 at 20:20
• edited my original post Commented Sep 20, 2020 at 20:30
• wait a second ... hope this is right, but cant you express any integer as (2^e)*s, where s is odd? thus by construction, my pigeonholes will contain all values 1..2n Commented Sep 20, 2020 at 20:44
• Hi, so my question was essentially asking how to prove that every integer is of the form $(2𝑘−1)2^p$. Commented Sep 20, 2020 at 20:46

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$$.