Solution: 2017 Fall Midterm - 3

Author: Michiel Smid

Question

Let $n \geq 1$ be an integer. Consider functions $$ f : \{1,2,3,\dots,n\} \rightarrow \{1,2,3,\dots,7n\} $$ such that, for each $i$ with $1 \leq i \leq n$, $f(i)$ is divisible by 7. How many such functions are there?

(a)

$7^{n}$

(b)

$n^{7n}$

(c)

$n^{n}$

(d)

$(7n)^{n}$

Solution

So the output of the function has to be divisible by 7.

That means we only take into account the multiples of 7: $ 7, 14, 21, …, 7n $.

We only really have n options to choose from.

Because each of the n inputs can only map the values mentioned above, each only has n options.

Thus, there are $ n^n $ possible functions.