A cell can divide into 42 or 44 smaller cells. How many divisions are needed to obtain, starting from one cell, exactly 1993 cells?

## - Solutions -
Each division adds either 41 or 43 new cells (since the initial cell disappears). Let $a$ be the number of divisions by 42 and $b$ the number of divisions by 44. We need to add 1992 cells to the initial cell, so:

$$
41 a + 43 b = 1992
$$

Thus, we have $41(a + b) + 2b = 1992$ and since $b \geq 0$, we have $41(a + b) \leq 1992$ and therefore $a + b \leq \frac{1992}{41} = 45.8 \ldots$ But we also have $43(a + b) - 2a = 1992$ and since $a \geq 0$, we have $43(a + b) \geq 1992$ and therefore $a + b \geq \frac{1992}{43} = 46.3 \ldots$. Moreover, $41(a + b) = 1992 - 2b$ shows that $a + b$ must be even, and thus finally, since $47 \leq a + b \leq 48$, we have that $a + b = 48$.

## 3 Basic Strategies

## 1 Course

This course is not strictly about combinatorics, but rather the presentation of two "basic strategies" that are important to handle in combinatorics as well as in many other areas of mathematics. A large number of arithmetic proofs, for example, rely on the pigeonhole principle.

## - Pigeonhole Principle -

If at least $n+1$ objects are placed into $n$ drawers, at least one drawer will contain at least two objects. More generally, if at least $k n + 1$ objects are placed into these same $n$ drawers, at least one drawer will contain at least $k+1$ objects. For example: knowing that a human has fewer than 300,000 hairs and that there are 3,000,000 Parisians, at least two Parisians have the same number of hairs. We can even specify that there are at least 10 Parisians with the same number of hairs. If there were 3,000,001 Parisians each with at most 300,000 hairs, we could assert that at least 11 of them have the same number of hairs.

One of the first mathematical results that can be deduced from this is that the decimal expansion of the fraction $\frac{p}{q}$ is periodic with a period strictly less than $q$. Indeed, when performing the division, each new decimal corresponds to a new remainder. Among $q$ consecutive remainders, either one is zero (and the division stops, which corresponds to a period of 1 since from a certain rank, all decimals are equal to 0), or these $q$ remainders are all between 1 and $q-1$, which proves that at least two of them, $r_i$ and $r_j$, are equal. Since each remainder determines the entire sequence of the division, $r_{i+1} = r_{j+1}, r_{i+2} = r_{j+2} \ldots$ therefore the decimal expansion will be periodic with a period of at most $|i-j| < q$.