8
$\begingroup$

Q. How many integers from $0$ through $60$ must you pick in order to be sure of getting at least one that is odd? at least one that is even?

Here is my verbal solution 'without using' pigeonhole principle.

A. The list of integers $0,1,2...,60$ has $31$ even integers $30$ odd integers. So in order to be sure that at least one of the picked integers is odd, we must pick $32$ integers. This is because it may happen that first $31$ integers we pick turn out to be even. By similar argument, we find that if we pick $31$ integers from the list, then we are sure that at least one amongst them is even.

Now I want to write this solution in terms of a function, pigeons and pigeonholes.

Unfortunately the list of given integers contains total $61$ integers which is odd. Thus I can't take pigeonholes to be $\{0,1\}, \{2,3\}, \{4,5\},...,\{58,59\},\{60\}.$ The problem is that last element is a singleton set. I tried to use these pigeonholes as follows:

Let $X$ denote the set of pigeons that are picked and $Y=\{A_1=\{0,1\},A_2= \{2,3\},A_3= \{4,5\},...,A_{30}=\{58,59\},A_{31}=\{60\}\}$ denote the set of pigeonholes. Let $f : X \to Y$ be a function such that $f(x)=A_i$ whenever $x \in A_i.$

To be sure that at least one integer is odd : Suppose that we have picked $n$ number of pigeons. Then we are through when we find the least value of $n$ such that $\lceil \frac n{31} \rceil \ge 2$ (By generalized pigeonhole principle). Observe that $n=32$ fits the bill. Also $A_{31}$ is not the pigeonhole containing at least $2$ pigeons since the set $\{60\}$ has only one element. Thus one amongst the other pigeonholes must work out and we are sure that we have found at least one odd integer.

However, this argument fails when we want to be sure that at least one integer is even.

How should I think about pigeons and pigeonholes here?

EDIT: Should I consider different pigeonholes for the case of picking at least one even integer? Specifically I would just change $A_{30}=\{58,59\}$ to $A_{30}=\{58,59,60\}$ and rule out $A_{31}$ for this case. Then the least value of $n$ such that $\lceil \frac n{30} \rceil \ge 2$ is $n=31.$ Here even if $A_{30}$ turns out to be the pigeonhole with at least $2$ pigeons we are sure that one of the pigeons is bound to be even since this pigeonhole has only one odd number viz $59$ in it.

$\endgroup$
  • 2
    $\begingroup$ The edit is correct. You cannot use the same set of pigeonholes for odd and even, because in one case you need to show that $31$ pigeons cannot be placed in the pigeonholes, whereas in the other case you need to show that while $31$ pigeons can be placed, $32$ cannot. $\endgroup$ – David K Oct 18 '17 at 15:04
  • $\begingroup$ @DavidK That's what I wanted to hear. :) +1 $\endgroup$ – Error 404 Oct 18 '17 at 15:05
  • $\begingroup$ As pointed out already in an answer, OTOH, most people would accept your first argument as a pigeonhole-principle argument. It just doesn't build quite the same structure on top of the principle. $\endgroup$ – David K Oct 18 '17 at 15:09
  • $\begingroup$ @DavidK Can you elaborate more on your last sentence? "It just doesn't build quite the same structure on top of the principle." $\endgroup$ – Error 404 Oct 18 '17 at 15:13
  • $\begingroup$ Your second proof includes a particular partition of the set $\{0,\ldots,60\},$ so if you're trying to avoid picking an odd number, when you pick your $31$st number the partition not only tells you all the pigeonholes are already occupied, it tells you specifically which pigeon your new number would have to be shoved in with. That's a more specific result than you need (and when you think about it, it's completely arbitrary). $\endgroup$ – David K Oct 18 '17 at 15:22
6
$\begingroup$

Actually, your initial reasoning is a perfectly good instance of 'reasoning by pigeonholing': there are at most 31 'even' holes for pigeons to go in, so with 32 pigeons you're bound to get an odd number.

That's it!

Your second method is far more complicated than it has to be. Yes, you can make it work by making the holes $\{ 0,1 \}$, $\{2,3 \}$, etc. but also by using $\{0,3 \}$, $\{ 1,2 \}$, etc. In fact, to get as many holes as even numbers, you could even use $\{ 0,37,39 \}$, $\{2, 13 \}$, $\{ 4 \}$, $\{ 6, 19,23,29,59 \}$, etc. In other words, adding the odd numbers to the even numbers when all that really counts is how many even numbers there are is completely extraneous.

Now: I understand you tried to set it up in such a way that you can try to answer both the question about the odd and the even numbers at once ... which seemed to work fine ... until you got to the $60$ 'by-itself-hole' ... and now you get into trouble: Using $\{ 60 \}$ as a hole means it can contain exactly one 'even' pigeon, but now it cannot contain any 'odd' pigeon, and so it can't be used to do the reasoning regarding odd numbers, and using $\{ 58,59,60 \}$ means two 'even' pigeons can go into that hole, and so now it cannot be used to reason about the even numbers.

So really the best thing is to answer the question about the even numbers separately from the question about the odd numbers: with $31$ even numbers you need to pick $32$ pigeons to get an odd pigeon, and with $30$ odd numbers you need $31$ pigeons to get an even pigeon.

$\endgroup$
  • $\begingroup$ +1 Thanks! What is your opinion about my second approach? and specifically the edit. I am sorry if it's not clear from my question that I am seeking an argument by second approach. $\endgroup$ – Error 404 Oct 18 '17 at 15:11
  • $\begingroup$ @Mathmore OK, I added my thoughts about that to my Answer. $\endgroup$ – Bram28 Oct 18 '17 at 15:48
  • $\begingroup$ But by definition of my function $f$, it is automatically clear that the pigeonhole $\{60\}$ can't contain more than one element. Suppose it contains two pigeons then $f(x_i)=f(x_j)=A_{31}$ and $x_i \neq x_j.$ But by definition of $f$, $x_i,x_j \in A_{31}$ thus $x_i=x_j$. Which is a contradiction. That's why $32$nd pigeon will go to any other pigeonholes from $\{0,1\}$ to $\{58,59\}$. $\endgroup$ – Error 404 Oct 18 '17 at 17:39
  • $\begingroup$ @Mathmore Sure ... but the whole idea behind the pigeonhole principle is that pigeonholes can contain exactly one pigeon ... so you have to set up things that way. So, using $\{ 60 \}$ as a hole means it can contain exactly one even pigeon, but now it cannot contain any odd pigeon, and so it can;t be used to do the reasoning regarding odd numbers, and using $\{ 58,59,60 \}$ means two even pigeons can go into that hole, and so now it cannot be used to reason about the even numbers. So again it's best to just handle the even case separately from the odd case. $\endgroup$ – Bram28 Oct 18 '17 at 17:45
2
$\begingroup$

I'll attempt to answer the question in the sense you mean to ask it.

As noted already, your first argument actually is what many people (myself included) already would consider an argument by the pigeonhole principle. The second argument adds a lot more structure on top of this, namely the partition of the set $\{0,\ldots,60\}$ into $31$ subsets (to prove that you can choose $31$ even integers but not $32$) or $30$ subsets (to prove that you can choose $30$ odd integers but not $31$).

The extra structure adds information to any particular selection of numbers that is not really relevant to the thing to be proved; namely, if you have already chosen $31$ even integers, the partition tells you not only that the $32$nd number will be assigned to an already-occupied pigeonhole; once you actually choose a $32$nd number, the partition tells you specifically which odd number is already in the pigeonhole where you are trying to put the new number.

I don't see anything particularly wrong with this; I'm sure there are plenty of proofs where we build some structure that does a little more than the thing to be proved, because it's a convenient way to get at least what we needed. And you may have good reasons to want a partition (for example, if the principle has been defined in terms of partitions).

I would say that the partition for "$32$ numbers must include one odd number" has just a few essential properties:

  1. It consists of exactly $31$ subsets.
  2. Each subset contains exactly one even number.

Everything else is arbitrary, so you can arrange it in whichever way you want. A perfectly good partition is to have $30$ singleton subsets containing one even number each, and everything else in the last subset:

$$\{0\},\{2\},\{4\},\ldots,\{58\},\{60, 1,3,5,\ldots,59\}.$$

So now we have the (unnecessary, but harmless) extra information that if we selected two numbers for the same pigeonhole, they're both in the pigeonhole that was assigned to the number $60.$ And those double-occupancy numbers are either two odd numbers (so you have chosen at least one!) or $60$ and an odd number.

Since there's no problem putting $31$ numbers in one subset of this partition, I would be equally willing to put three numbers in one of the $30$ subsets, namely $A_{30}=\{58,59,60\}$, when making a partition for a proof that at least one number must be even if you choose $31$ numbers.

$\endgroup$
  • $\begingroup$ This is clear to me but the last paragraph. Which three numbers are you talking about in last paragraph? "...I would be equally willing to put three numbers in one of the $30$ partitions..." Thanks! $\endgroup$ – Error 404 Oct 18 '17 at 17:52
  • $\begingroup$ Sorry, I meant "subset" although I wrote "partition." I have fixed that, and also explicitly specified the three-element subset. $\endgroup$ – David K Oct 18 '17 at 18:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.