In this exercise, we consider binary representations with the least significant digit first. We also allow trailing zeros. A number is said to be odious if its representation contains an odd number of 1s.

1. Describe an automaton that accepts exactly the binary representations of odious numbers.
2. Let $\Sigma=\{0,1\}^{3}$. Describe an automaton on $\Sigma$ that accepts words of triplets such that the third components form the binary representation of a number which is the sum of the numbers represented by the first two components. For example, the word

$$
(0,0,0)(1,0,1)(0,1,1)(1,1,0)(0,0,1)
$$

will be accepted: the three components are the representations of $\overline{01010}^{2}=10, \overline{01100}^{2}=12$ and $\overline{10110}^{2}=22$ respectively, and indeed $10+12=22$.

3. Deduce an automaton on $\Sigma$ that accepts words of triplets such that the first two components are representations of odious numbers and the third is the representation of the sum of the first two.
4. Deduce an automaton on $\{0,1\}$ that accepts the representations of numbers which are the sum of two odious numbers.
5. How to answer the question "Which numbers are sums of two odious numbers?"

## Solutions
1. The following automaton is suitable:

![](https://cdn.mathpix.com/cropped/2024_05_10_10c029b6c4865f8b8ca3g-268.jpg?height=235&width=482&top_left_y=545&top_left_x=844)

2. The following automaton is suitable. The idea is to remember whether there is a carry in the addition being performed. We start without a carry, and the carry and the digits we read allow us to determine if the addition is correct and the next carry, and we must end without a carry.

![](https://cdn.mathpix.com/cropped/2024_05_10_10c029b6c4865f8b8ca3g-268.jpg?height=289&width=486&top_left_y=1032&top_left_x=288)

3. By combining the two previous points, we construct an automaton that remembers three things in its states: whether what we have read on the first line is odious or not, then whether what we have read on the second line is odious or not, and finally the presence or absence of a carry in the addition. We take the set of states to be \(\{n, y\}^3\). We obtain the following automaton.

![](https://cdn.mathpix.com/cropped/2024_05_10_10c029b6c4865f8b8ca3g-268.jpg?height=911&width=1016&top_left_y=1569&top_left_x=286)

4. This time, the choice of the two terms of the sum is free, so we will use nondeterminism to guess these terms. Consider the following automaton.

![](https://cdn.mathpix.com/cropped/2024_05_10_10c029b6c4865f8b8ca3g-269.jpg?height=914&width=974&top_left_y=248&top_left_x=284)

On the one hand, if a number is the sum of two odious numbers, the triplet of the representations of these two odious numbers and the number itself is accepted by the automaton from the previous point, so the representation of the number itself is accepted by this automaton. On the other hand, if a representation is accepted by this automaton, by reading the labels of the same arrows in the previous automaton, the first two components provide representations of two numbers that are odious and have the desired sum. Therefore, this automaton is indeed the one sought.

5. Since we have an automaton that accepts exactly the representations of the numbers we are looking for, we can find its language, which will answer the question. The method described in the proof of Kleene's theorem is one way to do this, but it is not the only one. We can also determinize the automaton and simplify it, hoping to get a sufficiently simple result from which the language can be deduced. All these calculations can be done by hand, but also by computer. We will find that the previous automaton is equivalent to the following automaton:

![](https://cdn.mathpix.com/cropped/2024_05_10_10c029b6c4865f8b8ca3g-269.jpg?height=406&width=754&top_left_y=1913&top_left_x=274)

From there, we verify that all numbers are sums of two odious numbers, except for 0 and numbers of the form \(2^{2i+1} - 1\) for \(i\) a natural number.

## VI. Group D

## Content of this part

1 First part: Algebra & Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272

1 Combinatorial Arithmetic (Aurélien & Théodore) . . . . . . . . . . . . . . . . . . . 272

2 TD - Polynomials (Tristan) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277

3 Polynomials and Dynamical Systems Modulo \(p\) (Théo) . . . . . . . . . . . . . . . . 284

4 Functional Equations (Théodore & Rémi) . . . . . . . . . . . . . . . . . . . . . . . . 293

5 The Revenge of Inequalities (Martin & Alexander) . . . . . . . . . . . . . . . . . . . 296

6 TD - Quadratic Residues & Zsigmondy (Rémi & Pierre-Marie) . . . . . . . . . . . . 311

2 Mid-course Training . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315

3 Second part: Combinatorics & Geometry . . . . . . . . . . . . . . . . . . . . . . . . . 319

1 Midpoints of Segments (Martin) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319

2 TD - Graphs (Colin) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334

3 TD - Inversion (Baptiste) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339

4 TD - Combinatorial Geometry (Emile) . . . . . . . . . . . . . . . . . . . . . . . . . . 352

5 Basics of Projective Geometry (Colin) . . . . . . . . . . . . . . . . . . . . . . . . . . 359

6 TD - Generating Functions (Yaël) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367

4 End-of-course Training . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381

5 Final Lectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385

1 Electrical Networks (Théo) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385

2 Analytic Number Theory (Mathieu) . . . . . . . . . . . . . . . . . . . . . . . . . . . 385

## 1 First part: Algebra & Arithmetic

## 1 Combinatorial Arithmetic (Aurélien & Théodore)

## Exercises