Shortlist 2012, A2¶
Domaine : Algèbre · Difficulté : ★★☆☆☆ · Proposé par : non indiqué
Concepts : Congruences, théorèmes de Fermat et d'Euler · Invariants et monovariants
Solution officielle : Shortlist officielle 2012 (avec solutions), p. 10 (page 10 du PDF)
Énoncé¶
Let \(\mathbb{Z}\) and \(\mathbb{Q}\) be the sets of integers and rationals respectively.
a) Does there exist a partition of \(\mathbb{Z}\) into three non-empty subsets \(A\), \(B\), \(C\) such that the sets \(A + B\), \(B + C\), \(C + A\) are disjoint?
b) Does there exist a partition of \(\mathbb{Q}\) into three non-empty subsets \(A\), \(B\), \(C\) such that the sets \(A + B\), \(B + C\), \(C + A\) are disjoint?
Here \(X + Y\) denotes the set \(\{x + y \mid x \in X, y \in Y\}\), for \(X, Y \subseteq \mathbb{Z}\) and \(X, Y \subseteq \mathbb{Q}\).
Indices : les idées clés
- Dans \(\mathbb{Z}\) : les trois classes modulo \(3\) conviennent.
- Relations clés : pour \(a \in A\), \(b \in B\), \(c \in C\), on a \(a + b - c \in C\), etc. ; on en déduit \(B + C = A + A\), \(C + A = B + B\), \(A + B = C + C\).
- Invariant dans \(\mathbb{Q}\) : avec \(0 \in A\), on obtient \(3r \in A\) pour tout rationnel \(r\), ce qui est absurde pour \(r = \frac{b}{3}\) avec \(b \in B\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2012 (deux solutions et une remarque).
Solution 1¶
a) Les classes modulo \(3\) donnent une telle partition :
b) La réponse est non. Supposons que \(\mathbb{Q}\) puisse être partitionné en parties non vides \(A\), \(B\), \(C\) comme dans l'énoncé. Pour tous \(a \in A\), \(b \in B\), \(c \in C\), on a
En effet, \(a + b - c \notin A\) puisque \((A + B) \cap (A + C) = \varnothing\), et de même \(a + b - c \notin B\), donc \(a + b - c \in C\). Les deux autres relations suivent par symétrie. Donc \(A + B \subset C + C\), \(B + C \subset A + A\), \(C + A \subset B + B\).
Les inclusions inverses sont vraies aussi. Soient \(a, a' \in A\), \(b \in B\) et \(c \in C\) quelconques. Par (1), \(a' + c - b \in B\), et comme \(a \in A\), \(c \in C\), on utilise à nouveau (1) pour obtenir
Donc \(A + A \subset B + C\), et de même \(B + B \subset C + A\), \(C + C \subset A + B\). En résumé,
Supposons de plus, sans perte de généralité, que \(0 \in A\). Alors \(B = \{0\} + B \subset A + B\) et \(C = \{0\} + C \subset A + C\). Comme \(B + C\) est disjoint de \(A + B\) et de \(A + C\), il est aussi disjoint de \(B\) et de \(C\). Donc \(B + C\) est contenu dans \(\mathbb{Q} \setminus (B \cup C) = A\). Comme \(B + C = A + A\), on obtient \(A + A \subset A\). D'autre part \(A = \{0\} + A \subset A + A\), donc \(A = A + A = B + C\). Ainsi \(A + B + C = A + A + A = A\), et \(B + B = C + A\), \(C + C = A + B\) donnent \(B + B + B = A + B + C = A\) et \(C + C + C = A + B + C = A\). En particulier, pour tout \(r \in \mathbb{Q} = A \cup B \cup C\), on a \(3r \in A\).
C'est impossible : prenons \(b \in B\) (car \(B \neq \varnothing\)) et \(r = \frac{b}{3} \in \mathbb{Q}\). Alors \(b = 3r \in A\), une contradiction. \(\blacksquare\)
Solution 2¶
Montrons que l'exemple de la première solution est le seul dans \(\mathbb{Z}\), puis utilisons ce fait pour la partie b).
Soit \(\mathbb{Z} = A \cup B \cup C\) une partition avec \(A, B, C \neq \varnothing\) et \(A + B\), \(B + C\), \(C + A\) disjoints. Les relations (1) sont clairement vraies dans \(\mathbb{Z}\). Fixons deux entiers consécutifs de parties différentes, disons \(b \in B\) et \(c = b + 1 \in C\). Pour tout \(a \in A\), d'après (1), \(a - 1 = a + b - c \in C\) et \(a + 1 = a + c - b \in B\). Donc tout \(a \in A\) est précédé d'un nombre de \(C\) et suivi d'un nombre de \(B\).
En particulier, il existe des couples \(c, c + 1\) avec \(c \in C\) et \(c + 1 \in A\). Pour un tel couple et tout \(b \in B\), un raisonnement analogue montre que tout \(b \in B\) est précédé d'un nombre de \(A\) et suivi d'un nombre de \(C\). Il existe aussi des couples \(b, b - 1\) avec \(b \in B\) et \(b - 1 \in A\). On s'en sert de même pour montrer que tout \(c \in C\) est précédé d'un nombre de \(B\) et suivi d'un nombre de \(A\).
En rassemblant ces observations, on obtient que \(A\), \(B\), \(C\) sont les trois classes modulo \(3\). Tous les multiples de \(3\) sont dans la partie qui contient \(0\).
Passons à la partie b). Supposons qu'il existe une partition de \(\mathbb{Q}\) avec les propriétés voulues. Choisissons trois rationnels \(r_i = \frac{p_i}{q_i}\) dans les trois parties \(A\), \(B\), \(C\) (\(i = 1, 2, 3\)), et posons \(N = 3q_1q_2q_3\). Soit \(S \subset \mathbb{Q}\) l'ensemble des fractions de dénominateur \(N\) (irréductibles ou non). Il s'obtient en multipliant chaque entier par \(\frac{1}{N}\), donc il est stable par somme et différence. De plus, si l'on identifie chaque \(k \in \mathbb{Z}\) à \(\frac{k}{N} \in S\), l'ensemble \(S\) est essentiellement \(\mathbb{Z}\) pour l'addition. Les nombres \(r_i\) appartiennent à \(S\), car
La partition \(\mathbb{Q} = A \cup B \cup C\) induit une partition \(S = A' \cup B' \cup C'\), avec \(A' = A \cap S\), \(B' = B \cap S\), \(C' = C \cap S\). Clairement, \(A' + B'\), \(B' + C'\), \(C' + A'\) sont disjoints, donc cette partition a les propriétés considérées.
Par l'unicité de l'exemple dans \(\mathbb{Z}\), les ensembles \(A'\), \(B'\), \(C'\) sont les classes modulo \(3\), multipliées par \(\frac{1}{N}\). Tous les multiples de \(\frac{3}{N}\) sont donc dans une même partie \(A'\), \(B'\) ou \(C'\). C'est vrai en particulier pour \(r_1\), \(r_2\), \(r_3\), qui sont tous multiples de \(\frac{3}{N}\). Or \(r_1\), \(r_2\), \(r_3\) sont dans des parties différentes, puisqu'ils ont été choisis dans des parties différentes. Cette contradiction achève la preuve. \(\blacksquare\)
Remarque¶
L'unicité de l'exemple dans \(\mathbb{Z}\) peut aussi se déduire de l'argument de la première solution.