1. (a) Use the product rule to prove that the number of functions from an n-element set to an m-element set is m^n.

(b) Use a counting argument to show that the multinomial coefficient

C(mn; n, n,..., n) is between m^n and m^(mn).

2. Suppose that S is a subset of {1, 2,..., 2n} of size n+1.

(a) Show that S must contain two integers a and b such that gcd(a,b)=1.

(b) Show that S must contain two integers c and d such that c divides d.

I'm no good at "showing" and "proving" so any help is much appreciated...thanks!