Permutations 1 There are 3 routes from Atlanta to Athens fou

Permutations:

1. There are 3 routes from Atlanta to Athens, four routes from Athens to Augusta, and 2 routes from Atlanta to Augusta. How many different ways are there to do a round trip from Atlanta to Augusta?

Pidgeon Hole Principle:

2. Show that if any eight posititve integers are chosen two of them have the same remainder when divided by 7.

Solution

2.

Assume you have 8 integers that all have different remainders. Then the numbers will be of the form (not necessarily in order):
7A+q
7B+q+1
7C+q+2
...
7H+q+7

The last number can be rewritten:
7(H+1)+q, which has the same remainder as the first one (q) so they have the same remainder. This contradicts the initial claim therefore 8 positive integers must have at least two with the same remainder when divided by 7.