Tout le monde connaît les petites devinettes qu'on se pose lors (ou à la place) d'un dessert après un déjeuner frugal au restaurant universitaire. Voici une jolie devinette géométrique :

Sans lever la main, relier tous les neuf points suivants par quatre lignes droites.

°             °             °



°             °             °



°             °             °

Ce n'est pas si évident. La solution à voir dans le vidéo ci-dessous montre que nos habitudes nous empêchent de dépasser certaines limites...

MathOMan relie 9 points avec 4 droites

Souriante la petite Bin prend sa revanche et me lance le défi géométrique suivant :

Sans lever le stylo, tracer un cercle et son centre (pas plus).

Voici la vidéo où elle montre sa solution rusée à ce petit problème très troublant pour un spécialiste de la connexité.

Bin trace une cercle et son centre

Les commentaires du billet un exercice de topologie sur le blog de PB soulevait quelques questions intéressantes. Une parmi elles possède la réponse suivante :

Dans une variété topologique connexe on peut relier tout couple de points distincts par un chemin injectif.

Remarquons que ce résultat ne vaut plus sur des espaces non-séparés comme la droite avec un point dédoublé (une variété topologique est séparée par définition).

Démonstration :

Rappellons d'abord que sur une variété topologique les notions connexe et connexe par arcs sont équivalentes.
Quelques notations : B(r) désigne la boule ouverte de rayon r et de centre 0 dans pour la norme euclidienne. Pour noter la boule fermée, on mettra une barre dessus.

Soit M une variété topologique de dimension n et x un point de M. Notons E le sous-ensemble de M constitué de x et de tous les points qu'on peut relier injectivement à x. Notre but est de prouver que E=M. Vu que M est connexe et que E est non-vide, il suffit de montrer que E est ouvert et fermé.

• Ouvert : Soit y un point arbitraire dans E. Dans l'atlas de la variété M il existe une carte .
  
  
  • Si alors car dans une boule on peut toujours relier injectivement deux points distincts par un segment.
  
  
  • Dans l'autre cas où x n'est pas dans U nous posons r=1/2 et nous allons prouver que On sait déjà qu'il existe un chemin injectif tel que et . L'ensemble est compact, et comme M est séparé, on déduit qu'il est fermé (voir aussi remarque 2 en bas).
    
    Par continuité l'image réciproque est fermé dans [0,1] et possède donc un plus petit élément . On a l'inégalité car
    
    Le point ne peut pas être contenu dans la boule ouverte , sinon le serait également pour assez petit, contrairement à la définition de . Donc est sur le bord de la boule . Par construction on peut relier injectivement à tout point de sans rencontrer . En juxtaposant ces deux chemins, on relie donc injectivement x à n'importe quel point de Donc est un voisinage ouvert de y contenu dans E.

    



• Fermé : Nous devons prouver que le complémentaire de E est ouvert. Soit donc y un point arbitraire dans M\E, autrement dit y est un point qui ne peut pas être relié injectivement à x. On prend une carte . Alors on sait déjà que x ne peut pas être dans U. De deux choses l'une :
  
  
  • Soit l'ouvert U est une partie de M\E — dans ce cas on a terminé.
  
  
  • Soit U n'est pas inclu dans M\E — dans ce cas il existe un point z dans l'intersection . Pour on a . Il existe un chemin injectif allant de x à z. L'ensemble

    

    est compact car c'est l'intersection d'un compact et d'un fermé. (Pour voir que est fermé on utilise, comme en haut, le fait que M est séparé.)
    Parmi tous les points du compact il existe un ayant norme minimale. Nous notons w ce point et son correspondant sur la variété (toujours via la carte ). Clairement . D'une part on a la restriction de à et d'autre part le chemin correspondant au segment [w,0] ; en juxtaposant ces deux chemins injectifs on obtient un chemin de x à y qui, par construction, est injectif. Contradiction, ce cas ne peut pas avoir lieu.

    

Remarque 1 :

L'idée de la preuve est de se ramener à l'intuition que nous avons de notre espace usuel. Quand une trajectoire passe de l'extérieur d'une boule à l'intérieur d'une boule, elle doit forcément traverser le bord de la boule, elle coule comme une rivière. Or cela n'est plus vrai dans les espaces non-séparés comme la droite à deux origines dédoublées, 0' et 0''. Quand je fais un chemin de 0' à 0'' alors je rentre directement dans l'intérieur de la boule [-1,1]'' sans passer par -1 ou par 1. Le chemin apparait miraculeusement de nul part, il jaillit comme une source...

Il est donc intéressant de voir où la preuve ne fonctionne plus dans cet exemple. Evidemment c'est au moment où on utilise le fait qu'un compact d'un espace séparé est toujours fermé. Sur la droite dédoublée l'ensemble [-1,1]'' est compact mais il n'est pas fermé, car son complémentaire n'est pas ouvert.

Remarque 2 :

On est tenté de dire que est fermé comme image réciproque d'un fermé par une application continue. Mais cela serait faux ! En effet, est seulement définie sur U et pas sur toute la variété M. On peut donc dire que est un fermé de l'espace U (pour la topologie induite par M), mais de là on ne peut pas conclûre directement qu'il s'agit d'un fermé de M. C'est pourquoi nous devons faire ce détour :

compact dans B(1),
donc compact dans U,
donc compact dans M,
donc fermé dans M (séparé).

Vous croyez déjà tout savoir sur la multiplication ? Vous allez être surpris ! Voici trois méthodes pour multiplier deux nombres entiers.

• Multiplication posée du bon élève.




 

• Méthode du cancre.
 




Mode d'emploi : A gauche on prend toujours la moitié en arrondissant, s'il le faut, vers le bas ; à droite on prend toujours le double. Puis on supprime les lignes (en noir) dont le nombre gauche est pair et à droite on additionne les lignes restantes (en rouge).
 
 

• Méthode de Karatsuba (publiée en 1962).
On sépare chaque facteur en deux parties

puis on effectue les multiplications suivantes :



Le résultat est ensuite

Remarque
L'idée de tout ça c'est de se ramener à des opérations élémentaires (opérations entre deux nombres entre 0 et 9). Sur un ordinateur le choix d'un bon algorithme peut accélerer considérablement le temps de calcul — quelques jours pour des facteurs constitués de plusieurs milliards de chiffres ! Le calcul avec de très grands nombres n'est pas une question purement théorique mais a beaucoup d'applications, notamment en théorie de cryptage.
 
Questions

1. Pourquoi la méthode du cancre fonctionne-t-elle ? Les deux facteurs jouent des rôles différents; lequel choisir pour quel rôle ?
2. Utilisez la méthode de Karatsuba pour calculer 3116 x 1014. Pourquoi cette méthode fonctionne-t-elle ?
3. Avec la méthode classique (multiplication posée du bon élève), combien de multiplications élémentaires sont nécessaires pour calculer le produit de deux nombres à n chiffres ?
4. En réitérant la méthode de Karatsuba on obtient un algorithme. Combien de multiplications élémentaires sont alors nécessaires pour calculer le produit de deux nombres à n chiffres ? Comparer avec l'algorithme classique.

Réponses
Cliquez pour afficher les solutions en format pdf.

Et pour finir une vidéo présentant une méthode qui produit une belle calligraphie — elle s'appelle donc la multiplication chinoise !

L'idée de base de la multiplications chinoise est le fait suivant : un ensemble de n droites parallèles coupe un autre ensemble de m droites parallèles en nxm points.

Un joli exercice de géométrie

Voici le dessin d'une route. Elle passe tout droit en plein désert, on la voit disparaître à l'horizon.
Au bord de la route il y a des poteaux, tous les quinze mètres. Le dessinateur n'en a représenté que les deux premiers.

Question: Comment peut-on trouver, par construction sur ce dessin, les emplacements des poteaux suivants?

Réponse: Cliquez ici pour la solution.

Remarque: Peut-être plus de bacheliers L que de bacheliers S savent résoudre cet exercice!

Des élèves qui ne viennent pas le jour du contrôle, c'est l'horreur de tout prof qui doit alors concocter un deuxième sujet pour le rattrapage. On comprend donc que très souvent ce deuxième sujet sera un peu plus difficile... Voici une belle petite histoire que des collègues m'ont écrite :

Ce sont quatre taupins qui ont un DS de math le lundi à passer. Ils vont faire la fête toute la nuit du dimanche à l’occasion de l’anniversaire de l’un d’entre eux. Seulement, ils ne se réveillent pas le fameux lundi matin et vont voir mardi le professeur pour s’excuser. Ils lui demandent alors de rattraper le lendemain en argumentant qu’ils ont crevé une roue sur le chemin en guise d’excuse. Le professeur accepte finalement.
Les étudiants bossent toute la nuit et arrivent le matin confiants à l’examen. Le professeur les met dans des salles différentes et leur donne le sujet d’examen qui comporte deux questions.
La première est sur 1 point. Chacun la lit dans son coin et trouve cela très facile. En effet, la question est : « Quelle est la raison qui vous a empêché de passer le DS prévu lundi ? ». Après, ils tournent la page et la seconde question, sur 19 points, est : « Quelle roue a été crevée ? »

Question (niveau probabilités classe de première)

Quelle est la note moyenne (valeur d'expectation) des quatre élèves à laquelle il faut s'attendre ?

Incitation à la réflexion

Pourra-t-on intégrer la question précédente comme troisième question au contrôle sans provoquer une boucle logique ?

Apparemment la question sur un pavage de rectangles posée ici il y a quelques jours est stimulante. Après la solution par produit tensoriel, voici une autre qui repose sur une activité habituellement réservée aux enfants: le coloriage. (Les matheux ne sont que de grands enfants !) Merci à David Caisson qui m'a envoyé cette solution extraite du livre Solving Mathematical Problems de Terence Tao.

L'idée de T. Tao est aussi simple que belle: on colore en vert tous les rectangles ayant un côté horizontal entier, et en rouge tous les autres rectangles. Un argument topologique de connexité nous assure alors que dans le grand rectangle on peut relier les deux côtés verticaux par un chemin vert ou les deux côtés horizontaux par un chemin rouge. (Pour ceux qui ne connaissent pas encore la notion de connéxité : c'est une sorte de théorème des valeurs intermédiaires qui dit que deux lignes reliant les côtés opposés se coupent forcément). Or un chemin vert consiste en la juxtaposition de rectangles verts, donc sa longueur horizontale est entière; et de manière analogue pour un chemin rouge.

Vous pouvez lire la solution complète ici.

Cette "solution" m'a laissé perplexe car sur les trois premières pages l'auteur n'avance pas beaucoup, puis au tout dernier paragraphe il évoque, sans les traiter, quelques obstacles qui pourraient éventuellement se poser. Et avec un peu d'esprit critique on trouve que la démonstration est fausse! Voici un contre-exemple.

 

 
La largeur est 4 et la hauteur est 3,5. Pourtant il n'y a pas de chaîne verte mais seulement une chaîne rouge dont on ne peut rien déduire sur la hauteur (car elle possède des décalages) ni sur la largeur (car les rectangles rouges n'ont pas de largeurs entières).

Mais Terence Tao ne serait pas Terence Tao, porteur de la Médaille Fields 2006 (sorte de prix Nobel pour mathématiciens), si l'idée de sa preuve était entièrement fausse ! En effet, après une petite recherche sur internet, je me rends sur son blog personnel et j'y trouve une liste d'errata où il corrige, entre autres, cette preuve. Voici l'amélioration qu'il apporte:

On colore les rectangles comme avant, mais seulement leurs intérieurs. Ensuite on colore en vert les côtés verticaux ouverts, et le reste en rouge.

Maintenant mon contre-exemple ne résiste plus! On peut relier les deux côtés verticaux par un chemin vert.


 
Pourquoi cette démonstration améliorée fonctionne-elle ? Et bien, lorsqu'on parcourt un chemin vert disons, alors chaque fois qu'on quitte un rectangle vert pour passer dans un autre, ça se fait sur un segment vertical dont l'abscisse est un entier.

Voilà donc une jolie solution purement topologique, sans analyse. Je ne pense pas qu'elle s'adapte aux dimensions supérieures.

Il y a beaucoup de lycées français dans le monde entier mais il n'y a qu'un seul bac français. Ca demande une grande organisation (gérée par l'Agence pour l'enseignement français à l'étranger title="AEFE - Agence pour l'enseignement français à l'étranger"), car les dates des épreuves varient de continent en continent. Le candidats métropolitains s'intéressent chaque année au sujets de bac posé à Pondichéry en Inde, qui est le premier centre d'examen de l'hémisphère nord à passer le bac. Cette année la date de l'épreuve de maths en Inde était le 16 avril.

Je viens de mettre en ligne le sujet de l'épreuve de mathématiques de la série ES et j'ai rédigé un corrigé.

Je trouve toujours intéressant les barèmes des QCM. Dans cette épreuve le QCM est sur 3 points, et ça se présente ainsi :

Pour chacune des quatre questions suivantes trois réponses sont proposées, une seule de ces réponses convient.
Barème : Une réponse exacte rapporte 0,75 point, une réponse inexacte enlève 0,25 point. L’absence de réponse ne rapporte ni n’enlève de point. Si le total donne un nombre négatif, la note attribuée à cette partie sera ramenée à zéro.

Forcément, si on n'attribue jamais de total négatif alors, en termes de probabilités, c'est un jeu à espérance strictement positive, c'est-à-dire un candidat mal préparé a tout intérêt à répondre au hasard plutôt que de rien répondre. En fait, faisant le calcul, on trouve qu'un candidat répondant au hasard peut s'attendre à obtenir une moyenne de sur cet exercice à 3 points.

Vous avez un troupeau de 101 vaches vérifiant l'hypothèse suivante : chaque fois que vous prenez 100 vaches parmi elles il est possible de les séparer en deux parties de 50 vaches telle que les deux parties ont le même poids.
Démontrez que toutes les 101 vaches ont le même poids.

D'ailleurs, pour ceux qui se sont posés la question : le poids d'une vache (Bos primigenius taurus) se situe entre 500 et 800 kg, et celui d'un taureau peut atteindre 1200 kg. Evidemment cela n'a pas d'importance pour l'exercice.

Et comme je n'aime pas les billet trop courts, voici un autre exercice (indépendant du premier). Retrouvez les neuf mathématiciens célèbres cachés dans la phrase suivante :

Quand t’auras fini de classer des cartes et de les ranger, coche ici et ferme à clef la grange : la dernière fois t’as laissé tout ouvert, et les chats l’ont saccagée et ont volé des poissons.

Mon billet récent sur la dimension maximale d'un sous-espace affine contenu dans l'ensemble des matrices non-inversibles m'a inspiré les réflexions suivantes, une sorte de version différentiable de ce résultat.

On note l'espace des matrices n x n à coefficients réels et le sous-ensemble des matrices inversibles. On sait que est un ouvert dans . En effet c'est l'image réciproque de l'ouvert par l'application continue déterminant

On peut même dire un peu plus : le déterminant étant polynômial en le complémentaire des matrices inversibles, c'est-à-dire l'ensemble des matrices de déterminant nul,

est une hypersurface algébrique. Géométriquement parlé est un fermé de qui ressemble localement à un hyperplan (c'est-à-dire à un sous-espace affine de dimension n²-1). Enfin, cela est vrai en presque tous les points, ceux où la différentielle du déterminant ne s'annulle pas (points réguliers). En revanche, en les points où la différentielle du déterminant est nulle (points singuliers), l'hypersurface ne ressemble plus à un sous-espace affine. Il peut y avoir un croisement comme par exemple

ou un rétrécissement comme par exemple

(Pour plus d'images de surfaces algébriques visitez le la galerie de Herwig Hauser.)

Il est évident que la différentielle du déterminant est nulle à l'origine. Donc notre hypersurface possède une singularité à l'origine. Le résultat suivant dit qu'il s'agit d'une singularité de type rétrécissement, car l'hypersurface de dimension n²-1 y perd quelques dimensions — il y reste juste assez de place pour n²-n dimensions...

Proposition :

Le nombre n²-n est la plus grande dimension possible d'une sous-variété différentiable F de telle que

Démonstration :

• L'ensemble des matrices dont la première ligne est nulle est un sous-espace vectoriel (et donc en particulier une sous-variété différentielle) de dimension n²-n. Evidemment il contient l'origine 0 et est contenu dans .


• Soit F une sous-variété de de dimension n²-n+1 et telle que . Nous allons prouver que F contient une matrice inversible.
  Au voisinage de l'origine la sous-variété F est décrite par un système de n-1 équations

  

  tel que les différentielles sont linéairement indépendantes à l'origine. On résoud ce système par le théorème des fonctions implicites, c'est-à-dire on peut isoler (théorétiquement) n-1 des coordonnées et les exprimer par les autres. On a ainsi, toujours au voisiange de l'origine, n²-n+1 coordonnées variables et n-1 coordonnées isolées (fonctions différentiables des coordonnées variables).
  Maintenant je peux poursuivre mon raisonnement de la preuve du cas affine : par des permutations de lignes et de colonnes je m'arrange à ce que les coordonnées isolées soient toutes au-dessus de la diagonale matricielle ; puis je prends les coordonnées sur la diagonale toutes égales à un nombre non-nul et proche de 0 et les autres coordonnées variables égales à 0. Ainsi j'obtiens une matrice inversible qui est dans F.

Mathias Wandel a construit une calculatrice en bois, basée sur la notation binaire !

Ceux qui ont vu le film Matrix se rapellent des suites constituées des chiffres 0 et 1 qui défilent sur l'écran presque interminablement, comme par exemple 10011100100001101010111111. Beaucoup appellent cela un "nombre binaire", mais cette appellation est mal choisie, mieux est de l'appeler "écriture binaire d'un nombre naturel". Pour mieux comprendre cette écriture bizarre faisons un petit détour.

Les nombres naturels

Les nombres naturels sont le premiers que nous avons appris à l'école : zéro, un, deux, trois, quatre,... Il y en a une infinité, car à chaque nombre on peut ajouter 1 :

zéro = 0 , un = 1 , deux = 1+1 , trois = 1+1+1, quatre = 1+1+1+1 , etc.

Cette écriture en forme de somme est essentiellement la même que l'écriture primitive par bâtons qu'on trouve sur les murs des prisons : par exemple |||| pour quatre ou |||| ||| pour huit. Elle prendrait trop de place pour des grands nombres. Pour éviter cela on utilise une ruse, que j'illustre d'abord par quelque chose que tout le monde connaît et utilise :

Le système décimal

Il fonctionne comme suit.

• Nous convenons que les dix premiers nombres (zéro, un, deux, trois, ..., huit, neuf) soient représentés par les dix symboles 0, 1, 2, 3, ..., 8, 9.
• Nous convenons que le onzième nombre, à savoir le 9+1 ou encore le dix, est représenté par la juxtaposition de 1 et de 0 : donc 10.
• Puis on donne une règle pour les autres juxtapositions en utilisant les puissances de 10. Voici deux exemples:

  et .

Il n'est pas difficile de montrer que tout nombre naturel peut s'écrire dans ce système en n'utilisant que dix chiffres. Le fait qu'on ait pris dix chiffres est un pur hasard, certainement lié au fait que nous comptons dix doigts. Cela marcherait de la même manière si nous nous étions contentés par exemple de sept chiffres ; dans ce cas là, la juxtaposition signifierait le nombre sept et signifierait (c'est-à-dire dans notre système décimal habituel).

Dans toutes les langues que je connais il y a les noms particuliers "onze" et "douze" ; on dit "vingt-deux", mais on ne dit pas "dix-deux", on dit "douze". Cela montre qu'il fût un temps où nous ne comptions pas dans en dizaines mais en douzaines.

Le système binaire

Maintenant au lieu de prendre dix chiffres nous nous contentons du minimum syndical, des deux chiffres 0 et 1. C'est vraiment le minimum car avec un seul chiffre nous ne pourrions pas aller très loin, nous serions restreints à la notation primitive par bâtons |||| .

La juxtaposition signifie alors le nombre deux et signifie , c'est-à-dire , donc cinq dans notre système décimal habituel.

Ecrivons quelques nombres naturels dans les deux systèmes, binaire suivi de décimal :

0 est 0, 1 est 1, 10 est 2, 11 est 3, 100 est 4, 101 est 5, 110 est 6, 111 est 7, 1000 est 8, etc.

est , est , est (un méga)

Ces derniers nombres sont très familiers en informatique. C'est simplement parce que les ordinateurs utilisent le système binaire pour compter. En effet, la manière la plus simple pour communiquer avec une machine c'est de lui donner seulement deux signaux (et pas trois ou plus), comme oui/non, comme on/off, comme gauche/droite (dans les leviers de la machine en bois) ou comme haut/bas, etc.


Exemples de passage d'un système à l'autre

Résumons par deux exemples les règles qui permettent de passer du système binaire au système décimal :

• Soit un naturel écrit dans le système binaire. Alors dans le système décimal c'est le nombre
  


• Soit un naturel écrit dans le système décimal (!). Pour le transformer en écriture binaire nous devons d'abord trouver la plus grande puissance de 2 qui "rentre" dans . Nous savons que et que . Donc est la plus grande puissance de 2 qui "rentre" dans et ainsi l'écriture binaire de nécessitera onze chiffres le premier étant 1. Nous avons La plus grande puissance de 2 qui "rentre" dans est On est passé de la dixième puissance directement à la sixième ; les trois puissances "sautées" (neuvième, huitième, septième) sont représentées par des zéros. Donc l'écriture binaire de notre nombre commence par les cinq chiffres On poursuit de la même manière : ; la plus grande puissance de 2 qui "rentre" dans est Puis ; la plus grande puissance de 2 qui "rentre" dans est . Le dernier reste est Ainsi nous obtenons (notation binaire).


• Pour nous rassurer de notre dernier résultat faisons le test et re-transformons l'écriture binaire en écriture décimale. Le nombre en binaire devient en décimal donc (notation décimale).

Compris ? Et n'oubliez pas : il y a 10 sortes de gens au monde : ceux qui comprennent la notation binaire et ceux qui ne la comprennent pas ;-)

Matthias Wandel est le fils d'un éleveur de vaches allemand qui a émigré au Canada en 1980 avec sa famille. Il construit des choses fabuleuses en bois (notamment la calculatrice binaire en bois), mais il programme également des jeux en ligne, comme par exemple The Eyeballing Game.


On peut y entraîner sa vision approximative en géométrie plane. Les huit épreuves proposées sont les suivantes.

• Ajuster un sommet pour obtenir un parallelogramme,
• trouver le milieu entre deux points,
• trouver la bissectrice d'un angle,
• placer le centre d'un triangle (centre du cercle inscrit, l'intersection des bissectrices),
• trouver le centre d'un cercle,
• former un angle droit,
• placer l'intersection de trois droites concourantes.

En principe, ce sont toutes des constructions géométriques qu'un élève de collège peut réaliser à la règle et au compas. Or ici il ne s'agit pas d'ancrer votre compas sur votre écran d'ordinateur LCD et y percer des trous, mais d'essaier de trouver à l'oeil nu le point demandé. Vous devez jouer trois tours pour obtenir un score final; vous allez voir que vous vous améliorez à chaque tour. Pensez à enfoncer la souris, puis à la relacher à l'endroit souhaité (vous ne pouvez plus corriger après).

Le score est mesuré en écarts (pixels) entre votre résultat et le vrai — donc plus bas mieux c'est. Mon score total des trois tours était de 5,05 (ma meilleure réponse était de 0,2). C'est un résultat très moyen... pas terrible pour un mathématicien! Ma seule excuse: je suis myope et astighmate ;-)