FLASH INFORMATIQUE FI



Solution du problème de l’été




Manuel OJANGUREN


Voici la solution du problème proposé en dernière page du numéro 4.
Le plus simple c’est de prendre le cas d’un échiquier (carré, rectangulaire ou autre) de 2^{n} cases. Ashokavardhana et Balagangadhara s’accordent sur une bijection entre les 2^{n} cases et les 2^{n} sous-ensembles de

{1,2,...,n}.

Considérons donc l’ensemble
\sum = P ({1,2,...,n})
des parties de {1,2,...,n} et rappelons-nous que \sum est un espace vectoriel de dimension n sur le corps F2 à deux éléments : on fait la somme de deux ensembles en additionnant leurs fonctions caractéristiques modulo 2 (c’est-à-dire en prenant leur différence symétrique). Les distributions de pile ou face sur l’échiquier s’additionnent aussi : on pense que chaque case avec une pièce côté face a un coefficient égal à 1, chaque case avec une pièce côté pile un coefficient égal à 0 et on additionne les distributions coefficient par coefficient, modulo2. L’ensemble des distributions devient ainsi un espace vectoriel \mathcal{D} de dimension 2^{n} sur F2. Comme base de \mathcal{D} nous choisirons les distributions D_X qui ont une pièce côté face sur la case qui correspond à X \in \sum et une pièce côté pile sur les autres.

Pourquoi ce choix  ? Parce que ce sera celui d’Ashokavardhana et Balagangadhara.
Remarquons que retourner, dans une distribution D, la pièce qui correspond à X \in \sum équivaut à additionner à D la distribution D_X .
Les prisonniers s’accordent ensuite pour associer à chaque distribution D \in \mathcal{D} l’ensemble S(D) qui est la somme des ensembles correspondant aux pièces côté face. Ils remarquent que la fonction S est une application linéaire
S = \mathcal{D} \rightarrow \sum
munie d’une section ensembliste évidente :
\sigma : \sum \rightarrow \mathcal{D} définie par \sigma(X) = D_X .
Lorsqu’Ashokavardhana entre chez le directeur, il voit une distribution D de pièces côté pile ou côté face. Il calcule S(D). Le directeur lui indique une case, qui correspond à un ensemble Z \in \sum. Il retourne alors la pièce qui correspond à S(D)+ Z, autrement dit, il ajoute à D la distribution \sigma(S(D)+ Z). Lorsque Balagangadhara entre chez le directeur, il voit sur l’échiquier la distribution

D + \sigma(S(D) + Z).
Il calcule la valeur de S, trouve :
S(D+ \sigma (S(D) + Z)) = S(D) + S\sigma(S(D) + Z = S(D) + S(D) + Z) = Z
et annonce le résultat au directeur, qui se demande comment ces deux hurluberlus ont-ils pu trouver une solution à un problème n’en ayant apparemment pas.

Cherchez ...

- dans tous les Flash informatique
(entre 1986 et 2001: seulement sur les titres et auteurs)
- par mot-clé

Avertissement

Cette page est un article d'une publication de l'EPFL.
Le contenu et certains liens ne sont peut-être plus d'actualité.

Responsabilité

Les articles n'engagent que leurs auteurs, sauf ceux qui concernent de façon évidente des prestations officielles (sous la responsabilité du DIT ou d'autres entités). Toute reproduction, même partielle, n'est autorisée qu'avec l'accord de la rédaction et des auteurs.


Archives sur clé USB

Le Flash informatique ne paraîtra plus. Le dernier numéro est daté de décembre 2013.

Taguage des articles

Depuis 2010, pour aider le lecteur, les articles sont taggués:
  •   tout public
    que vous soyiez utilisateur occasionnel du PC familial, ou bien simplement propriétaire d'un iPhone, lisez l'article marqué tout public, vous y apprendrez plein de choses qui vous permettront de mieux appréhender ces technologies qui envahissent votre quotidien
  •   public averti
    l'article parle de concepts techniques, mais à la portée de toute personne intéressée par les dessous des nouvelles technologies
  •   expert
    le sujet abordé n'intéresse que peu de lecteurs, mais ceux-là seront ravis d'approfondir un thème, d'en savoir plus sur un nouveau langage.