How do I prove that each number is in a pigeonhole? (Edit: figured it out, thanks!)

Question

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

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$? — Acccumulation, Sep 20 '20 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 — beginner, Sep 20 '20 at 20:20
What properties would a number need to have to not be in any pigeonhole? — It'sNotALie., Sep 20 '20 at 20:33
@It'sNotALie. the number must not be odd because if t = 0, then (2k-1)*2^0 = 2k-1 for k 1...n spits out all the odds from 1..2n-1. I'm currently thinking about the evens — beginner, Sep 20 '20 at 20:39
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 — beginner, Sep 20 '20 at 20:44
Yes, you can. Every integer is of the form $(2k-1)2^p$. So your proof is finished. — Jean-Claude Arbaut, Sep 20 '20 at 20:44
Hi, so my question was essentially asking how to prove that every integer is of the form $(2−1)2^p$. — beginner, Sep 20 '20 at 20:46
@beginner Welcome to Math SE. Note a specific case of your question, where $n = 50$, is asked at Pigeonhole Principle - numbers between $1$ and $100$, with its answer also being applicable to your case. — John Omielan, Sep 20 '20 at 23:02

score 1 · Accepted Answer · answered Sep 20 '20 at 21:09

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

How do I prove that each number is in a pigeonhole? (Edit: figured it out, thanks!)

1 Answers1