The Student Room Group

Pigeonhole Principle question

Capture.PNG

I can't seem to figure out how to construct the pigeonholes here, seems like a straightforward problem.

Initially, as there are 999 natural numbers, I was thinking that I can split the this into 38 equal intervals which are 26.2895\approx 26.2895 in length so taking the floor value of this would be 26 to go along with the notion of integers - hence two of the chosen numbers MUST be in the distance of 26 from each other at most, but I'm not sure if this is the correct application of the principle?
(edited 7 years ago)
Reply 1
Original post by RDKGames
Capture.PNG

I can't seem to figure out how to construct the pigeonholes here.

Initially, as there are 999 natural numbers, I was thinking that I can split the this into 38 equal intervals which are 26.2895\approx 26.2895 in length so taking the floor value of this would be 26 to go along with the notion of integers, but I'm not sure if this is the correct application of the principle?


I'm not really sure why you're thinking in terms of intervals (you mean partitions or subsets) or why you want 38 of them. You want n partitions where n is one less than the number of choices you can make so that by the principle you can ensure two of your choices are in the same partition/subset. If you have 38 partitions then nothing is guaranteed, all 38 of your choices could be in 38 seperate partitions.

You have the natural numbers (I'm counting from 1) {1,,999}\{1, \ldots, 999\} which you can partition into {1,,27},{28,,53},,{...,999}\{1, \ldots, 27\}, \{28, \ldots, 53\}, \ldots, \{...,999\} of size 27 each. There are 37 of these subsets. So if you pick 38 natural numbers less than 1000 then two of them are...? Can you finish off from here?
(edited 7 years ago)
Reply 2
Original post by RDKGames
Capture.PNG

I can't seem to figure out how to construct the pigeonholes here.

Initially, as there are 999 natural numbers, I was thinking that I can split the this into 38 equal intervals which are 26.2895\approx 26.2895 in length so taking the floor value of this would be 26 to go along with the notion of integers, but I'm not sure if this is the correct application of the principle?

Instead of 38 equal size pigeonholes, consider 37 pigeonholes that fit 27 numbers each e.g. hole 1 holds numbers 1-27. Then think about putting 38 numbers in these holes.
Reply 3
FWIW, a different method to tackle this is to pick 38 numbers 0<a1<<a38<10000 < a_1 < \cdots < a_{38} < 1000 such that the different between any two is at least 2727. Then clearly a38a1+27×371+27×37=1000a_{38} \geq a_1 + 27 \times 37 \geq 1 + 27\times 37=1000. Contradiction.
Original post by Zacken
I'm not really sure why you're thinking in terms of intervals (you mean partitions or subsets) or why you want 38 of them. You want n partitions where n is one less than the number of choices you can make so that by the principle you can ensure two of your choices are in the same partition/subset. If you have 38 partitions then nothing is guaranteed, all 38 of your choices could be in 38 seperate partitions.

You have the natural numbers (I'm counting from 1) {1,,999}\{1, \ldots, 999\} which you can partition into {1,,27},{28,,53},,{...,999}\{1, \ldots, 27\}, \{28, \ldots, 53\}, \ldots, \{...,999\} of size 27 each. There are 37 of these subsets. So if you pick 38 natural numbers less than 1000 then two of them are...? Can you finish off from here?


Okay that seems much clearer than what I was going with before. So for 38 numbers it would make two of them be in the same partition and in maximum possible distance of 26 from each other. Would that be sufficient enough to say for the proof?
Reply 5
Original post by RDKGames
Okay that seems much clearer than what I was going with before. So for 38 numbers it would make two of them be in the same partition and in maximum possible distance of 26 from each other. Would that be sufficient enough to say for the proof?


Yes.

Quick Reply

Latest