Discrete Mathematics

1) In how many permutations of (1,2,..,8)  are all the even numbers out of place?

2) How many permutations of (1,2,..,8) contain none of the patterns 12, 23 and 34?

3) The nodes of a 4x82 grid are colored by one of three possible colors, Green, Yellow and

Blue. Show that no matter how the nodes are colored, we can always nd two identically

colored columns.

4) Show that, in the sequence 7, 77, 777, 7777, ... , there is a number that is divisible by2017.

5) A lattice point in R2 is a point (x; y), where both x and y are integers. Prove that if

we pick 5 lattice points in random, we can always nd 2 points so that their midpoint is

also a lattice point. (The mid point of (x1; y1) and (x2; y2) is given by (x1+y1

2 ; x2+y2

2 ).)