Radjaïdjah Blog

lundi 2 août 2021

Hedged Yield Farming as a Service

With Decentralized Finance (DeFi) attracting more and more users as globalization of liquidity empowers protocols to offer higher returns than legacy (TradFi) finance, this draft describes a potential financial business "Hedged Yield Farming as a Service" whose aim is to offer profits to customers by investing funds into high-APY crypto pools or farms in a market-neutral way.

Lire la suite...

jeudi 4 février 2021

Galois theory

Today, the best thing to do is probably to (re-)study Galois theory.

Here is a great online Galois theory course by Richard E. Borcherds (Fields medal).


lundi 25 janvier 2021

SPACompliqué - faut-il investir dans les SPACs ?

Vous connaissez Ark Invest ? Ce fonds d'investissement spécialisé en innovation disruptive[1] a plusieurs composants : ARKK (innovation tech), ARKQ (robotique), ARKW (Internet), ARKG (génomique), et ARKF (fintech). Tout récemment, l'annonce par sa charismatique CEO Cathie Wood de la création future d'un nouveau fonds ARKX spécialisé dans l'exploration et la technologie spatiale a fait bondir le cours de l'action Virgin Galactic, la société du milliardaire Richard Branson spécialisée dans l'exploration spatiale humaine.

Or, ce qu'il y a de rigolo avec Virgin Galactic, c'est la manière originale avec laquelle cette boîte est entrée au New York Stock Exchange. En juillet 2019, alors entreprise non cotée en bourse, elle annonçait son intention de fusionner avec la société Social Capital Hedosophia de Chamath Palihapitiya (Chamath pour les intimes[2]). Trois mois plus tard l'accord était signé par les deux parties et voilà VIrgin Galactic était cotée, avec un joli symbole SPCE. Social Capital Hedosophia était un SPAC, de symbole IPOA.

Un SPAC (Special Purpose Acquisition Company) est une société-coquille dont l'unique but est de lever des fonds afin de fusionner avec une entreprise. Investir dans un SPAC, c'est en quelque sorte donner quitus à ses dirigeants afin qu'ils trouvent une bonne entreprise avec qui fusionner. Acheter des parts d'un SPAC est donc une forme d'investissement par procuration.

Note : le Radjaïdjah Blog ne propose bien sûr pas de conseils financiers en quoi que ce soit.

Notes

[1] Ark Invest a aussi une unité de recherche ; ainsi en est-il pour ce rapport sur Bitcoin.

[2] Après l'accomplissement de son programme de 26 SPACs IPOA-IPOZ, on peut imaginer Chamath un jour à la Maison Blanche.

Lire la suite...

vendredi 1 janvier 2021

Bonne année 10 − 9 + 8 ⋅ 7 ⋅ 6! / 5 / 4 + 3! / 2 + 1

Le Radjaïdjah Blog souhaite une très bonne année 2021 à tous ses lecteurs :)

mardi 10 novembre 2020

L'art des maths

Le colloque Wright pour la science 2020 était consacré cette année à l'art des mathématiques. À distance, C19 oblige.

Au programme :

Le chaos: imprévisible mais compréhensible (Etienne Ghys)

Il est inhabituel qu’une idée mathématique se diffuse dans la société. C’est pourtant le cas avec la théorie du chaos, popularisée grâce à l’effet papillon, imaginé par le météorologue américain Edward Lorenz qui, en 1972, a posé la fameuse question: «Le battement des ailes d’un papillon au Brésil déclenche-t-il une tornade au Texas?». L’idée dans cette image est qu’une cause minime peut avoir de grandes conséquences. Mais peut-on résumer la théorie du chaos d’une manière aussi simpliste? Une théorie scientifique peut-elle se contenter d’énoncés négatifs? Les mathématiciennes et les mathématiciens sont-ils responsables de la transmission inadéquate de cette théorie? Cette conférence s’appliquera à traiter de ces questions et, en particulier, à décrire le côté positif de la théorie. Car il y en a. En effet, il arrive que le chaos engendre une espèce d’ordre. Les systèmes chaotiques sont peut-être imprévisibles mais ils sont loin d’être incompréhensibles.

Le désordre, le hasard et les grands nombres (Laure Saint-Raymond)

Le désordre augmente de manière irréversible. Cette affirmation ne concerne pas forcément la chambre d’un enfant ni la marche du monde. Elle est l’énoncé du second principe de la thermodynamique, exprimé par le physicien Sadi Carnot en 1824. C’est un principe que l’on peut expérimenter tous les jours. Lorsqu’on verse du lait dans de l’eau, par exemple, les deux liquides se mélangent et ne restent pas séparés l’un de l’autre. Les billes à jouer contenues dans un sac ne vont pas s’aligner spontanément selon leur couleur mais se mêler de manière aléatoire. S’il est facile de mélanger deux gaz, il est quasi impossible de les séparer une fois réunis. Cet exposé propose d’étudier un modèle mathématique simple qui explique pourquoi nous pouvons observer un mélange spontané mais pas le phénomène inverse. Spoiler alert: la clé pour comprendre cette irréversibilité temporelle se trouve dans la théorie des probabilités et plus précisément dans la loi des grands nombre.

Un voyage mathématique De l’infiniment petit à l’infiniment grand (Martin Hairer)

Le monde minuscule des particules et des atomes et celui gigantesque de l’univers tout entier sont séparés par environ une quarantaine d’échelles de grandeur différentes. En passant de l’une à l’autre, les lois de la nature peuvent parfois se comporter de manière drastiquement différente, obéissant tantôt à la physique quantique, à la relativité générale, ou encore à la mécanique classique de Newton, sans parler des autres théories intermédiaires. Comprendre les transformations qui s’opèrent d’une échelle à l’autre est une des grandes questions classiques en mathématiques et en physique théorique. Cet exposé a pour objectif d’explorer comment ces questions informent et motivent encore des problèmes intéressants en théorie des probabilités et pourquoi des «toy models», malgré leur caractère superficiellement ludique, peuvent parfois conduire à certaines prédictions quantitatives.

La musique des formes (Alain Connes)

La physique quantique, en particulier la mécanique des matrices, a exercé une profonde influence sur les notions mathématiques d’espace géométrique. Cette conférence expliquera ce lien en traitant, entre autres, de «spectres» et de la «musique des formes». En effet, si les caractéristiques géométriques d’un instrument, par exemple, déterminent les sons qu’il peut produire, inversement la connaissance de la gamme et des accords produits par un objet suffisent à reconstruire sa forme. Cette propriété permet de caractériser les formes géométriques à partir d’invariants qui ne font pas référence à un système de coordonnées. La nouvelle géométrie qui en découle, illustrant le lien mathématique entre perception visuelle et auditive, est riche d’applications en physique, en particulier pour la gravitation et la physique quantique. Ce sera d’ailleurs aussi l’occasion de discuter de la signification des notions de variabilité et de l’émergence du temps.

Les mathématiques : art ou science ? (Stanislas Smirnov)

Les mathématiques sont une science étonnante et mystérieuse. Depuis l’époque de Platon, les philosophes se demandent si les objets mathématiques sont imaginaires ou réels, tandis que les mathématiciens et mathématiciennes démontrent des théorèmes, souvent sans s’interroger sur leur rapport à la réalité. En même temps, des pharaons d’Egypte et des rois de Babylone avaient déjà saisi l’importance pratique des mathématiques, sans parler des progrès technologiques recents reposant en grande partie sur des applications de notre science.

D’où viennent les mathématiques ? Comment les scientifiques choisissent-ils des problèmes à résoudre et pourquoi trouvent-ils les mathématiques si fascinantes ? Pourquoi la science « imaginaire » est si utile dans le monde réel ? Cet exposé ne parviendra pas à répondre à ces questions, mais essaiera de jeter un peu de lumière sur la recherche en mathématiques.

Bonus : une présentation par l'auteur du Radjaïdjah Blog sur le mathématicien Benoît Mandelbrot.

Enfin, ceux qui s'interrogent sur la finalité des maths pourront lire À quoi servent les maths ? (2015).

lundi 27 avril 2020

Srinivasa Ramanujan 1887-1920

Srinivasa Ramanujan

These results must be true, because, if they were not true, no one would have the imagination to invent them.

G.H. Hardy on Ramanujan

jeudi 2 avril 2020

La légende de Sissa

Comme il faut bien se détendre un peu, une courte histoire qui n'a rien à voir avec le Coronavirus, la Légende de Sissa. Elle a été écrite autour des années 1250 par Ibn Khallikan, un historien kurde qui vivait au sein de l'Empire Abbasside (aujourd'hui Irak).

À l'époque, le roi d'Inde, Shihram, était un sombre tyran qui opprimait constamment ses pauvres sujets. Or, l'un d'entre eux, Sissa fils de Dahir, inventa le jeu d'échecs pour le roi, dans le but de lui montrer qu'il avait besoin des autres pour le protéger et qu'il était donc important de prendre soin de tous ses sujets.

Le roi Shihram était si impressionné qu'il ordonna que le jeu d'échecs devait être conservé dans les plus grands Temples en tant que bijou national et merveille du monde, et enseigné partout. En particulier, c'était un excellent moyen d'entraîner les généraux à l'art de la guerre.

Le roi demanda à Sissa si celui-ci désirait une récompense pour cette fantastique invention. La légende dit que le sage Sissa déclina poliment, mais le roi insista.

Sissa apporta donc un échiquier vide et demanda au roi de déposer un grain de riz sur la première case, deux grains de riz sur la suivante, puis quatre sur la suivante, et ainsi de suite en doublant le nombre de grains de riz à chaque nouvelle case, jusqu'à avoir parcouru toutes les cases de l'échiquier. Le roi, surpris par la modestie apparente du cadeau demandé, donna immédiatement son accord tout en commentant qu'il aurait personnellement demandé bien plus. Il ordonna à ses esclaves d'apporter le riz nécessaire.

Tout se passa bien au début, toutefois le roi et ses conseillers furent surpris de voir qu'arrivés à la moitié de l'échiquier, la trente deuxième case demandait plus de quatre milliards de grains de riz, soit environ cent mille kilos. Le cadeau n'était donc pas si modeste, et Sissa semblait moins stupide. Un peu plus tard, le conseiller principal du roi lui expliqua que l'ensemble des récoltes de l'année et de toutes les années précédentes ne suffiraient pas à payer la récompense de Sissa[1].

Note

[1] On pourrait nommer nombre de Sissa (Sissa number) le nombre de grains de riz requis, soit \( 1+2+4+...+2^{63} = \sum_{k=0}^{63} 2^{k} = 2^{64}-1 \).

jeudi 14 mars 2019

pi Day

A treat for pi day (3.14).




Happy π day!

mercredi 26 avril 2017

Uncaptcha me

Celles et ceux qui ont déjà posté un commentaire sur le Radjaïdjah Blog ont remarqué qu'ils avaient dû résoudre un petit problème de maths afin de valider l'envoi de leur message.

Ceci afin d'éviter le spam des commentaires par des robots. En effet, le serveur du blog compare le résultat entré par l'utilisateur avec la solution du problème mathématique, et en cas de discordance envoie le commentaire dans un vortex du cyberespace (/dev/null pour les intimes).

En vérité cette protection élémentaire contre le spam est assez facile à contourner.

La plupart des sites voulant s'assurer que l'utilisateur est humain ont recours à des CAPTCHAs (Completely Automated Program to Tell Computers from Humans Apart).

Toute personne dotée de l'esprit d'un programmeur a un jour voulu passer un CAPTCHA de façon automatisée.

Un entraînement à cela est offert via CAPTCHA me if you can, un défi où il s'agit de se poser les bonnes questions (et trouver les bonnes réponses) afin de coder la validation automatique d'un CAPTCHA élémentaire, comme par exemple :

Uncaptcha Me

Plus généralement, root-me propose de nombreux défis ayant trait à la sécurité informatique, répartis dans diverses catégories :

  • App - Script
  • App - Système
  • Cracking
  • Cryptanalyse
  • Forensic
  • Programmation
  • Réaliste
  • Réseau
  • Stéganographie
  • Web - Client
  • Web - Serveur

Entre analyser des ELF, décoder le traffic réseau, identifier des antécédents de hashs, utiliser parcimonieusement la mémoire pour insérer des overflows, trouver rapidement un terme lointain d'une suite récurrente, retrouver une image XORée, et bien plus encore, le site root-me, une plateforme d'apprentissage dédiée au hacking et à la sécurité de l'information propose une large palette d'exercices qui ravira petits et grands.

Un test de Turing est une catégorisation de comportement parmi deux groupes : humains et ordinateurs. Un CAPTCHA est ainsi suppposé être à même de valider la preuve d'un travail humain. Ce qui s'oppose à la preuve de travail informatique (proof of work) sous-jacente à la validation des blocs au sein du protocole Bitcoin, qui est basée sur l'idée du Hashcash, originalement conçu pour... la lutte anti-spam pour les e-mails.

lundi 30 janvier 2017

Labyrinthe Magique

Pour les amateurs de mathémagie, voici un tour présentant une certaine esthétique mathématique, qui ravira petits et grands.

Description (extraite du site Mayette Magie) :

---

Le Magicien propose à un spectateur de faire une partie de Labyrinthe Magique.

Le Magicien montre une espèce de plan sur lequel il y a cinq points de départ, et cinq points d'arrivée.
Il demande au spectateur de choisir un point d'arrivée (le choix est complètement libre), qui sera le point d'arrivée du vainqueur.
Puis il lui demande de choisir les quatre points de départ qu'il va utiliser pour lui-même.
Le seul point de départ restant sera celui du Magicien.
Il est évident que le spectateur aura définitivement toutes les chances de gagner.

Le plan est déployé, et on constate qu'il n'y a aucun tracé entre le départ et l'arrivée.

Le Magicien sort alors quatre Cartes Labyrinthes.
Sur chaque carte, il y a des lignes qui se croisent. On demande au spectateur de disposer les cartes dans l'ordre, et dans le sens qu'il désire (aucun forçage, aucune influence d'aucune sorte), afin de relier les points de départ et d'arrivée de manière complètement aléatoire.

Enfin, le jeu peut commencer !

Le spectateur suit lui-même les lignes à partir de chacun de ses propres points de départ (ceux qu'ils a choisis pour lui-même). Il sera à chaque fois perdant !
La dernière ligne, celle que le spectateur a déterminé pour le Magicien, est la ligne gagnante !

---

Magic Maze

Et la démo vidéo.

Le défi du jour pour les lecteurs du Radjaïdjah Blog : comment ça marche ?

Indice 2 (donne quasiment la solution) Indice 2 (donne quasiment la solution)

Penser aux permutations circulaires du groupe symétrique à 5 éléments : i-ème carte = (1 2 3 4 5)i.

Ce petit tour vendu par le fabricant japonais Tenyo sous le nom de Magic Maze est une version modernisée de Light the Lamp (démo vidéo), apparu dans les années 70, où le but était cette fois d'allumer une ampoule.

Une fois que vous avez compris le principe, vous pouvez bien sûr fabriquer vos propres cartes, éventuellement avec plus où moins de points de départ et d'arrivée, et créer votre propre histoire (loterie, prédiction, chasse au trésor...). Cela peut être présenté comme un tour classique, ou un tour où le spectateur devient le magicien.

Ou même, pour ceux qui veulent gagner un peu d'argent ou un bisou, sous la forme d'un pari avec une ou plusieurs victimes :)

vendredi 30 septembre 2016

Bonne année 5777

Devinette : à Paris, l'hôtel Richelieu possède 100 chambres, numérotées de 1 à 100, alignées le long d'un grand couloir. Chaque chambre est munie d'un interrupteur individuel permettant d'y allumer la lumière ou de l'éteindre. C'est la nuit, et toutes les chambres sont éteintes. À l'entrée du couloir se trouvent cent personnes. La personne n° 1 traverse le couloir et appuie sur tous les interrupteurs, changeant ainsi l'état de toutes les chambres. Puis la personne n°2 traverse le couloir et appuie sur un interrupteur sur deux, changeant ainsi l'état des chambres 2, 4, 6, etc. Ensuite, la personne n°3 vient appuyer sur un interrupteur sur trois, changeant l'état des chambres 3, 6, 9, 12, etc. Et ainsi de suite jusqu'à ce que la centième personne soit passée. Question : combien de chambres sont-elles allumées après le dernier passage ?

Indice Indice

Quel est l'état final de la centième chambre ?

Réponse Réponse

À la fin, il y aura 10 chambres allumées. À vous de comprendre pourquoi...

Sans transition, nous célébrons ce dimanche l'an 5777 du calendrier séléno-solaire hébraïque.

Pommiel : le meilleur usage d'un iPhone

5777 est un nombre semi-premier, en tant que multiple de deux nombres premiers : 5777 = 109 * 53. Plus précisément, 5777 appartient :

La nouvelle année juive commémore non pas la création du monde, mais celle de l'homme.

שנה טובה ומתוקה

mercredi 21 septembre 2016

Enigmatron

Il y a beaucoup de sites dont le but est de réaliser un parcours en résolvant des énigmes ou défis. Ouverture Facile en est un exemple pionnier, avec des énigmes en flash. De même Notpron, en anglais, est connu pour sa difficulté, avec seulement 0,0001% des joueurs qui ont fini les 140 niveaux.

Enigmatron est un autre site de ce genre made in Switzerland, où la plupart des énigmes sont de nature ludique et/ou scientifique (maths, logique, informatique, cryptographie...) et où une certaine capacité à faire des recherches pertinentes sur internet est requise.

Enigmatron

Parfois il est utile d'essayer de se mettre à la place du créateur des énigmes pour comprendre le raisonnement sous-jacent à un problème.

Si vous êtes perdus face à une énigme, il y a un système d'indices pour vous aider, un forum, et il est même possible de demander de l'aide en commentaire sur cet article.

lundi 15 août 2016

Clefs privées : attrapez-les toutes

Note : cet article est pour le moment plus une trame qu'autre chose, il sera mis à jour.

Une clef privée Bitcoin, c'est quoi ? C'est simplement un nombre de 256 bits. Il y a 2^256-1 c'est-à-dire environ 10^77 clefs privées. Tout nombre de 256 bits, c'est-à-dire tout nombre entre 0 et 2^256 (sauf 0), constitue une clef privée.

Le secret d'une clef privée est uniquement sa valeur. Donc, choisir une clef privée simple, c'est prendre le risque que quelqu'un la trouve et transfère les bitcoins susceptibles d'y être indexés.

Une clef privée "simple", c'est quoi ? Par exemple :

0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001

FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF

Disons, des clefs de faible entropie binaire.

Autre exemple : les brainwallets basiques[1]. Par exemple :

$ echo -n bitcoin|sha256sum|cut -d ' ' -f 1
6b88c087247aa2f07ee1c5956b8e1a9f4c7f892a70e324f1bb3d161e05ca107b

$ echo -n monkey|sha256sum|cut -d ' ' -f 1
000c285457fc971f862a79b786476c78812c8897063c6fa9c045f579a3b2d63f

Disons, des hashs de mots du dictionnaire, rapides à inverser avec des rainbow tables. Le deuxième exemple a pour adresse 145d1kjpDo55zVWTUVphYXm8ovNfMw55Jn, qui a visiblement été utilisée.

brainflayer est un logiciel écrit par Ryan Castellucci, dont la tâche est de :

  1. calculer les clefs privées générées à partir de mots du dictionnaire, via des algorithmes simples (sha256, etc)
  2. chercher lesquelles des clefs publiques correspondantes sont dans une liste de clefs publiques donnée en argument (l'algorithme de recherche utilise un filtre de Bloom probabiliste pour gagner en vitesse)

À titre d'exemple le court fichier example.hex donné contient des clefs publiques de brainwallets générées simplement par sha256 de certains mots du dictionnaire anglais.

Les premiers tests de ce logiciel, effectués dans un but pédagogique, ont donné des résultats édifiants : Stealing bitcoin with maths.

Pour implémenter plus efficacement le concept de brainwallet, 3 éléments sont à prendre en compte :

  1. la complexité du mot de passe (password entropy) (loin d'être simple)
  2. le salage du mot de passe pour individualiser les hashs (password salting) (pour contourner les rainbow tables)
  3. la vitesse d'exécution de l'algorithme de hachage (key stretching) (sans comparaison douteuse, plus ça prend de temps mieux c'est)

Et c'est cette approche que suivent par exemple les warp wallets.

Note

[1] Autre cas, un programmeur malintentionné d'un générateur d'adresses vanity (même hors-ligne) peut très bien s'arranger pour que les clefs privées des adresses engendrées soient facilement retrouvables, ne serait-ce qu'en scannant les clefs privées candidates à partir d'une clef quelconque qu'il connaît et que le programme utilise comme point de départ.

lundi 25 juillet 2016

Comment lacer ses chaussures

Vous cherchez un noeud solide pour vos chaussures, baskets, ou crampons ? Un article à lire si vos lacets se défont régulièrement.

Il y a en gros deux façons de faire un noeud classique de laçage de chaussures : une version solide et une version faible, topologiquement différentes.

Effectuez-vous la technique solide ? Nous allons essayer de répondre à cela de manière succinte. Le noeud de chaussure se fait essentiellement en 3 étapes : la demi-clef, la boucle, et l'enlaçage.

  • Étape 1 (demi-clef) : si vous passez le brin gauche du lacet par-dessus (devant) le brin droit, comptez un point, sinon, zéro.
  • Étape 2 (boucle) : si vous faites la boucle à gauche comptez un point. si c'est à droite : zéro.
  • Étape 3 (enlaçage) : si l'enlaçage passe d'abord devant la boucle, puis derrière, comptez un point, dans le cas contraire zéro.
  • Bilan : si vous avez un nombre total de points impair, vous faites la version solide, si vous avez un nombre total de points pair vous faites la version faible !

(Évidemment les plus informaticiens des lecteurs auraient trouvé plus simple de XORer.)

Si la conclusion est que vous effectuez la version faible, pas de problème ! Vous pouvez passer à la version solide en inversant une des trois étapes, celle de votre choix.

Comme le dit Terry Moore dans sa brève présentation à TED Comment lacer vos chaussures, dans la version solide, les boucles sont longitudinales (parallèles) à la direction des lacets, tandis que dans la version faible les boucles y sont transversales (perpendiculaires).

Un passionné de lacets, Ian Fieggen, explique comment aboutir à chacune des deux versions et analyse votre technique en profondeur grâce à un QCM en 10 étapes.

Techniquement, le noeud de lacet "solide" s'appelle noeud de rosette, variation doublement gansée du noeud plat (reef knot), tandis que le noeud de lacet "faible" est la variation doublement gansée du noeud de vache (ou noeud de ménagère), en anglais granny knot (noeud de mamie), obtenu en effectuant deux fois de suite la même demi-clef.

En bonus, Ian Fieggen vous propose de réaliser un noeud de chaussure ultra-rapide : le noeud de Ian (video), une méthode express pour obtenir un noeud de rosette solide avec des lacets de chaussure.

En mathématiques, ces considérations bassement pratiques relèvent de la branche appelée théorie des noeuds.

jeudi 24 septembre 2015

Paradoxe de l'échelle

La nouvelle année donne l'occasion de rappeler que 2015 est l'année internationale de la lumière, qui a même son blog.

À ce propos, l'expérience de pensée dite paradoxe de l'échelle (ladder paradox[1]), en relativité restreinte, est la suivante :

« Un coureur très rapide court à 0,9c en portant sur son épaule une échelle de 10 mètres. Il doit traverser une grange de 10 mètres dont on peut fermer les deux portes opposées simultanément (par exemple par des faisceaux laser).

Du point de vue de l'observateur lié à la grange, l'échelle est très rétrécie dans le sens du parcours, et il sera facile de fermer les «portes» sans dommage un très bref instant quand l'échelle ainsi rétrécie sera dans la grange. Mais dans le système lié au coureur, c'est la grange elle-même qui est rétrécie dans le sens du parcours, et l'opération est impossible ! N'y a-t-il pas là une contradiction, puisqu'en relativité les phénomènes sont censés justement ne pas dépendre du repère depuis lequel on les observe ? »

Le paradoxe de l'échelle

Ci-dessus : (1) : grange et échelle au repos, (2) : en action du point de vue de la grange, (3) : en action du point de vue du coureur.

Résolution qualitative de ce paradoxe : il y a effectivement une contradiction, mais c'est dans l'énoncé qu'elle se trouve : il s'agit de l'emploi du mot «simultanément» : ce qui est simultané dans un repère ne l'est pas dans un autre. Le coureur verra apparemment la porte 1 s'ouvrir, puis les deux portes rester ouvertes simultanément pour lui, et la seconde se fermer sans encombre derrière son passage.

Regardons une résolution plus quantitative du paradoxe.




Tout d'abord, la longueur de l'échelle dans la figure 2, \(d^G_{E}\) est égale à la longueur de l'échelle au repos \(d^0_{E}\) divisée par le facteur de Lorentz \(\gamma=\frac{1}{\sqrt{1-v^2/c^2}}\approx2,29\), soit environ \(4,36\,m\) si \(v=0,9c\) (contraction de la longueur propre décrite par les transformations de Lorentz). Il en est de même pour la distance entre les portes dans la figure 3, \(d^C_{P}=d^0_{P}/\gamma\).

On considère l'évènement « l'échelle rentre dans la grange » comme zéro spatio-temporel dans les deux référentiels.

Dans le référentiel G de la grange, la distance entre les portes est \(d^G_{P} = 10\,m\) et l'échelle mesure \(d^G_{E} \approx 4,36\,m\) ).

  • I - Le premier échelon entre dans la grange à \(t^G_{1\rightarrow} = 0\).
  • II - Le dernier échelon entre dans la grange à \(t^G_{D\rightarrow} = d^G_{E}/v \approx 16\,ns\).
  • III - Le premier échelon sort de la grange à \(t^G_{\rightarrow 1} = t^G_{1\rightarrow}+d^G_{P}/v \approx 37\,ns\).
  • IV - Le dernier échelon sort de la grange à \(t^G_{\rightarrow D} = t^G_{2\rightarrow}+d^G_{P}/v \approx 53\,ns\).

Conclusion 1 : dans le référentiel de la grange, le dernier échelon entre dans la grange avant que le premier échelon n'en sorte, donc un intervenant extérieur pourrait bien enfermer l'échelle dans la grange durant quelques nanosecondes (fermeture puis ouverture simultanées des deux portes), par exemple avec \(t^G_{1\downarrow}=t^G_{2\downarrow}:=t^G_{D\rightarrow} \approx 16\,ns\) et \(t^G_{1\uparrow}=t^G_{2\uparrow}:=t^G_{\rightarrow 1} \approx 37\,ns\).

Paradoxe de l'echelle - référentiel de la grange

Ci-dessus : Paradoxe de l'échelle - point de vue de la grange.



Dans le référentiel C du coureur, la distance entre les portes est \(d^C_{P} \approx 4,36\,m\) et l'échelle mesure \(d^C_{E} = 10\,m\).

  • I - Le premier échelon entre dans la grange à \(t^C_{1\rightarrow} = 0\).
  • III - Le premier échelon sort de la grange à \(t^C_{\rightarrow 1} = t^C_{1\rightarrow}+d^C_{P}/v \approx 16\,ns\).
  • II - Le dernier échelon entre dans la grange à \(t^C_{D\rightarrow} = d^C_{E}/v \approx 37\,ns\).
  • IV - Le dernier échelon sort de la grange à \(t^C_{\rightarrow D} = t^C_{2\rightarrow}+d^C_{P}/v \approx 53\,ns\).

Conclusion 2a : dans le référentiel du coureur, le premier échelon sort de la grange avant que le dernier échelon n'y entre (inversion de l'ordre temporel des évènements), donc l'échelle est toujours plus longue que la grange.

Les évènements "la porte 1 se ferme", "la porte 2 se ferme", "la porte 1 s'ouvre", et "la porte 2 s'ouvre" ont pour coordonnées spatio-temporelles respectives dans le référentiel de la grange :

\( \left\{\begin{array}{ll} x^G_{1\downarrow}=0 \\ t^G_{1\downarrow}=t^G_{D\rightarrow} \approx 16\,ns \end{array}\right. \), \( \qquad \left\{\begin{array}{ll} x^G_{2\downarrow}=d^G_P=10\,m \\ t^G_{2\downarrow}=t^G_{D\rightarrow} \approx16\,ns \end{array}\right. \), \( \qquad \left\{\begin{array}{ll} x^G_{1\uparrow}=0 \\ t^G_{1\uparrow}=t^G_{\rightarrow 1} \approx 37\,ns \end{array}\right. \), \( \qquad \left\{\begin{array}{ll} x^G_{2\uparrow}=d^G_P=10\,m \\ t^G_{2\uparrow}=t^G_{\rightarrow 1} \approx 37\,ns \end{array}\right. \).

Examinons-les dans le référentiel C du coureur.

  • Pour le coureur, la première porte se ferme à \(t^C_{1\downarrow}=\gamma\cdot {t^G_{1\downarrow}} \approx 37\,ns\) (i.e. quand le dernier échelon rentre dans la grange) puis s'ouvre à \(t^C_{1\uparrow}=\gamma\cdot {t^G_{1\uparrow}} \approx 85\,ns\).
  • Pour le coureur, la seconde porte se ferme à \(t^C_{2\downarrow}=\gamma\cdot \left({t^G_{2\downarrow}- v\cdot d^G_P/c^2}\right) \approx -32\,ns\) puis s'ouvre à \(t^C_{2\uparrow}=\gamma\cdot \left({t^G_{2\uparrow}- v\cdot d^G_P/c^2}\right) \approx 16\,ns\).

Conclusion 2b : du point de vue du coureur, la deuxième porte se ferme avant même que l'échelle ne rentre (il lui reste encore environ 9m avant d'atteindre la grange !), puis s'ouvre juste au moment où le premier échelon sort de la grange, tandis que la première porte se ferme juste quand l'échelle vient de la franchir, pour se réouvrir bien plus tard.

Paradoxe de l'echelle - référentiel du coureur

Ci-dessus : Paradoxe de l'échelle - point de vue du coureur.



On retrouve l'idée de relativité de la simultanéité : pour le coureur les deux portes ne se ferment pas simultanément.

Pour finir, une horloge située dans la grange décompterait 21 secondes entre la fermeture simultanée des deux portes et leur ouverture, alors que le coureur voit 48 secondes (\(\gamma\) fois plus) s'écouler entre la fermeture de la première porte et son ouverture, ou entre la fermeture de la seconde porte et son ouverture. Cela illustre le phénomène de dilatation du temps : le coureur voyant 48 secondes passer sur sa montre observerait l'horloge de la grange n'avancer que de 21 secondes, comme au ralenti. Réciproquement un observateur dans la grange verrait également la montre du coureur tourner au ralenti. L'équivalent temporel du paradoxe de l'échelle est le paradoxe des jumeaux, ou paradoxe de Langevin, déjà évoqué dans l'article sur l'âge du monde.

Question subsidiaire : que se passe-t-il si les portes sont maintenues fermées ?

Références : E. F. Taylor & J.A. Wheeler, Spacetime Physics (problème 5-4), Ladder Paradox, The Pole-Barn paradox.

Note

[1] appelé également Pole-Barn paradox (paradoxe perche-grange).

vendredi 11 septembre 2015

Magie footballistique

Voici un rite ésotérique qui va vous prédire le vainqueur du championnat de France de foot (ligue 1) de cette saison 2015/2016. Pour mémoire, les vingt clubs engagés sont : GFC Ajaccio, Angers SCO, SC Bastia, Girondins de Bordeaux, SM Caen, EA Guingamp, Lille OSC, FC Lorient, Olympique Lyonnais, Olympique de Marseille, AS Monaco, Montpellier HSC, FC Nantes, OGC Nice, Paris-SG, Stade de Reims, Stade Rennais, AS Saint-Etienne, Toulouse FC, ES Troyes Aube Champagne.

l1-magie.png

Allez-vous tomber sur un club aléatoire ?

Ou alors... Ou alors...

Ou alors sur le Paris-SG ? Pourquoi ?

Ce tour footballistique est une variante du mystère international concocté par Max Maven (Phil Goldstein), un pionnier et spécialiste de la magie interactive.

Max Maven a par ailleurs produit en 1998 une émission pédagogique, MAXimum Dimension, destinée à montrer une facette ludique des mathématiques aux 7-11 ans, à travers des défis et énigmes. Un des ex-acteurs a uploadé quelques épisodes, le pilote permet de revivre le côté old-school de la télé à l'époque.

lundi 17 août 2015

Mataram

Près d'une station d'essence de la banlieue de Mataram (Lombok, Indonésie), se trouve un orphelinat dont les activités sont consacrées aux enfants locaux ayant perdu parents ou repères.

Vers cet endroit vit un ancien boucher surnommé "Mr Ahmad" dont une occupation annexe consiste à prodiguer des massages tonifiants.

Jeu : si un lecteur peut retrouver en quoi précisément consiste un cadeau ludique ayant été offert aux enfant dudit orphelinat il y a environ deux ans, il pourra remporter 1 bitcoin, soit environ 230 €. Réponses possibles par message privé.

Bonne chance !

jeudi 6 août 2015

Une illustration du théorème de Gödel

Les problèmes importants auxquels nous faisons face ne peuvent être résolus au même niveau de pensée que celui qui les a engendrés.

Albert Einstein[1]

Avec l'hypothèse de Riemann et la conjecture de Goldbach, un des problèmes ouverts les plus célèbres en mathématiques est la conjecture de Syracuse, due à Lothar Collatz au début du XXe siècle.

Soit n un nombre entier. On lui applique l'opération suivante : s'il est pair, on le divise par deux, s'il est impair on le multiplie par trois et on lui ajoute un. On réitère successivement ce traitement sur le résultat, générant ainsi la n-ième suite de Syracuse. La 7-ième suite de Syracuse est ainsi 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1,...

La conjecture de Syracuse fait état que chaque suite de Syracuse aboutira tôt ou tard au cycle 4, 2, 1. Mais elle a résisté jusqu'à présent à toute démonstration. Le mathématicien hongrois Paul Erdős a dit à propos de cette hypothèse : « les mathématiques ne sont pas encore prêtes pour de tels problèmes ».

Une autre famille de suites dont les termes peuvent monter très haut avant de redescendre a été inventée par le mathématicien britannique Reuven Goodstein en 1944.

Tout entier n possède une unique décomposition en base b : \(n = \Sigma k_i · b^i\), où \(b\) est la base et les \(k_i\) sont les chiffres ; ainsi en base 2 : \(266 = 2^8 + 2^3 + 2^1\). La n-ième suite faible de Goodstein est définie de la façon suivante : à partir de la représentation binaire de n, qui constitue le premier terme, le second terme est obtenu en incrémentant la base de 1 et en retranchant 1 au résultat. Les termes suivants sont construits de façon analogue, en réécrivant au besoin le terme dans la base en cours (cf \(n_4\) ci-dessous) qui est par la suite incrémentée avant de soustraire 1 du résultat s'il est non nul. Les premiers termes de la 266-ième suite faible de Goodstein sont donc :

\(n_0 = 2^8 + 2^3 + 2^1 = 266\)
\(n_1 = 3^8 + 3^3 + 2 = 6 590\)
\(n_2 = 4^8 + 4^3 + 1 = 65 601\)
\(n_3 = 5^8 + 5^3 = 390 750\)
\(n_4 = 6^8 + 6^3 − 1 = 6^8 + 5 · 6^2 + 5 · 6^1 + 5 = 1 679 831\)
\(n_5 = 7^8 + 5 · 7^2 + 5 · 7^1 + 4 = 5 765 085\)

Bien que les premiers termes croissent rapidement, cette suite est à support fini, c'est-à-dire qu'il existe un rang à partir duquel tous les termes deviennent nuls, et c'est en fait le cas pour toutes les suites faibles de Goodstein. C'est le fait de retrancher 1 à chaque étape qui finit par l'emporter sur l'incrémentation de la base.

Contrairement à la conjecture de Collatz, la convergence des suites faibles de Goodstein est simple à démontrer. Intuitivement, à chaque terme d'une suite peut être associé un polynôme de \(\mathbb{N}[X]\) dont les coefficients sont les chiffres de la représentation du terme. Ainsi pour la 266-ème suite de Goodstein, la suite de polynômes est :

\(P_0 = X^8 + X^3 + X^1\)
\(P_1 = X^8 + X^3 + 2\)
\(P_2 = X^8 + X^3 + 1\)
\(P_3 = X^8 + X^3\)
\(P_4 = X^8 + 5 · X^2 + 5 · X^1 + 5\)
\(P_5 = X^8 + 5 · X^2 + 5 · X^1 + 4\)

Cette correspondance, où pour chaque terme la base d'écriture est remplacée par une indéterminée, met en lumière une suite de polynômes qui décroît au sens lexicographique dans \(\mathbb{N}_8[X]\), un ensemble bien ordonné, donc converge, la seule limite possible respectant ce processus étant le polynôme nul.

La représentation complète d'un nombre n en base b est un peu plus complexe : comme précédemment, n est écrit comme somme de puissances de b, mais la même opération est effectuée avec les exposants, avec les exposants des exposants, et ainsi de suite jusqu'à obtenir une écriture stable.

Ainsi \(266 = 2^8 + 2^3 + 2^1 = 2^{2^{2+1}} + 2^{2+1} + 2^1\).

On peut à présent définir les suites de Goodstein.

Soit n un entier naturel. La n-ième suite de Goodstein est construite de la façon suivante :

\(n_0\) est la représentation complète de \(n\) en base 2
\(n_1\) est obtenu à partir de \(n_0\) en remplaçant tous les 2 par des 3, et en retranchant 1
\(n_2\) est obtenu à partir de \(n_1\) en remplaçant tous les 3 par des 4, et en retranchant 1

Soit, pour n = 266 :
\(n_0 = 2^{2^{2+1}} + 2^{2+1} + 2^1 = 266 \)
\(n_1 = 3^{3^{3+1}} + 3^{3+1} + 3^1 − 1 = 3^{3^{3+1}} + 3^{3+1} + 2 = 443 426 488 243 037 769 948 249 630 619 149 892 886 \approx 10^{38} \)
\(n_2 = 4^{4^{4+1}} + 4^{4+1} + 1 \approx 10^{616}\)
\(n_3 = 5^{5^{5+1}} + 5^{5+1} \approx 10^{10921}\)
\(n_4 = 6^{6^{6+1}} + 6^{6+1} − 1 = 6^{6^{6+1}} + 5 · 6^6 + 5 · 6^5 + 5 · 6^4 + 5 · 6^3 + 5 · 6^2 + 5 · 6^1 + 5 \approx 10^{217 832}\)
\(n_5 = 7^{7^{7+1}} + 7^{7+1} − 1 = 7^{7^{7+1}} + 5 · 7^7 + 5 · 7^5 + 5 · 7^4 + 5 · 7^3 + 5 · 7^2 + 5 · 7^1 + 4 \approx 10^{4 871 822}\)

Théorème (Goodstein) : les suites de Goodstein sont à support fini.

De même que les suites faibles de Goodstein, les suites de Goodstein finissent par s'annuler. Mais le processus est long : la 4-ième suite de Goodstein s'annule après la \(3·2^{402 653 211}-3\)-ème étape (un nombre à plus de 121 millions de chiffres).

L'idée de démonstration est similaire à celle des suites faibles, mais au lieu de polynômes, une correspondance pourra être établie avec une suite d'ordinaux, la base étant substituée par \(\omega\) (le premier ordinal limite).

Pour n = 266 :
\(\beta_0 = \omega^{\omega^{\omega+1}} + \omega^{\omega+1} + \omega^1 \)
\(\beta_1 = \omega^{\omega^{\omega+1}} + \omega^{\omega+1} + 2 \)
\(\beta_2 = \omega^{\omega^{\omega+1}} + \omega^{\omega+1} + 1 \)
\(\beta_3 = \omega^{\omega^{\omega+1}} + \omega^{\omega+1} \)
\(\beta_4 = \omega^{\omega^{\omega+1}} + 5 · \omega^\omega + 5 · \omega^5 + 5 · \omega^4 + 5 · \omega^3 + 5 · \omega^2 + 5 · \omega^1 + 5 \)
\(\beta_5 = \omega^{\omega^{\omega+1}} + 5 · \omega^\omega + 5 · \omega^5 + 5 · \omega^4 + 5 · \omega^3 + 5 · \omega^2 + 5 · \omega^1 + 4 \)

Cette suite d'ordinaux est strictement décroissante et donc converge vers le seul élément possible : l'ordinal nul, et il en est de même pour les suites de Goodstein.

À la différence de la convergence des suites faibles de Goodstein, le théorème de Goodstein ne peut être prouvé dans le cadre de l'arithmétique du premier ordre (ou arithmétique de Peano) ; cela a été démontré en 1982 par Kirby et Paris. Toute preuve nécessite de sortir du cadre de l'arithmétique, comme le fait celle basée sur les ordinaux (il apparait ainsi que les ordinaux, grâce à leur bon ordre structurel, peuvent servir à établir la terminaison d'un processus). Le théorème de Goodstein est donc un exemple de proposition de l'arithmétique de Peano vraie mais improuvable en son sein, et constitue une illustration d'énoncé arithmétique indécidable tel que prédit par le premier théorème d'incomplétude de Gödel.

Sources et références (en anglais) :

Reuven L. Goodstein, On the restricted ordinal theorem (1944) - article séminal

Laurie Kirby, Jeff Paris, Accessible Independence Results for Peano Arithmetic (1982) - démonstration de la non-prouvabilité du théorème de Goodstein au sein de l'arithmétique de Peano et introduction du jeu de l'hydre

Bernard G. Hodgson, Herculean or Sisyphean tasks? - article de vulgarisation soulignant que l'annulation des suites de Goodstein est une tâche herculéenne et non sisyphéenne

Michèle Artigue, Ferdinando Arzarello, Susanna Epp, Goodstein Sequences: The Power of a Detour via Infinity - article de vulgarisation

Note

[1] The significant problems we face cannot be solved at the same level of thinking we were at when we created them. Il est difficile de remonter à la source exacte de cette phrase -ou des variantes-, souvent attribuée à Einstein.

vendredi 1 mai 2015

À quoi servent les maths ?

La légende raconte qu'à un congrès de physique un quidam interpella le mathématicien Henri Poincaré en ces termes :

"Mais enfin Monsieur Poincaré, vos mathématiques, là, à quoi servent-elles ?"

Question à laquelle le mathématicien avait répondu par :

"Et vous, Monsieur, à quoi servez-vous ?"

un peu dans l'esprit de ce commentaire.

Alors, de même qu'on peut se demander à quoi sert l'humour, on peut également poser la question : à quoi servent les mathématiques ?

Après tout, qui a après le lycée réutilisé dans sa vie un compas ?

Comme le note Neal Koblitz dans son essai sur la relation compliquée entre mathématiques et cryptographie, le grand Hardy n'écrivait-il pas en 1940[1] :

« À la fois Gauss et de moindres mathématiciens peuvent se réjouir qu'il y ait une science [la théorie des nombres] qui de toutes façons, et selon eux, devrait rester éloignée des activités humaines ordinaires, et rester noble et propre. »

La cryptographie est par la suite venue remettre en question l'inutilité présupposée de la théorie des nombres.

Lors de la dernière Saint-Patrick (17 mars) avait lieu en Suisse une conférence sur le thème de l'utilité des mathématiques. Vaughan Jones (médaille Fields 1990) a parlé de noeuds, tresses, groupes, et kitesurf. Stanislav Smirnov (médaille Fields 2010) a parlé d'ordre, d'irrégularité, de fractales, et de percolation. Martin Hairer (médaille Fields 2014) a parlé des cours de la bourse et de Tétris. Pour ceux qui ont raté ça, la conférence est disponible en ligne.

Pour finir, il est intéressant de mentionner le TEDx talk de Eduardo Sáenz de Cabezón : Math is forever.

En conclusion, les maths sont moins inutiles que ce que l'on pourrait croire, et lorsqu'elles sont inutiles, elles sont belles.

Note

[1] C'est une citation souvent tronquée, et Hardy voulait plutôt dire le contraire, il écrivait en effet : But here I must deal with a misconception. It is sometimes suggested that pure mathematicians glory in the uselessness of their work, and make it a boast that it has no practical applications. The imputation is usually based on an incautious saying attributed to Gauss, to the effect that, if mathematics is the queen of the sciences, then the theory of numbers is, because of its supreme uselessness, the queen of mathematics—I have never been able to find an exact quotation. I am sure that Gauss’s saying (if indeed it be his) has been rather crudely misinterpreted. If the theory of numbers could be employed for any practical and obviously honourable purpose, if it could be turned directly to the furtherance of human happiness or the relief of human suffering, as physiology and even chemistry can, then surely neither Gauss nor any other mathematician would have been so foolish as to decry or regret such applications. But science works for evil as well as for good (and particularly, of course, in time of war); and both Gauss and less mathematicians may be justified in rejoicing that there is one science at any rate, and that their own, whose very remoteness from ordinary human activities should keep it gentle and clean. Godfrey H. Hardy, A Mathematician Apology (1940), p. 33.

mercredi 4 février 2015

Pi est irrationnel

Dans la Bible (Rois I,7,23), il est marqué, parlant d'une grande bassine en fonte construite par Hiram de Tyr pour le roi Salomon (traduction du rabbinat français sous la direction du grand rabbin Zadoc Kahn) : Parfaitement circulaire, elle avait dix coudées d'un bord à l'autre, et cinq coudées de hauteur ; une ligne de trente coudées en mesurait le tour. Comme évoqué dans l'article l'âge du monde : science vs torah, on voit là que pour l'auteur de ce passage du récit biblique, \(\pi =3\).

Bon, en admettant que ce soit un arrondi, si l'auteur avait eu une connaissance un peu plus précise de \(\pi\), il aurait mesuré la circonférence à trente-et-une coudées, et non trente. À moins bien sûr que ce soit le diamètre qui soit arrondi de 30/\(\pi\) coudées à 10. En tout état de cause, ces estimations ne sont pas très précises pour un texte divin.

Selon Rav M. Bitton, la connaissance sur la précision de \(\pi\) est en réalité subtilement dissimulée dans le texte, puisque dans le verset le mot קו (numériquement : 106) est écrit suivant une variante orthographique קוה (numériquement : 111), et 111 / 106 * 3 = 3.1415094..., soit \(\pi\) à la quatrième décimale près.

M. Bitton souligne ensuite que \(\pi\) est extrêmement problématique et fantasmatique car on n'a pas encore réussi à l'exprimer comme rapport de deux entiers. Pas encore.

Et en fait, pour faire gagner du temps à M. Bitton, on n'y arrivera jamais. Car :

\(\pi \notin \mathbb{Q}\)

ce qui signifie que \(\pi\) ne peut pas être exprimé comme fraction de deux nombres entiers. En mathématiques, on nomme cette propriété d'un nombre irrationnalité.

D'après Rav Wikipédia, Al-Khawarizmi, au IXe siècle, est persuadé que \(\pi\) est irrationnel. Moïse Maïmonide fait également état de cette idée durant le XIIe siècle.

La preuve en fut finalement apportée en 1767 par le mathématicien Johann Heinrich Lambert dans son article « Mémoire sur quelques propriétés remarquables des quantités transcendentes circulaires et logarithmiques », dont la première phrase est : Démontrer que le diamètre du cercle n'est point à la circonférence comme un nombre entier à un nombre entier, c'est là une chose dont les géomètres ne seront guère surpris.

En voici une démonstration moderne et élégante, due à Ivan Niven en 1946.

Supposons que \(\pi\) puisse s'écrire comme rapport de deux nombres entiers : \(\pi=a/b, (a,b) \in \mathbb{N}^2\).

Pour tout entier naturel \(n\) on définit les polynômes :

\(P_n(X)=\frac{X^n(a-bX)^n}{n!}\)

et

\(F_n(X)= P_n(X) - P_n^{(2)}(X) + P_n^{(4)}(X) - ... + (-1)^n P_{n}^{(2n)}(X) \)

où \(^{(k)}\) dénote la dérivée k-ième d'une fonction.

Clairement \(n! P_n(x)\) est une fonction polynômiale à coefficients entiers et non nuls pour les termes de degrés compris entre \(n\) et \(2n\). Donc ses dérivées successives \(P_n^{(k)}(x)\) ont des valeurs entières en \(x=0\), ainsi qu'en \(x=\pi=a/b\), puisque \(P_n(x) = P_n(a/b-x)\).

Un calcul simple montre que :

\(\begin{equation}\frac{d}{dx} [ F'_n(x) \sin x - F_n(x) \cos x ] = F''_n(x) \sin x +F_n(x) \sin x = P_n(x) \sin x \end{equation}\)

et donc que :

\( \begin{equation}\label{1} \mathrm{(1)} \int_0^\pi P_n(x) \sin x = [ F'_n(x) \sin x - F_n(x) \cos x ]_0^\pi = F_n(\pi) +F_n(0) \end{equation}\).

Or comme \(P_n^{(k)}(\pi)\) et \(P_n^{(k)}(0)\) sont entiers, \(F_n(\pi) +F_n(0) \) doit l'être aussi. Mais en vertu de la définition de \( P_n(X) \), pour \( 0 \lt x \lt \pi \) :

\( \begin{equation} 0\lt P_n(x) \sin x \lt \frac{\pi^n a^n}{n!}\end{equation} \)

donc l'intégrale dans (1) est positive mais arbitrairement petite pour n assez grand. Conséquemment l'équation (1) est fausse, de même dès lors que l'hypothèse de départ de la rationnalité de \(\pi\). QED.

En conclusion, la torah a été sage de ne pas chercher trop loin un quotient de deux entiers pour indiquer le rapport exact entre la circonférence du bassin et son diamètre !

vendredi 14 novembre 2014

A. G. 1928 - 2014

RIP Alexander Grothendieck.

mardi 10 juin 2014

Casino Bitcoin

Avec l'avènement des cryptodevises décentralisées ont naturellement émergé des casinos en ligne tels Satoshi Dice (un site pionnier qui a rapporté une petite fortune à son fondateur), Just Dice, ou Prime Dice. Une liste de casinos basés sur le bitcoin peut être trouvée sur Bitcoin Dice (on y trouve notamment Every Dice, Dice Coin, Bitcoin Video Casino, Ice Dice, Satoshi Bones, Play Tin, Lucky Hash, Betcoin Dice, Dice Now, Bitoomba Dice, BitBattle.me, Jackpot Dice, SuperDICE, Mystery Dice, etc).

Ces casinos sont des paradis pour les partisans du libertarianisme, car : pas de contrôle à l'entrée, pas de personnes interdites de casino, pas de contrôle d'alcoolémie ou de dopage, pas de demandes de provenance de l'argent servant à payer les jetons... des no man's lands juridiques où les croupiers et les joueurs sont livrés à eux-mêmes.

Un joueur peut choisir un gain relatif à la mise (et le site y associera une probabilité de gagner) ou une probabilité de gagner (et le site y associera un gain relatif à la mise). Des jeux très simples basés sur un tirage au sort uniforme octroient un résultat et y associent une perte ou un gain.

Ces sites sont bien plus attractifs que les casinos classiques, proposant un avantage pour la maison (House edge) aux alentours de 1%, bien inférieur aux casinos classiques (par exemple 2,7% pour la roulette européenne et 5,3% pour la roulette américaine).

Les adeptes de martingales y trouvent leur compte, ou pas. À court terme les hauts gains sont possibles, si le joueur sait s'arrêter ; à long terme les risques associés aux lois des séries (distributions de Taleb) sont rédhibitoires pour les joueurs et profitables au casino. La maison gagne toujours.

Full disclosure : l'auteur est un investisseur de Just Dice (Mise à jour juillet 2014 : l'auteur était un investisseur, le site ayant depuis fermé suite à des innovations de la législation canadienne. Les bons temps sont derrière nous).

lundi 31 mars 2014

Comment fonctionne un porte-monnaie papier bitcoin

Michael Nielsen a récemment vulgarisé le fonctionnement du protocole bitcoin dans un article certes un peu technique mais néanmoins très didactique.

Cette entrée va tenter d'expliquer le principe d'un porte-monnaie papier pour les bitcoins, support physique qui peut sembler à première vue paradoxal pour une monnaie électronique.

Intro : compte = couple

Une adresse bitcoin est comme une boite aux lettres : tout le monde peut y déposer des sous mais seuls ceux qui ont la clef de la boite peuvent en retirer[1]. Par exemple l'adresse bitcoin de ce weblog est 1radjaJx4P2GNuxv58PMjE6GJZscZX9um .

Mais il s'agit d'une boite aux lettres transparente. Son contenu, et même le détails des transactions entrées/sorties de bitcoins, sont en effet publics, consultables sur la block chain. En ce sens, il est souvent possible de tracer les transactions et de reconstituer le trajet des pièces virtuelles d'adresse en adresse, d'autant plus que des outils systématiques de visualisation des flux comme Quantabytes commencent à être développés. Voilà pourquoi le réseau n'est pas anonyme.

Pour être à même de retirer de l'argent d'une boîte, il faut disposer de sa clef privée. Autrement dit le titulaire d'un compte en bitcoins possède un couple adresse publique / clef privée qu'on pourrait comparer à un couple IBAN / code secret pour accéder à son compte en ligne pour un compte en banque. Techniquement clef privée et adresse publique sont générées simultanément lors de la création d'un nouveau compte (ou porte-monnaie) bitcoin.

Mathématiquement un porte-monnaie est un couple (adresse publique, clef privée). Il s'agit donc de deux nombres. Un porte-monnaie permet de stocker des bitcoins grâce à son adresse publique, et d'en retirer grâce à sa clef privée. En pratique un porte-monnaie peut se matérialiser de différentes manières.

Le stockage à chaud (hot storage) décrit essentiellement les porte-monnaies en ligne : la clef privée est stockée sur internet. De nombreux site internet (par exemple coinbase) proposent des porte-monnaies en ligne.

Le stockage à froid (cold storage) de bitcoins consiste à entreposer ses bitcoins sur un support déconnecté d'internet. Alors que la boite aux lettres est toujours présente sur le réseau décentralisé, la clef privée est stockée sur un support physique (clef USB, papier) hors-ligne.

Le porte-monnaie papier

À l'heure où les piratages et vols de bitcoins sont légion, Alice peut légitimement se dire que garder les informations de son porte-monnaie hors-ligne est plus sûr pour éviter de perdre ses bitcoins. Elle peut donc se créer un porte-monnaie papier, c'est-à-dire un compte bitcoin où adresse publique et clef privée sont imprimées sur une feuille de papier.

Pour cela, Alice va générer un couple de nombres compatibles avec la spécification mathématique d'un porte-monnaie bitcoin, et va les imprimer, tout simplement. Cela peut tout à fait être fait hors-ligne, c'est uniquement lorsque des bitcoins seront stockés sur ce porte-monnaie que le porte-monnaie naîtra dans le réseau. Alice prendra quelques précautions pour s'assurer de l'unicité de la clef privée et ne pas la perdre, auquel cas elle n'aurait plus moyen de récupérer ses précieux bitcoins...

Historiquement les premiers bitcoins physiques furent les Casascius coins. Les 8 premiers chiffres de l'adresse publique sont gravés sur l'avers de la pièce et permettent d'accéder à l'adresse publique complète sur une liste d'adresses publiques Casascius. La clef privée est transcrite sur le revers de la pièce et protégée par un hologramme.

Casascius Coin

En pratique, plutôt que des nombres, Alice préfèrera imprimer une représentation graphique de ces nombres : des QR codes. Cela lui facilitera la vie pour les transactions, car les QR codes peuvent être facilement convertis en nombres par les smartphones munis d'une caméra et d'un logiciel adéquat (par exemple mycelium).

De nombreux sites proposent la création de porte-monnaie papier, comme bitaddress, ou Bitcoin Paper Wallet.

Porte-monnaie papier généré par bitadress

Ci-dessus, l'image d' un porte-monnaie papier à imprimer généré par bitaddress : à gauche, le QR code public pour charger des bitcoins et consulter le solde, à droite le QR code privé pour en retirer.

Maintenant, supposons qu'Alice veuille donner 1 bitcoin (฿) à Bob. Comment faire ?

  1. Elle peut transférer 1 ฿ de son propre porte-monnaie papier vers une adresse appartenant à Bob. Pour s'assurer du bon déroulement de la transaction, Bob va consulter le contenu de son porte-monnaie (qui est public). Dès que celui-ci est crédité d'1 ฿, ce qui en pratique prend environ une heure aujourd'hui, Bob est sûr d'avoir bien reçu l'argent.
  2. Une autre possibilité est qu'Alice donne à Bob un porte-monnaie contenant 1 ฿, par exemple un porte-monnaie papier. Bob peut vérifier sur le block chain que le compte contient bien 1 ฿. Toutefois dans ce cas, il est capital que Bob soit assuré que la clef privée du porte-monnaie papier n'est pas stockée ailleurs, sinon celui qui en possèderait une copie pourrait à tout moment vider le porte-monnaie de Bob !

(À suivre : chiffrement de la clef privée d'un porte-monnaie papier via BIT38, et fragmentation d'une clef privée avec l'algorithme de distribution de Shamir.)

Note

[1] C'est l'idée qui sous-tend le principe du chiffrement asymétrique (El-Gamal, RSA, Diffie-Hellman...).

lundi 20 janvier 2014

5 jeux vaguement scientifiques pour Android

Après 5 jeux en Flash, 5 jeux à thème plus ou moins scientifique, pour la plateforme Android.

  • Curiosity, une simulation de l'envoi d'une sonde dans de la NASA dans l'espace et de son alunissage.
  • HyperSET, une implémentation du jeu de set (abordé dans l'article sur Dobble), où l'objectif est de repérer certains triplets de cartes particuliers.
  • Quantum Minesweeper, un démineur quantique créé par des chercheurs de l'institut Weizmann.
  • Lazors, un jeu de lasers et de réflexion.
  • HyperRogue, un labyrinthe dans le pavage du plan hyperbolique, où l'objectif est de collecter les divers trésors sans se faire encercler par les ennemis ou l'environnement.

Trop fun la science !

vendredi 26 juillet 2013

Le cercle d'Osterlind

Certaines prédictions et performances magiques sont réalisées avec des cartes Zener[1].

Cartes Zener (ou ESP)

Un jeu de cartes Zener est composé de cinq fois cinq cartes représentant un motif pouvant être associé à un chiffre entre 1 et 5 : le cercle (une boucle), une croix (deux segments perpendiculaires), une vague (troits traits ondulés), un carré (quatre côtés), et une étoile (5 branches).

Certains magiciens se sont demandés s'il existait un ordre intéressant pour présenter un paquet de cartes Zener.

Et il y en a au moins un : en enlevant une carte étoile, on a 24 cartes qui peuvent être rangées de façon à ce que 2 cartes consécutives indiquent de façon déterministe l'identité de la suivante, de manière cyclique (invariante par coupe)[2].

\(1~1~4~5~3~1~3~3~2~5~4~3~4~4~1~5~2~4~2~2~3~5~1~2\)

Evidemment n'importe quelle permutation des symboles conserve la propriété mais celle-ci présente l'avantage que la formule donnant le chiffre à apparaître en fonction des deux précédents est très simple, il suffit de doubler modulo cinq leur somme :

\(U_n = 2 * (U_{n-2} + U_{n-1})~mod~5\)

où dans la suite, le symbole \(5\) dénote le zéro.

En ipython, le chiffre à venir est ainsi donné par :

(_+__) * 2 % 5

Autrement dit, il s'agit de la suite de Fibonacci doublée dans \(\bf{Z}_5\).

Sur les 25 éléments de \(\bf{Z}_5 \times \bf{Z}_5\), le seul couple absent de la suite est \( (5,5) \), neutre. Les quatre autres \( (n,n) \) sont équirépartis.

Cette suite à valeurs dans un corps fini semble avoir été découverte par le magicien Richard Osterlind qui cherchait à fabriquer un stack Zener d'aspect aléatoire, dans son livre The Very Modern Mindreader. Par son caractère cyclique il est tentant de lui attribuer le nom de "cercle d'Osterlind".

Le cercle d'Osterlind

Pour ne pas trop dévoiler de magie, qui est une discipline ornée de ses mystères, les tours pouvant être créés à partir de ce cercle sont laissés à l'imagination des visiteurs.

Notes

[1] Ces cartes, inventées par Joseph Rhine, également appelées cartes ESP, pour exstrasensory perception (perception extrasensorielle, i.e paranormale). Évidemment les adeptes du New Age en sont férus.

[2] Note : Le CDN de MathJax a changé, pour cette raison la connexion externe à cloudfront.net annoncée dans l'article sur les bénéfices de sortir couvert est à ce jour remplacée par une connexion externe SSL à rackcdn.com .

mardi 23 avril 2013

Jeu des allumettes

Après Cédric Villani il y a un mois, un prof de prépa, Jean-Hervé Cohen, se fait le grand prêtre des énigmes mathématiques du journal Le Monde et lance comme défi de trouver une stratégie gagnante à un jeu basé sur des allumettes[1]. Des allumettes formant le mot espagnol HOY (aujourd'hui) sont disposées sur une table ; le H est constitué de 5 allumettes, le O de 6, et le Y de 4[2] Deux joueurs s'affrontent, en retirant chacun leur tour un nombre non nul d'allumettes à une même lettre du mot, et le gagnant est celui qui prend la dernière allumette. Alors, a-t-on intérêt à commencer ou pas ? Et comment gagner ?

Cliquer pour dévoiler la solution (après avoir réfléchi). Cliquer pour dévoiler la solution (après avoir réfléchi).

Pour comprendre comment gagner, voyons d'abord s'il y a des situations dans le jeu dans lesquelles on est sûr de pouvoir gagner quand c'est à notre tour de jouer (des ''positions gagnantes). En quelque sorte, on part de la fin.

Il y a des positions gagnantes triviales, ce sont celles où il ne reste plus qu'une lettre en jeu. Si la lettre comporte \(n\) allumettes, on peut noter cette position \([n]\). Dans ce cas on ramasse toutes les \(n\) allumettes de ladite lettre et c'est gagné.

Maintenant, que se passe-t-il s'il reste deux lettres en jeu ? Là il y a deux cas :

  • Si les deux lettres comportent le même nombre d'allumettes ( \( [n,n] \) ), alors on est mal. En effet l'adversaire possède une stratégie imparable : jouer en miroir, c'est-à dire jouer à chaque fois comme nous sur l'autre lettre. Il est ainsi assuré de prendre la dernière allumette. Ce cas est donc une position perdante.
  • Si les deux lettres n'ont pas le même nombre d'allumettes, alors c'est le contraire, on a une position gagnante ; en effet on peut amener l'adversaire au cas précédent en retirant le bon nombre d'allumettes à la lettre qui en comporte le plus.

Plus compliqué, il y a maintenant trois lettres en jeu. Que faire ?

  1. Si deux des lettres ont le même nombre d'allumettes \([n,n,m]\), on sait maintenant qu'on peut gagner en enlevant toutes les allumettes de la troisième.
  2. Le cas le plus simple \([m,n,p]\) avec \([m \neq n \neq p]\) est \([1,2,3]\), manifestement perdant puisque chaque coup possiblement joué ramène l'adversaire à un cas précédent gagnant. Donc, \([1,2,p>3]\) et \([1,3,p>3]\) sont gagnants.
  3. Qu'en est-il de \([1,4,5]\) ? De même que dans le cas précédent, chaque coup possiblement joué ramène à un cas précédent gagnant. Donc c'est perdant. Et donc tous les \([1,4,p>5]\) et \([1,5,p>5]\) sont gagnants.
  4. Du coup, en partant du mot HOY...

Cliquer pour dévoiler le bonus qui généralise le jeu (après avoir réfléchi). Cliquer pour dévoiler le bonus qui généralise le jeu (après avoir réfléchi).

  1. Progressivement, il apparaît que toutes les positions sont soit gagnantes, soit perdantes. Cela provient en fait de la symétrie du rôle des joueurs.
  2. Il apparaît aussi que les positions perdantes \([1,n,p]\) sont de la forme \([1,n,n+1]\) avec \(n\) pair, ou autrement dit, \([1,n,n-1]\) avec \(n\) impair. Il y a donc pour chaque valeur de \(n\) une unique valeur possible pour \(p\) correspondant à une position perdante, qui sera \(n+1\) ou \(n-1\) en fonction de la parité de \(n\).
  3. Cela peut s'exprimer plus simplement sous la forme \(p=n \oplus 1\) où \( \oplus \) est la fonction d'addition binaire (appelée également ou exclusif ou XOR en informatique).
  4. Les premières positions perdantes \([m,n,p]\) sont \([2,4,6]\), \([2,5,7]\), \([2,7,9]\) et \([2,8,10]\) ; le cas général est \([2,n,n \oplus 2]\).
  5. Les positions perdantes à trois lettres \([m,n,p]\) sont \([m,n,m \oplus n]\).
  6. On peut alors conjecturer que plus généralement, les positions perdantes \([m_i]\) sont celles pour lesquelles \(\bigoplus_{m_i} = 0\) (cette conjecture se démontre facilement, cf la section 2.4 du lien en fin de texte).

Par définition d'une position gagnante, il est toujours possible de partir de n'importe laquelle de celles-ci pour mettre l'adversaire en position perdante en un unique coup. Et réciproquement jouer une position perdante mettra systématiquement l'adversaire en position gagnante. Les positions gagnantes sont toutes celles pour lesquelles \(\bigoplus_{m_i} \neq 0\).

En pratique, il n'est pas complètement trivial de jouer un bon coup à partir d'une position gagnante. Mais ce n'est pas trop difficile non plus. Illustrons cela sur l'exemple du défi, en écrivant la décomposition binaire de chaque nombre d'allumettes constituant les lettres (avec bit le plus fort à gauche) :

[ b : 4 2 1 ]
[ 5 : 1 0 1 ]
[ 6 : 1 1 0 ]
[ 4 : 1 0 0 ]

On peut agir sur n'importe quelle lettre qui a le bit le plus fort allumé, c'est-à-dire toutes dans notre cas, et la transformer de façon à avoir une somme binaire totale nulle. Il suffit pour cela de la transformer en la somme binaire de toutes les autres lettres, c'est-à-dire faire en sorte que le nombre de 1 dans chaque colonne soit pair. L'intérêt d'avoir le bit le plus fort allumé, c'est d'être sûr que le nombre d'allumettes résultant pour la lettre transformée sera plus petit.

Ainsi à partir de \([5,6,4]\) on a trois choix possibles : \([2,6,4]\), \([5,1,4]\), et \([5,6,3]\), qui mettent toutes l'adversaire en position perdante.

Ce jeu est connu sous le nom de jeu de Nim (en France il est également dénommé jeu de Marienbad en raison de sa présence dans le film L'année dernière à Marienbad), et il est décrit en détails entre autres dans le classique Berlekamp, Conway, & Guy : Winning Ways for your Mathematical Plays. Il y a des variations et des généralisations bien plus complexes.

Note : ce texte sur la théorie des jeux a une approche didactique assez similaire à celle présentée ici.

Questions ou commentaires bienvenus.

Notes

[1] D'ailleurs il y a eu deux autres défis entre temps.

[2] On remarque que le jeu peut être également fait avec "564" écrit en style LCD.

vendredi 22 mars 2013

Palindromes à 351 chiffres

Le mathématicien Cédric Villani propose un défi mathématique aux lecteurs du Monde : dénombrer les nombres palindromes (c'est à dire qui ne varient pas pas quand on les lit de gauche à droite et de droite à gauche) à 351 chiffres et trouver la plus petite différence absolue séparant deux d'entre eux.

Deux questions de difficultés inégales.

Cliquer pour dévoiler la solution à la première question (après avoir réfléchi). Cliquer pour dévoiler la solution à la première question (après avoir réfléchi).

Concernant le dénombrement, il y a pour construire un palindrome le choix des 176 premiers chiffres (à l'exception du tout premier qui ne peut être nul), qui imposent par la suite les autres pour satisfaire la condition de palindrome. Soit un total de \(N = 9 * 10^{175}\).

Généralisation : à \(n\) chiffres, \(N = 9 * 10^{\lfloor\frac{n-1}{2}\rfloor}\).

Cliquer pour dévoiler la solution à la seconde question (après avoir réfléchi). Cliquer pour dévoiler la solution à la seconde question (après avoir réfléchi).

Quant à la question de la différence minimale \(D\) entre deux palindromes différents \(P\) et \(G\) (avec \(P\) le plus petit des deux), on peut voir les choses de la façon suivante.

Si on raisonne toujours sur les 176 premiers chiffres, en changeant le dernier de ceux-ci sur un palindrome quelconque il est facile de construire deux palindromes de différence \(D = 10^{175}\) (par exemple P=\(\overbrace{5...5}^{175}0\overbrace{5...5}^{175}\) et G=\(\overbrace{5...5}^{175}1\overbrace{5...5}^{175}\) ). Mais peut-on faire mieux ?

Il n'est pas possible d'avoir \(D<10\). En effet si le dernier chiffre \(p\) de \(P\) diffère de celui de \(G\) \(g\), alors le premier aussi. Or pour minimiser la différence \(G-P\) dans ce cas, on doit avoir \(g-p=1\), Ainsi on voit que P=\(4\overbrace{9...9}^{349}4\) et G=\(5\overbrace{0...0}^{349}5\) ne diffèrent que de \(D = 11\) (en soi un palindrome aussi), ce qui est beaucoup mieux que l'exemple précédent, et même inaméliorable, car deux palindromes de 351 chiffres ne peuvent clairement pas différer de \(D=10\).

Généralisation : à \(n\) chiffres, \(D=11\), sauf pour les cas \(n=1\) où \(D=1\) et \(n=3\) où \(D=10\).

Par ailleurs il est facile de trouver deux palindromes de 350 chiffres et de 351 chiffes qui diffèrent seulement de 2.

jeudi 10 janvier 2013

Successful random papers

The famous internet RFC 2795 (The Infinite Monkey Protocol Suite) states that a monkey hitting keys at random on a typewriter keyboard for an infinite amount of time will almost surely type a given text, such as the complete works of William Shakespeare.

A modern variation of this monkey-fed typewriter consists of programs outputting random text sequences from a words database and a set of rules called grammar. Such programs are nicknamed generators.

Examples of generators in the area of science are SCIgen who produces meaningless computer science papers, or Mathgen who creates nonsensical math papers. The latter provides even the source code to generate full-size random e-books featuring custom-named authors, which can then be printed out at Lulu.

One can think that target journals for publication of such gems should be world-class journals such as the Journal of Irreproducible Results or the Journal of Universal Rejection, where no failure is to expect.

But it happens that from time to time so-called random papers are accepted in real-world publications. For example, a paper entitled Deconstructing Access Points has been accepted in The Open Information Science Journal, whereas Independent, Negative, Canonically Turing Arrows of Equations and Problems in Applied Formal PDE has been accepted in Advances in Pure Mathematics. As far as conferences are concerned, the talk Rooter: A Methodology for the Typical Unification of Access Points and Redundancy has been accepted at the WMSCI2005 and the talk Towards the Simulation of E-Commerce has been accepted at the 2008 International Conference on Computer Science and Software Engineering.

This highlights that some slimy journals or conferences are ready to accept fees to publish irrelevant non-peer-reviewed papers while it may be deduced that some authors are ready to pay (institutional) money in exchange for easy CV bullets.

It also reminds of Georges Perec's Experimental demonstration of the tomatotopic organization in the Soprano (pdf) and of the Sokal affair[1], which was more of a critic of post-modernism.

Update (March 2015): a more recent hoax in sociology has been ployed and unveiled by Arnaud Saint-Martin and Manuel Quinon after their postmodern-funny-gibberish paper entitled Automobilités postmodernes : quand l'Autolib' fait sensation à Paris has been accepted and published in Sociétés, a journal whose editor-in-chief is the French iconic sociologist Michel Maffesoli.

Note

[1] In 1996 Physics professor Alan Sokal managed to publish his manuscript Transgressing the Boundaries: Towards a Transformative Hermeneutics of Quantum Gravity in the Social Text Spring/Summer "Science Wars" issue. The text included jokes such as: Just as liberal feminists are frequently content with a minimal agenda of legal and social equality for women and 'pro-choice', so liberal (and even some socialist) mathematicians are often content to work within the hegemonic Zermelo–Fraenkel framework (which, reflecting its nineteenth-century liberal origins, already incorporates the axiom of equality) supplemented only by the axiom of choice.

mardi 4 septembre 2012

Les problèmes juifs

Alors que le musée d'Israël à Jérusalem présente jusqu'à la fin de l'année une exposition sur le judaïsme haredi, voici cinq petits problèmes mathématiques.

  • 1) Soient un segment du plan et un cercle dont le segment soit un diamètre. Soit un point du plan n'appartenant ni au cercle ni au segment, tracer avec seulement une règle la perpendiculaire au segment passant par le point.
  • 2) Un quadrilatère de l'espace est tangent à une sphère (c'est-à-dire que chacun de ses côtés est tangent à la sphère). Montrer que les points de tangence sont coplanaires.
  • 3) Trouver toutes les fonctions \(F : \mathbb{R} \rightarrow \mathbb{R}\) telles que pour tous \(x_1\) et \(x_2\) : \(F(x_1) - F(x_2) \leq (x_1 - x_2)^2\).
  • 4) Soit un parallélogramme. En utilisant uniquement une règle, diviser l'un des côtés en six segments de même longueur.
  • 5) Un cercle est inscrit dans une face d'un cube de côté \(a\). Un autre cercle est circonscrit à une face adjacente de ce cube. Quelle est la distance minimale entre les points des cercles ?

Ces problèmes ont été spécialement conçus pour avoir une solution simple à comprendre mais (souvent) très difficile à trouver ; ils font partie d'une liste, les problèmes juifs.

Pourquoi ? Dans les années 70-80, lors des examens oraux d'admission au département de mathématiques (Mekh-mat) de l'Université de Moscou (MSU), ils étaient proposés aux candidats juifs et autres indésirables. Comme les problèmes étaient très difficiles, les candidats échouaient la plupart du temps, mais comme les solutions étaient simples à comprendre, l'administration était protégée contre les éventuelles plaintes ou autres recours. En soumettant des problèmes différents aux candidats « acceptables » et aux « inacceptables », l'Université pratiquait subtilement une discrimination basée sur la technique. La liste de ces problèmes juifs a longtemps été tenue secrète, et sa publication présente une valeur tant mathématique qu'historique. Certains d'entre eux sont élégants, d'autres sont fastidieux, et enfin certains sont présentée d'une façon ambiguë, voire incorrecte. Un échantillon a été publié par les chercheurs Tanya Khovanova et Alexey Radul. Le mathématicien Ilan Vardi a également publié une liste similaire et y évoque « peut-être pour la première fois, une utilisation politique des mathématiques ».

vendredi 22 juin 2012

Dobble

Le jeu Dobble est né d'un concept de Denis Blanchot qui semble simple : 55 cartes, 8 symboles différents par carte, et toujours un et un seul symbole commun entre chaque carte. Il faut être le plus rapide à trouver ce symbole commun[1].

Exemple : quel est l'unique symbole commun aux cartes suivantes ?

[ ⚑ ★ ☋ ◐ ☎ ☕ ☣ ☯ ] et [ ☪ ☕ ♞ ♬ ⚓ ⚷ ✈ ➑ ]

Une question naturelle qui se pose est : comment construire un ensemble de cartes muni de cette propriété : pour toute paire de cartes, il existe un un et seul symbole commun ?

En indexant les symboles, par des entiers, la question peut être reformulée de la manière suivante : comment construire une famille \(S_i\) de parties de \([|1,n|]\) telles que \(\forall (i,j): \# S_i = \# S_j\) et \(\# (S_i \cap S_j) =1\) ?

Pour commencer, prenons 2 symboles par carte. Si on note [ 1 2 ] la première carte, alors la deuxième carte devra être de la forme [ 1 3 ], puis on a deux solutions pour une troisième carte : [ 1 4 ] ou [ 2 3 ]. Seulement, dans le premier cas, il n'est plus possible d'ajouter d'autres cartes qui ne soient pas de la forme [ 1 x ], ce qui signifie que 1 est un unique symbole commun à chaque paire de cartes, ce qui n'est pas vraiment ce qu'on veut. Dans l'autre cas, on obtient un système constitué de { [ 1 2 ], [ 1 3 ], [ 2 3 ] } qui répond bien à nos attentes.

Plan de Fano Avec trois symboles par carte, on peut construire de même un ensemble de façon itérative, dont chacun pourra s'assurer que chaque couple de cartes possède exactement un unique chiffre en commun : { [ 1 2 3 ], [ 1 4 5 ], [ 2 4 6 ], [ 3 5 6 ] }. On a aussi la possibilité suivante :

[ 1 2 3         ]
[ 1     4 5     ]
[   2   4   6   ]
[ 1         6 7 ]
[   2     5   7 ]
[     3 4     7 ]
[     3   5 6   ]

Soit maintenant T l'ensemble des parties de \([|1,7|]\) à 2 éléments. Un élément de T ne peut être inclus dans deux cartes différentes, sinon leur intersection aurait strictement plus d'un chiffre en commun. De plus, à chaque carte peuvent être associés 3 éléments de T, nécessairement différents d'une carte à l'autre, ce qui fait 21 éléments, soit le cardinal de T. Conséquemment chaque élément de T est inclus dans une et une seule des cartes.

Un ensemble \(S\) à \(n\) éléments et un ensemble de parties \(K\) de \(S\) à \(k\) éléments (blocs) tels que chaque partie de \(S\) à \(t\) éléments soit incluse exactement dans un bloc constituent un système de Steiner \(S(t,k,n)\). Le jeu de cartes précédent est donc isomorphe à \(S(2,3,7)\), ce qu'on peut illustrer par le plan de Fano ci-dessus, où les symboles sont les chiffres et les cartes les lignes. Deux lignes quelconques (blocs) s'intersectent toujours au niveau d'un unique symbole.

Remarquons enfin qu'à chaque carte on peut associer un mot binaire, les chiffres codant les positions des bits allumés. Les 7 mots sont tous sur une sphère de rayon 3 et Hamming-équidistants de 4, leur énumération forme la matrice d'incidence du plan de Fano.

[ 1 1 1 0 0 0 0 ]
[ 1 0 0 1 1 0 0 ]
[ 0 1 0 1 0 1 0 ]
[ 1 0 0 0 0 1 1 ]
[ 0 1 0 0 1 0 1 ]
[ 0 0 1 1 0 0 1 ]
[ 0 0 1 0 1 1 0 ]

Pour finir, un petit exercice au lecteur : le jeu de Dobble est-il, tel le jeu de Set, un système de Steiner, et si oui, lequel ?

La réponse : comme l'explique très bien cet article, la structure sous-tendant le Dobble est le plan projectif d'ordre 7 \(PG(2,7)\) (le plan de Fano est d'ordre 2), qui est aussi le système \(S(2,8,57)\). Le jeu devrait donc avoir en principe 57 symboles différents et 57 cartes, or il n'en comporte que 55, apparemment pour des raisons techniques de production. Il en résulte une certaine asymétrie, puisque 15 symboles apparaissent moins fréquemment que les autres, dont un (, celui commun aux deux cartes manquantes) pourrait être qualifié de "rare". Les plus malins en déduiront éventuellement des stratégies gagnantes basées sur ces statistiques.

Notes

[1] Le jeu existe en 5 modes : la tour infernale, le puits, la patate chaude, attrapez-les tous, le cadeau empoisonné.

- page 1 de 2