**1.** Prove, using the induction on the number of elements *n* of set *A*, that there exactly kn functions from *A* into a set *B* with exactly *k* elements

**2.** Let *A* be an *n* element set and *B* be a k element set with *k < n*. Prove the following:

**(a)** There is onto mapping from* A* to *B*.

**(b)** There is an injective mapping from *B* to *A*.

**3.** Let *G* = (*V, E*) be a weighted connected graph. Consider graphs of the form G′ = (V, E′ ) where E′ ⊆ E. The cost of such subgraph G′ is the sum of the weights of the edges in E′ . We want to build a subgraph G′ = (V, E′ ) such that G0 is connected and the cost of G′ is as minimum as possible. We call this the minimum network design problem.

Prove that if G′ is a solution to the minimum network design problem then G′ is a tree

**4.** Let *B* be the set of all strings over the alphabet {0, 1, 2}. Consider the function *f* : *B* → *B* such that for any string *x*, the value *f*(*x*) is obtained by replacing all 0s in *x* by 1s, and all 1s in *x* by 2s, and all 2s in *x* by 0s. Is the function bijective? Explain your answer.

**5.** Consider the function f : Z² → Z² defined as follows. For (*x*, *y*) ∈ Z² : if both *x* and *y* are even or both *x* and *y* are odd then *f*(*x*, *y*) = (*x*, *y* + *1*); otherwise f(*x*, *y*) = (*x* + *1*, *y*).

Prove that f is a bijective function.

**6.** Let f : *Z* → *Z* be the function defined as: *f*(*n*) = (*−1*)*n* +* n*. Prove that f is a bijective function.

**7.** Let *A* and *B* be finite sets. Prove that if f : *A* → *B* is a bijection, then *A* and *B* have the same number of elements

**8.** Assume that there is a path in graph *G* from vertex *x* to vertex *y*, where* x* ≠ *y*. Prove that there is a path from *x* to *y* such that no vertex in this path is repeated.

## Reviews

There are no reviews yet.