"Pigeon Hole" maths question

mrmac

I'm doing some maths revision, and I clearly must have been having a brain freeze when we were doing the "Pigeon hole principle"!!

Here's the question:

Show that among any seven positive integers, there are two whose sum or difference is divisible by 10.

I've tried to figure this out, but to me this seems like a false statement, yet I'm really unsure. If someone could explain this principle, on a lower evolutionary scale than "dummies", I'd really appreciate it!

hivizman

The pigeonhole principle states that, if you have n objects, and you are required to classify these objects into m groups, where m<n, then there must be at least one group with more than one object in it.

A simple illustration is provided by a drawer full of socks, some of which are black and some of which are white. How many socks must you take out of the drawer to be sure of getting a pair the same colour (you don't care whether the pair is black or white so long as your socks match)? Here, the number of groups is 2, so if you take 3 socks out of the drawer, you must have at least two matching socks.

The question refers to any set of seven positive integers, so this hints that it is possible to divide all the integers into no more than six groups such that, if you choose any group, all of the integers in that group satisfy the condition that, if you take any two integers in the group. either their sum or difference is divisible by 10.

Think about the final digit, which can be 0, 1, 2, 3, 4, 5, 6, 7, 8 or 9. Can you split these into at most six groups that satisfy the condition? Think about pairs of digits that add up to 0 or 10 and you should get to the answer quickly.

mrmac

Ok,think I got that!
I was confusing myself by the condition "sum or difference", where there are examples of "sum" but not always examples of "difference" in any seven positive integers. i.e. it's an "OR" condition, not an "AND" condition.

So, the lowest set of seven positive integers is {1,2,3,4,5,6,7} which has two sets that matches the "sum = 10 / 10" condition, i.e. {4,6} and {7,3}. None of these elements will satisfy the second condition (but that's not needed!).

I get that now, I'm really grateful for the help, but while I'm trying to get this visualised in my head, how do I go about "proving" this for every set of seven positive integers?

Should I be trying to prove it by "contradiction" or is there some way to prove it by "modulus = 0"??

Maybe I'm over-thinking this - time to switch to Java GUIs for awhile!

hivizman

You're nearly there! You've identified two of the "pigeon-holes" - {3,7} and {4,6}.

Think of all the positive integers that end in either a 3 or a 7. Now consider any two of these numbers - they will either both end in a 3, both end in a 7, or one will end in a 3 and one in a 7. In the first two cases, the difference between the two numbers will end in 0 and hence the difference is divisible by 10. In the third case, the sum of the two numbers will end in 0 and hence the sum is divisible by 10. This shows that all the numbers ending in either a 3 or a 7 form a distinct class of integers.

Similarly, all integers ending in either a 4 or a 6 form a separate class of integers such that any two such integers satisfy the property that either their sum or their difference will be divisible by 10.

You need to find all the other such classes, such that every integer belongs to one and only one class. You should find that there are exactly six such classes. Then, by the pigeonhole principle, if you have any set of seven positive integers, there must be at least two integers in the same "pigeon-hole", as there are fewer classes (6) than integers in your set (7), and that's all you need to show.

Try to work it out yourself first and then check the answer:

The six classes consist of all the integers ending in: {0}, {1 and 9}, (2 and 8}, (3 and 7}, {4 and 6}, and {5}.