How many divisors does $68^{2008}$ have?

Exercise $10 E$ is a set containing $n$ elements. How many pairs $(A, B)$ of two sets are there such that $A \subset B \subset E$?
On a $68=2^{2} \cdot 17$, hence $68^{2008}=2^{4016} \cdot 17^{2008}$. All numbers of the form $2^{n} \cdot 17^{m}$, with $0 \leq n \leq 4016$ and $0 \leq m \leq 2008$, are therefore distinct divisors of $68^{2008}$, and conversely, all its divisors have this form. There are 4017 possible values for $n$ and 2009 possible values for $m$, hence a total of $4017 \cdot 2009=8070153$ divisors.

## $\underline{\text { Solution to Exercise } 10}$

## Brute force version:

First, we choose a set $A$ of $k$ elements in $E$. There are $\binom{n}{k}$ possibilities for $A$. Then $B$ can be chosen in $2^{n-k}$ ways. Indeed, to construct $B$, we complete $A$ with a subset of $E \backslash A$, which has $n-k$ elements. Therefore, the number of desired pairs is $\sum_{k=0}^{n}\binom{n}{k} 2^{n-k}=(2+1)^{n}=3^{n}$ by the binomial theorem.

Clever version:

To define such a pair, it suffices to determine, for each element of $E$, whether it belongs to both sets, to $A$ but not to $B$, or to neither. There are therefore 3 possibilities for each element, hence $3^{n}$ possibilities in total. (If we wanted to write it out properly, we should exhibit a bijection between the set of such pairs and the set of functions from $E$ to $\{0,1,2\}$).