Pigeonhole Principle

Printable View

October 25th 2008, 11:54 PM
iloveher85

Pigeonhole Principle

Dear readers,

I'm quite stucked with this below question.

If the remainder is 0 hen an integer a is divided by an integer b, we say that a is divisible by b. Given 27 distinct integers, prove that there must be 2 integers whose sum or difference is divisible by 50.

Can anyone help me with this?

Best regards,
Roland
October 26th 2008, 07:00 AM
awkward

Quote:

Originally Posted by iloveher85

Dear readers,

I'm quite stucked with this below question.

If the remainder is 0 hen an integer a is divided by an integer b, we say that a is divisible by b. Given 27 distinct integers, prove that there must be 2 integers whose sum or difference is divisible by 50.

Can anyone help me with this?

Best regards,
Roland

Hi Roland,

Actually, if I have this figured out correctly, 26 integers are enough.

Let’s say the 26 integers are $x_1, x_2, \dots , x_{26}$ . We may assume without loss of generality that if x is in the set then –x is not; otherwise we would have x + (-x) = 0, which is divisible by 50, and we would be through. Consider the expanded set made by throwing in the negatives of the original integers, i.e.

$x_1, x_2, \dots , x_{26}, -x_1, -x_2, \dots , -x_{26}$ .

This set contains at least 2 * 26 – 1 = 51 distinct integers, taking into account the possibility that one of the integers might be 0, in which case x and –x are the same.

Now place the integers into pigeonholes based on their residue class mod 50, i.e. if the remainder on dividing x by 50 is j, then place x in the jth pigeonhole. Then there are 50 pigeonholes, numbered 0 to 49, so some pigeonhole must contain at least two integers, say $\pm x_i$ and $\pm x_j$ . If the two $\pm$ ’s are the same (two +’s or two –‘s), then $x_i + x_j$ is divisible by 50. If the two $\pm$ ’s are different (+ and – or – and +), then $x_i - x_j$ is divisible by 50.
October 26th 2008, 07:09 AM
iloveher85

After going out and take a breath,

I realise it needs 27 integers.

Assuming each pigeon hole contains 0, 1, 2, 3, 4, 5, 6, 7.....25

We have 26 holes.
thereafter, any number going into the hole will make the sum or difference divisible by 50.

Therefore Max(27/26 ) = 2
October 26th 2008, 09:09 AM
awkward

Oops, you are right, 27 integers are required! I see the problem with my first try-- it breaks down if $x_i$ and $-x_i$ end up in the same residue class. So here is a revised proof that avoids that problem, I think:

Let’s start by thinking about how many of the integers can be multiples of 25. If there are 3 or more multiples of 25, say 25a, 25b, and 25c, then at least 2 of a, b, and c must have the same parity, i.e. both even or both odd. Let’s say it’s a and b that have the same parity; then 25a – 25b is an even multiple of 25, i.e. a multiple of 50, and we’re done. So we may assume that at most 2 of the set are multiples of 25. Let’s discard those two integers (because they would cause problems in the proof below), so we still have at least 25 integers, none of which are a multiple of 25.

Let’s say the remaining 25 integers are $x_1, x_2, \dots , x_{25}$ . We may assume without loss of generality that if x is in the set then –x is not; otherwise we would have x + (-x) = 0, which is divisible by 50, and we would be through. Consider the expanded set made by throwing in the negatives of the original integers, i.e.

$x_1, x_2, \dots , x_{25}, -x_1, -x_2, \dots , -x_{25}$ .

This set contains 50 distinct integers.

Now place the integers into pigeonholes based on their residue class mod 50, i.e. if the remainder on dividing x by 50 is j, then place x in the jth pigeonhole. We exclude the residue class 0 because we earlier removed any integers which were multiples of 25. Then there are 49 pigeonholes, numbered 1 to 49, so some pigeonhole must contain at least two integers, say $\pm x_i$ and $\pm x_j$ . We know $i \neq j$ because otherwise we would have $x_i$ and $-x_i$ in the same residue class, which would imply $2 x_i$ is a multiple of 50, which would imply $x_i$ is a multiple of 25. (This is why we excluded multiples of 25 earlier.) If the two $\pm$ ’s are the same (two +’s or two –‘s), then $x_i + x_j$ is divisible by 50. If the two $\pm$ ’s are different (+ and – or – and +), then $x_i - x_j$ is divisible by 50.