So, I am studying computer science (bachelor). This is actually my third degree (bachelor and master in management previously). I'm new to discrete mathematics, but I find as useful as fascinating.(I often stay late at night studying it).
So one of the exercises we're doing involves the Pigeonhole Principle. I'm asked to prove with the help of the Pigeonhole Principle that in any set of seven natural numbers, there is always a pair of numbers whose sum or difference is a multiple of 10.
I used Java to generate a set of random numbers: A = {53, 44, 34, 111, 134, 564, 1}.
If we look closely at what the exercise is asking, we see that there's a universal statement. It's identified by the keyword "always". This means that my random set should match the x R y criteria.
And indeed, if we take 111 - 1 = 110, we get a multiple of 10, because 110/10 = 11. I tried this with other sets, and the principle holds.
I would like to know if the way I've formulated the solution is correct. In this case, I want to know if if I've identified the "pigeonholes" and "pigeons" correctly.
So, here's the solution formulation:
The x R y relation determines the number of pigeonholes. In this case, the relation specifies that there's at least a single pair which matches the universal statement mentioned earlier. This means that if we have 7 elements in the set, but one pair, we have 6 pigeonholes. This allows us to put 7 element in one of the boxes, with the remaining extra element into the same box (in this case, 111 and 1).
Let me know what you think, I'd appreciate it. Thanks!
Hint: If you have two numbers with the same remainder when divided by $10$, then their difference is divisible by $10$, so you are done. Otherwise, consider the six pigeonholes (remainders when divided by $10$) $\{0\}, \{1, 9\}, \{2, 8\}, \{3, 7\}, \{4, 6\}, \{5\}$. Since you have seven numbers, two of them must be in the same pigeonhole. What can you conclude?