Determine the $gcd$ of all numbers of the form $(a-b)(a-c)(a-d)(b-c)(b-d)(c-d)$ where $a, b, c, d$ range over the integers.

## Solutions
We denote $P G C D$ as the integer sought.

We only have 4 numbers at our disposal and thus no chance to certify that a prime number $p \geqslant 5$ always divides integers of this form: $\forall p \geqslant 5$, prime, $p \nmid P G C D$. Therefore, we must stick to the factors 2 and 3 that would be present in all these integers.

Regarding the factor 3, by the pigeonhole principle, we always have two of the four numbers that are congruent modulo 3, thus ensuring a factor of 3: $3 \mid P G C D$. However, we cannot ensure a second factor of 3: $9 \nmid P G C D$.

Now, modulo 4, we can have each of the 4 possible remainders, and thus only two factors congruent to 2 modulo 4: $4 \mid P G C D$ but $8 \nmid P G C D$.

For any other possibility modulo 4, the integers obtained are at least multiples of 4.

Hence:

$$
P G C D=12
$$

## 3 Pigeonhole Principle and Extremum Principle (Pierre-Marie)

This course mainly reviewed the exercises given to group B of the 2019 summer camp.

## Pigeonhole Principle

The pigeonhole principle is a simple logical observation, but despite its apparent simplicity, it allows solving very complex situations.

Proposition 1 (Simple Pigeonhole Principle).

Given $n$ drawers and $n+1$ socks placed in these drawers, there exists at least one drawer containing at least two socks.

## Example 2.

A drawer contains 2019 distinct pairs of socks. What is the minimum number of socks to be taken out to be sure of having taken out at least one pair of identical socks? Note that the drawer is so messy that it is not possible to search inside. Proof: It is a matter of finding a minimum, so we need to show both that the proposed number is a solution and that any smaller number is not a solution.

By the pigeonhole principle, if 2020 socks are taken out, then we are sure to have taken out two identical socks. On the other hand, it is possible to take out 2019 distinct socks: the number sought is 2020.

## Notation.

We denote $\lceil x\rceil$ the unique integer satisfying $x \leqslant\lceil x\rceil<x+1$. Thus, $\lceil 3\rceil=3,\lceil 1.7\rceil=2,\lceil\pi\rceil=4$ and $\lceil-2.7\rceil=-2$.

Proposition 3 (Precise Pigeonhole Principle).

Given $n$ drawers and $l$ socks placed in these drawers, there exists at least one drawer containing at least $\left\lceil\frac{k}{n}\right\rceil$ socks.

## Example 4.

Paris has two million inhabitants. A human being has, at most, 600,000 hairs on their head. What is the largest number of Parisians that can be found who have exactly the same number of hairs on their head?

Proof: Here, the drawers are the numbers of hairs and the socks are the Parisians. We then have 2,000,000 socks for 600,001 drawers (don't forget the bald Parisians, at the risk of having trouble with the SPPC, the Society for the Protection of Bald Parisians): the pigeonhole principle ensures that it is possible to find $\left\lceil\frac{2000000}{600001}\right\rceil=4$ Parisians who have exactly the same number of hairs.

Proposition 5 (Infinite Pigeonhole Principle).

Given $n$ drawers and an infinite number of socks, there exists at least one drawer containing an infinite number of socks.

## Example 6.

Show that there are infinitely many numbers composed only of 0 and 1 in decimal notation that are divisible by 2019.

Proof: Consider the set of integers consisting only of the digit 1 in decimal notation: $\{1,11,111,1111, \ldots\}$. By the pigeonhole principle, since the set of possible remainders by Euclidean division by 2019 is finite, there exists an integer $0 \leq r<2019$ such that there are infinitely many integers written only with 1s such that the remainder in the Euclidean division by 2019 is $r$. But then the difference between two of these numbers will be composed entirely of 0s and 1s in decimal notation and will be divisible by 2019. Moreover, the consideration of the number of digits ensures that we have an infinite number of such integers. We could have also simply multiplied such a number by a power of 10 to have an infinite number.

Now, we need to learn to recognize the drawers and the socks...