One of my favorite problems (and solutions!)

51 numbers are chosen at random from the counting numbers 1, 2, …, 100.  Will those 51 numbers always contain a “consecutive pair”?  That is, will there always be an N so that N and N+1 are in among your 51 numbers?

There are a number of reasons that I like this problem, but the main one is the surprising result that’s proven in the process of solving the problem.

We’ll use the Pigeonhole Principle, which is a common sense result that can be summarized as follows:  If you have more objects than places to put them, when all of the objects are “put away”,  at least one of the places must contain at least two objects.

To model the problem, imagine that you have 100 ping pong balls 50 small boxes (large enough to hold 2 ping pong balls).  The ping pong balls are individually labeled with the natural numbers from 1 to 100, then placed in a large container and the boxes are labeled in pairs: the first box is labeled [1 2], the second box is labeled [3 4], and so on (officially, box K is labeled [2K-1  2K]).  Notice that each ball will have exactly one box whose label includes the number on the ball.

Now, pick 51 balls from the container (therefore choosing 51 numbers from 1 to 100).  Taking each of the 51 balls one at a time, place them in the box whose label includes the number of the ball.  Since there are 51 balls and only 50 boxes, at least one of the boxes must contain more than one ball, which mean at least one of the boxes has to contain both balls whose numbers match the the label on the box.  That is, at at least one pair of the balls are labeled with consecutive numbers, which solves the problem. Namely,

If 51 numbers are chosen at random from the natural numbers 1, 2, … , 100, then there will always be a consecutive pair of numbers among the 51 chosen numbers.

Interesting result, right?  Well, wait, because there’s a lot more to this than might first appear.  In fact, what we proved was that there will always be a consecutive pair chosen for which the smaller of the two numbers is ODD.

Now, that on its own might not seem so out of the ordinary, since you might expect that, since there are the same number of odds and evens from 1 to 100, there must also be a consecutive pair (among the 51 chosen numbers) in which the smaller of the two numbers is EVEN.  Shouldn’t there be some sort of symmetry to this problem so that anything true of odd numbers must also be true for evens? However, this is NOT guaranteed – in fact there are many examples of 51 numbers (from 1 to 100) among which there are no consecutive pairs that “start” with an even number.  For example, the 51 chosen numbers COULD BE 1, all the even numbers, for which the only consecutive pair is 1 and 2.

So, there will ALWAYS be a pair of consecutive numbers in which the smaller is odd, but there MIGHT NOT be a pair of consecutive numbers in which the smaller of the numbers is even.  Why is our intuition that evens and odds should somehow be “the same” so wrong in this case?

Well, in a nutshell, it’s fairly easy to see what the big difference is: In the numbers from 1 to 100, there are 50 consecutive pairs in which the smaller of the pair is odd (1 and 2, 3 and 4, 5 and 6, … , 99 and 100), while there are only 49 consecutive pairs in which the smaller of the two numbers is even (2 and 3, 4 and 5, … , 98 and 99), so it’s more likely to pick an “odd starting consecutive pair” than to pick an “even starting consecutive pair”.

In terms of the method of our proof, if we instead forced our pairs to start with an even number, our boxes would be labeled [2 3], [4 5], [6 7], … , [98  99], but this collection of boxes has a significant problem: two of the numbers (1 and 100) are missing, so we need another box, which we’ll have to label [1 100].  Now, when our 51 numbers are chosen, at least one of them must have 2 ping pong balls in it. However, this box MIGHT BE the one labeled [1   100], so there might not be a consecutive pair “starting” with an even number.

 

Leave a Reply

Your email address will not be published. Required fields are marked *