A printable PDF is available.

## Assignment 1: Due Tuesday, September 2

This assignment is a "warm-up exercise" with two purposes: one is to get you thinking mathematically again (if you're rusty!), and the other is to give me some information on your mathematics capabilities. The assignment grade will count into your final grade, but it will only count half as much as assignments later in the semester.

- Textbook, page 25, Exercise 0.2
- Textbook, page 26, Exercise 0.4
- Textbook, page 26, Exercise 0.5
- Textbook, page 26, Exercise 0.8
- Textbook, page 27, Problem 0.11
- Use induction to prove that for any
*n >= 1*, if you have*n*boolean variables*x*, then_{1},x_{2},...,x_{n}*x*if and only if an odd number of_{1}XOR x_{2}XOR ··· XOR x_{n}=1*x*variables are 1. (Note that_{i}*XOR*is the exclusive-or operation, and it is an associative operation). - Use proof by contradiction to prove the
*Pigeon-hole Principle*: Given*n*pigeons in*m*pigeon holes, there must be at least one hole containing at least*ceiling(n/m)*pigeons.