## Exercise 3

Twelve candidates for the position of mayor are participating in a televised debate. After a while, one of them declares, "Up until now, we have lied once." A second then says, "Now it makes two times." A third exclaims, "Three times, now," and so on until the twelfth affirms that before him, they had lied twelve times. The host then stops the discussion.

Knowing that at least one of the candidates correctly announced how many times they had lied before their turn to speak, determine how many candidates lied in total.
## Corrected

We will show that the first candidate told the truth and that the others lied.

Let $C_{1}, \ldots, C_{12}$ be the candidates in the order of their speaking. By contradiction, suppose that $k \geq 2$ and that $C_{k}$ told the truth. Therefore, exactly $k$ lies were told before $C_{k}$ spoke. Then:

$\triangleright$ Either $C_{k-1}$ told the truth and exactly $k-1$ lies were told before $C_{k-1}$ spoke, and thus also after. Hence, $C_{k}$ lied.

$\triangleright$ Or $C_{k-1}$ lied and exactly $p$ lies were told before $C_{k-1}$ spoke, with $p \neq k-1$. In this case, exactly $p+1$ lies were told before $C_{k}$ spoke, with $p+1 \neq k$. Hence, $C_{k}$ lied.

Finally, in all cases, we find that, for $k \geq 2$, if $C_{k}$ told the truth then $C_{k}$ lied, which is absurd. Therefore, $C_{k}$ lied for all $k \geq 2$. Since we know that at least one of the candidates did not lie, it can only be $C_{1}$.

Conversely, it is easy to verify that if exactly one lie was told before $C_{1}$ spoke, then $C_{1}$ indeed told the truth and all the others lied. This ensures that the desired situation is indeed possible. Finally, eleven candidates lied and only the first to speak told the truth.