(Bachet's weight problem) We have a two-pan balance with which we want to be able to weigh any object of an integer mass between $1 \text{and} 40 \text{ kg}$. What is the minimum number of integer-mass weights needed for this:

1. if these weights can only be placed on one pan of the balance?
2. if they can be placed on both pans?
1. We are forced to take a weight of $1 \mathrm{~kg}$ to be able to weigh $1 \mathrm{~kg}$. Then, to be able to weigh $2 \mathrm{~kg}$, we have two possibilities: either add another weight of $1 \mathrm{~kg}$, or add a weight of $2 \mathrm{~kg}$. The second solution is more advantageous because it allows us to weigh $3 \mathrm{~kg}$ at the same time. Similarly, to weigh $4 \mathrm{~kg}$, it is more advantageous to choose a weight of $4 \mathrm{~kg}$ rather than a weight of $1 \mathrm{~kg}$ or $2 \mathrm{~kg}$, because this allows us to weigh everything up to $7 \mathrm{~kg}$. For the same reason, we then choose $8 \mathrm{~kg}$. We notice that the choice of weights that appears is in fact the sequence of powers of two. To understand the reason, let's rephrase the problem a bit: we want integers $p_{1}, \ldots p_{k}$ (the weights) such that any integer $n$ between 1 and 40 can be written as $n=e_{1} p_{1}+\ldots+e_{k} p_{k}$ with $e_{i} \in\{0,1\}\left(e_{i}=1\right.$ if the weight is used to weigh $n, e_{i}=0$ otherwise) in the "most unique way possible," because to have an optimal number of weights, each weighing must be possible in as few different ways as possible, or even in a unique way. We have just seen such a possibility of decomposition, the binary decomposition, which is even unique! Therefore, taking weights equal to the powers of two less than 40, namely $1,2,4,8,16,32$, answers the problem. Better yet, with this we can even measure all weights up to $1+\ldots+32=2^{6}-1=63$.
2. Let's start by finding the first weights we need by hand, starting with a weight of $1 \mathrm{~kg}$. To weigh $2 \mathrm{~kg}$, we could take 2, but also 3, and this is the solution that turns out to be the most advantageous, because it also allows us to weigh 4. On the other hand, we cannot take 4 directly because with 1 and 4 we cannot weigh 2. We therefore choose 1 and 3. Similarly, the best solution next is to choose 9, because this allows us to cover all weights from 5 to 13. We see that this time, the weights that appear are powers of 3. To explain this, let's write the unique decomposition in base 3 of a number $n: n=e_{0}^{\prime} 3^{0}+\ldots+e_{k}^{\prime} 3^{k}$ with $e_{i}^{\prime} \in\{0,1,2\}$. Since in our problem we need coefficients in $\{-1,0,1\}$ (to indicate whether a weight is used, and if so, on which side of the balance), we will apply the following algorithm to our decomposition: replace all terms of the form $2 \times 3^{k}$ by $3^{k+1}-3^{k}$, then group by powers of 3 and simplify, and repeat until we have only coefficients $-1,0$ or 1. The algorithm necessarily terminates because new 2s can only appear in front of larger and larger powers of 3. On an example, this gives:

$$
\begin{aligned}
17 & =1 \times 3^{2}+2 \times 3+2 \times 1 \\
& =1 \times 3^{2}+3^{2}-3+3-1 \\
& =2 \times 3^{2}-1 \\
& =3^{3}-3^{2}-1
\end{aligned}
$$

Thus, any integer $n$ can be written as a sum of powers of 3 with coefficients $-1,0,1$, and we prove that this is unique in the same way that the base 3 decomposition is unique. Therefore, the powers of 3 provide a solution to our problem, and it suffices to have four weights $1,3,9,27$ to weigh all weights between 1 and 40, and this time, this system of weights is even optimal in the sense that it can only weigh these weights (41 cannot be weighed).

Solution to the exercise $52(21 n+4)-3(14 n+3)=-1$, so $\operatorname{pgcd}(21 n+4,14 n+3)=1$.