Exercise 4. A group of 20 dwarves coming out of the mine sit around a round table to count the gold nuggets each has mined. They make the following observations:

$\triangleright$ The difference in the number of nuggets between two neighboring dwarves is always 2 or 3.

$\triangleright$ All the dwarves have mined a different number of nuggets.

What is the greatest possible difference in nuggets between the dwarf who found the most and the one who found the least?
## Solution to Exercise 4

Answer: The greatest possible difference is 29.

In this exercise, we aim to demonstrate that 29 is the greatest possible difference. The solution necessarily consists of two parts. First, we show that if \( n \) is the difference between the largest and smallest number of nuggets collected, then \( n \leq 29 \); this step is called the analysis. Second, we show that there exists a configuration of 20 dwarfs that satisfies the conditions of the problem and where the difference between the largest and smallest number of nuggets collected is exactly 29; this step is called the construction or synthesis.

## Analysis:

Consider a configuration of 20 dwarfs arranged in a circle and satisfying the properties of the problem. Since the difference in nuggets between two neighboring dwarfs is at most 3, we deduce that if two dwarfs \( A \) and \( B \) are separated by \( k-1 \) dwarfs, the difference in their number of nuggets is at most \( 3k \), with equality only if the difference in nuggets between each pair of neighbors between \( A \) and \( B \) is exactly 3.

Given any two dwarfs in the circle, they are separated by at most 9 dwarfs. Indeed, if both arcs of the circle connecting the two dwarfs contain at least 10 dwarfs, it means there are 22 dwarfs around the table.

![](https://cdn.mathpix.com/cropped/2024_06_04_17def46ea4e6119381e4g-06.jpg?height=588&width=696&top_left_y=1528&top_left_x=680)

In particular, between the dwarf \( P \) with the most nuggets and the dwarf \( M \) with the least nuggets, there are at most 9 dwarfs, so the difference between the two numbers is at most \( 3 \times 10 = 30 \).

However, if there is exactly a 30-nugget difference between the dwarf \( P \) and the dwarf \( M \), it means, on the one hand, that they are diametrically opposite on the table (there are exactly 9 dwarfs on each arc of the circle connecting them), and on the other hand, that on each arc of the circle, the difference in nuggets between two neighboring dwarfs is exactly 3. In particular, the two neighbors of the dwarf with the most nuggets each have 3 more nuggets than \( M \). These two neighbors have the same number of nuggets, which is excluded. Thus, the difference sought is at most 30 and cannot be 30, so it is at most 29.

## Construction:

Conversely, in the following configuration where each dwarf is represented with their number of nuggets, we verify that the conditions of the problem are satisfied and that the difference between the dwarf with the most nuggets and the dwarf with the least nuggets is exactly 29.

![](https://cdn.mathpix.com/cropped/2024_06_04_17def46ea4e6119381e4g-07.jpg?height=605&width=625&top_left_y=340&top_left_x=721)

Comment from the graders: The exercise, which is quite difficult, was moderately well done, with many partial solutions and a significant number of misunderstandings of the problem statement. Many students drew the configuration they thought was the best, which is very good. A number of students unfortunately forgot some of the constraints of the problem, which stated that the dwarfs were in a circle and that all dwarfs must have a different number of nuggets. It is also worth noting that many students, although having good intuitions, were unable to justify them.