Sans laisser de trace

Dans une vitrine, des billes sont posées sur une table. Chaque nuit, un appareil la radiographie dans quelques directions fixées une fois pour toutes : pour chaque droite parallèle au faisceau, il compte les billes qu’elle traverse. Un faussaire veut tout emporter et poser d’autres billes, ailleurs, sans qu’aucun cliché ne change. Avec un seul cliché, c’est facile. Avec deux, il lui faut déjà un rectangle. Avec cent ? Cela dépend des billes : certaines configurations se laissent remplacer, d’autres résistent. On verra lesquelles pour deux clichés, puis que, les directions étant connues, il existe toujours des configurations que le faussaire peut remplacer, et enfin que, le nombre de billes étant connu, assez de directions interdisent toute substitution.

La partie I étudie deux clichés et dit exactement quelles configurations ils déterminent ; la partie II construit des substitutions invisibles pour n’importe quelle liste de directions ; la partie III montre qu’assez de clichés suffisent pourtant à figer un nombre donné de billes, que cette borne est exacte, et qu’une grille connue d’avance se contente d’un seul cliché.

Le plan est rapporté à un repère orthonormé, les points sont repérés par leurs coordonnées $(x,y)$.
Une direction est un vecteur non nul $d=(a,b)$ ; les droites de direction $d$ sont les droites d’équation $bx-ay=c$, $c\in\mathbb R$.
Quatre directions serviront de fil conducteur : $h=(1,0)$, dont les droites sont les horizontales $y=c$ ; $v=(0,1)$, dont les droites sont les verticales $x=c$ ; $d=(1,1)$, dont les droites sont les droites $x-y=c$ ; $d'=(1,-1)$, dont les droites sont les droites $x+y=c$.

Soit $A$ un ensemble fini de points du plan.
La radiographie de $A$ dans la direction $d$ est la donnée, pour chaque droite $\Delta$ de direction $d$, du nombre de points de $A$ situés sur $\Delta$.
Deux ensembles finis $A$ et $B$ sont indiscernables pour une liste de directions s’ils ont la même radiographie dans chacune de ces directions, c’est-à-dire si toute droite parallèle à l’une de ces directions contient autant de points de $A$ que de $B$.
Une substitution parfaite pour cette liste est un couple $(A,B)$ d’ensembles finis non vides, disjoints et indiscernables : le faussaire a remplacé $A$ par $B$ et aucun cliché ne le voit.
Les directions d’une liste sont toujours supposées deux à deux non parallèles.

I. Deux clichés

À gauche, trois billes noires et les trois billes orange qui les remplacent : chaque droite horizontale, verticale ou de pente $1$ en contient autant avant qu’après. À droite, les deux solutions du problème des quatre dames, disques et carrés : mêmes clichés dans les quatre directions de l’échiquier.

Dans cette partie, on ne dispose que des deux clichés $h$ et $v$.
Pour un ensemble fini $A$ et un réel $y$, on note $A_y=\{x : (x,y)\in A\}$ l’ensemble des abscisses des points de $A$ situés sur l’horizontale d’ordonnée $y$ ; c’est la ligne d’ordonnée $y$ de $A$.
On définit de même la colonne d’abscisse $x$, $A^x=\{y : (x,y)\in A\}$.
La radiographie $h$ de $A$ est donc la donnée des nombres $|A_y|$, et la radiographie $v$ celle des nombres $|A^x|$.

1. Montrer que deux ensembles indiscernables pour une direction ont le même nombre de points.
Décrire toutes les substitutions parfaites à un point pour la seule direction $h$.
Vérifier que $A=\{(0,0),(1,1)\}$ et $B=\{(1,0),(0,1)\}$ forment une substitution parfaite pour $h$ et $v$, puis montrer que toute substitution parfaite à deux points pour $h$ et $v$ est de cette forme : $A$ est formé de deux sommets opposés d’un rectangle aux côtés parallèles aux axes, et $B$ des deux autres.
Plus généralement, soit $N$ un entier pair et $A$ une partie de la grille $\{0,\ldots,N-1\}^2$ ayant $N/2$ points sur chacune des $N$ horizontales et des $N$ verticales de la grille ; montrer que $A$ et son complémentaire dans la grille forment une substitution parfaite pour $h$ et $v$, et en donner un exemple pour $N=4$.

2. Un rectangle commutable de $A$ est la donnée de réels $x\neq x'$ et $y\neq y'$ tels que $(x,y)$ et $(x',y')$ soient dans $A$ et que $(x,y')$ et $(x',y)$ n’y soient pas.
Montrer que si $A$ possède un rectangle commutable, il existe $B\neq A$ indiscernable de $A$ pour $h$ et $v$.
Montrer que $A$ ne possède aucun rectangle commutable si, et seulement si, deux quelconques de ses lignes sont emboîtées : pour tous $y$ et $y'$, on a $A_y\subseteq A_{y'}$ ou $A_{y'}\subseteq A_y$.
En déduire que les lignes de $A$ sont deux à deux emboîtées si, et seulement si, ses colonnes le sont.

3. On suppose les lignes de $A$ deux à deux emboîtées, et l’on se donne $B$ indiscernable de $A$ pour $h$ et $v$.
Soit $y_0$ une ordonnée telle que $r=|A_{y_0}|$ soit maximal.
Montrer que $A$ rencontre exactement $r$ droites verticales, puis que $B_{y_0}=A_{y_0}$.
En déduire que $B=A$.
Conclure qu’un ensemble fini est déterminé par ses radiographies $h$ et $v$ si, et seulement si, il ne possède aucun rectangle commutable.

II. Le faussaire

4. Vérifier que $A=\{(0,0),(2,1),(1,2)\}$ et $B=\{(1,0),(0,1),(2,2)\}$ forment une substitution parfaite pour $h$, $v$ et $d$.
Montrer qu’il n’existe aucune substitution parfaite à deux points pour trois directions.
Montrer que pour trois directions quelconques, il existe une substitution parfaite à trois points.

5. Le problème des quatre dames demande de placer quatre dames sur un échiquier $4\times4$ sans que deux d’entre elles soient sur une même ligne, une même colonne ou une même diagonale.
On repère les cases par leurs coordonnées $(x,y)\in\{0,1,2,3\}^2$.
Montrer que le problème a exactement deux solutions, $A=\{(0,1),(1,3),(2,0),(3,2)\}$ et $B=\{(0,2),(1,0),(2,3),(3,1)\}$, symétriques l’une de l’autre.
Montrer que $A$ et $B$ sont indiscernables pour $h$, $v$, $d$ et $d'$.

6. Soient $A$ et $B$ deux ensembles finis disjoints, indiscernables pour les directions $d_1,\ldots,d_k$, et $d_{k+1}$ une direction supplémentaire.
Soit $v$ un vecteur de direction $d_{k+1}$ de longueur strictement supérieure à toutes les distances entre deux points de $A\cup B$.
On note $A+v$ l’image de $A$ par la translation de vecteur $v$, et l’on pose
$$A'=A\cup(B+v),\qquad B'=B\cup(A+v).$$Montrer que les quatre ensembles $A$, $B$, $A+v$, $B+v$ sont deux à deux disjoints.
Montrer que $A'$ et $B'$ sont indiscernables pour $d_1,\ldots,d_{k+1}$.

7. En déduire que pour toute liste de $k$ directions, il existe une substitution parfaite à $2^{k-1}$ points.
Montrer que l’on peut même loger les deux ensembles dans un disque de rayon $1$.
Ainsi, aucune liste finie de directions ne permet de déceler toutes les substitutions.

Le faussaire a donc le dernier mot s’il choisit lui-même les billes après avoir vu les appareils ; la partie I a montré qu’il ne l’a pas pour n’importe quelles billes. Et si le gardien compte les billes avant de choisir ses directions ?

III. Le gardien

8. Soient $A$ et $B$ deux ensembles finis indiscernables pour $n+1$ directions, où $n$ est le nombre de points de $A$.
Montrer que $A=B$.
Ainsi $n+1$ directions deux à deux non parallèles, quelles qu’elles soient, figent toute configuration de $n$ billes.

9. Pour une liste de $k$ directions, on note $N$ le plus petit nombre de points d’une substitution parfaite.
Montrer que $k\leqslant N\leqslant 2^{k-1}$.
Vérifier que $N=k$ pour les listes $(h)$, $(h,v)$, $(h,v,d)$ et $(h,v,d,d')$.

10. Soit $k\geqslant2$ et $P$ un polygone régulier à $2k$ côtés, de sommets $V_0,V_1,\ldots,V_{2k-1}$ dans l’ordre, et soient $A$ l’ensemble des sommets d’indice pair et $B$ celui des sommets d’indice impair.
Montrer que les côtés de $P$ ont exactement $k$ directions.
Montrer que $(A,B)$ est une substitution parfaite pour ces $k$ directions.
La borne $N\geqslant k$ de la question 9 est donc atteinte pour tout $k\geqslant2$, et elle l’est pour $k=1$ par la question 1.

11. Le faussaire doit maintenant choisir ses billes parmi les points de la grille $G_N=\{0,1,\ldots,N{-}1\}^2$, où $N\geqslant2$ est connu du gardien.
Montrer que les $N^2$ nombres $x+Ny$, pour $(x,y)\in G_N$, sont deux à deux distincts.
En déduire qu’une seule radiographie, dans la direction $(N,-1)$, détermine toute partie de $G_N$.
Pourquoi cela ne contredit-il ni la question 7 ni la question 9 ?

Fixez les directions : certaines configurations leur échapperont.
Fixez le nombre de billes : assez de directions interdiront toute substitution.
Fixez la grille : une seule suffira.