Given any set of 53 integers, show that there are two of them having the property that either their sum or their difference is evenly divisible by 103. (this is a pigeonhole principle problem).

See proof below.

Step-by-step explanation:

The Pigeonhole principle states that if we place n+1 objects in n places, then one of those n places must have more than one object. In theory, this may seem a very obvious principle but some of the problems which involve this principle can be more difficult than what you'd think of.

In this case we have to prove that given ANY set of integers, there are two of them having the property that either their sum or their difference is evenly divisible by 103.

This would translate to: if we have n and m integers in this set, we'd have one pair for which 103|(n+m) or 103|(n-m). This last condition gives us the clue of using modulos for this problem.

First, we're going to choose 52 pigeonholes (since we have 53 integers). Now, we're going to label the integers with numbers from 0 to 102 depending on their congruence modulo 103.

Once we've done this, we're going to place the integers in the pigeonhole according to their congruence, the pigeonholes will be numbered (0,103), (1,102), (2,101), (3,100)... (50,53), (51,52). (I.e: If the integer is congruent to 6 modulo 103, it will be placed in the (6,97) pigeonhole).

This way any two integers that are placed in one of these pigeonholes will be divisible by 103 (either their sum or their difference).

Note that we have 52 pigeonholes and 53 integers, therefore, one of the pigeonholes will have more than one number (two at least) and that's how we are sure it will satisfy the relation that their sum or their difference is evenly divisible by 103.

sine

step-by-step explanation: