1 Contraposition
Prove the statement "if a+b < c+d, then a < c or b < d".
2 Perfect Square
A perfect square is an integer n of the form n = m2 for some integer m. Prove that every odd perfect square is of the form 8k+1 for some integer k.
3 Numbers of Friends
Prove that if there are n ≥ 2 people at a party, then at least 2 of them have the same number of friends at the party.
(Hint: The Pigeonhole Principle states that if n items are placed in m containers, where n m, at least one container must contain more than one item. You may use this without proof.)
1
4 Fermat’s Contradiction
Prove that 21/n is not rational for any integer n ≥ 3. (Hint: Use Fermat’s Last Theorem. It states that there exists no positive integers a,b,c s.t. an+bn = cn for n ≥ 3.)
