Les petites énigmes du vendredi. Trois problèmes de Martin Gardner

Chaque vendredi, je publie sur ce blogue de petites énigmes logico-mathématiques, ainsi que la solution des énigmes de la semaine précédente.
Merci de ne pas poster vos solutions ici, de manière à permettre à tout le monde de jouer.
Les questions demandant des éclaircissements ou des précisions sont par contre les bienvenues.

Enigmes de la semaine

Mes trois énigmes de la semaine sont reprises à Martin Gardner, plus précisément à son recueil Le paradoxe du pendu et autres divertissements mathématiques (édition originale, en anglais, 1969; traduction française: 1971).

1.  Six vedettes de Hollywood forment un groupe social de caractère très particulier. Quand on les prend deux à deux, ou bien elles s’aiment, ou bien elles se haïssent. Il n’y a aucun ensemble à trois éléments qui s’aiment mutuellement. Démontrer qu’il y a au moins un ensemble de trois éléments qui se haïssent mutuellement.

(Ce problème conduit à un nouveau domaine très intéressant de la théorie des graphes, celui des «graphes chromatiques vides en bleu», dont nous expliquerons la nature après avoir donné la solution du problème (p. 167))

2. Miranda remporte un set de tennis par 6 à 3. Cinq points ont été gagnés par la joueuse qui n’avait pas le service.

Qui avait le service au début du set? (p. 71).

3. Un beau matin vers les dix heures, M. Smith et son épouse quittent en voiture leur domicile dans le Connecticut pour se rendre chez les parents de Madame qui habitent en Pennsylvanie. Ils ont décidé de s’arrêter en chemin pour dîner au restaurant Les Chandelles, de Patricia Murphy, à Westchester.

Cette visite ches ses beaux-parents, jointe à quelques tracas dans son travail, fait que Monsieur Smith garde un silence maussade. Ce n’est que vers onze heures que Mrs Smith se risque à demander: «Avons-nous fait beaucoup de chemin mon chéri?»

M. Smith jette un coup d’oeil à son compteur et laisse tomber: «La moitié de ce qu’il nous reste à parcourir jusque chez  Patricia Murphy.»

Ils arrivent à midi au restaurant, prennent tout leur temps pour manger, puis poursuivent leur route. Nouveau silence qui n’est brisé que vers les cinq heures quand Mrs Smith, à 200 miles de l’endroit où elle a posé sa première question, en risque une seconde: « Quelle distance nous reste-il à parcourir ?».

«Moitié moins loin que d’ici chez Patricia Murphy», répond monsieur en grognant.

Ils arrivent à destination à 19 heures. Selon la densité du trafic, M. Smith a dû conduire à une vitesse très variable. Il est pourtant très simple de déterminer, et c’est l’objet du problème, quelle est la distance exacte parcourue par les Smith d’une maison à l’autre. (p. 76)

Solutions aux énigmes de la semaine dernière

1. Les cyclistes, par définition, pédalent pendant une heure avant de se rencontrer à mi-chemin ( car ils sont à 30 kms l’un de  l’autre au départ et avancent à 15 km/h). La mouche volera donc durant une heure à 25 km/h : elle aura donc parcouru 25 kms.

Facile, certes, du moins quand on y pense: on peut alors répondre en quelques secondes. Mais si on n’y pense pas, on peut être tenté de sommer des séries , ce qui est terriblement compliqué et long. L’histoire (une légende urbaine? qui sait?  mais il était tellement génial…) sur John Von Neuman est que quand on lui posa ce problème, il mit tout de même, étrangement, plusieurs secondes avant donner la bonne réponse. Interrogé, il avoua … avoir additionné des séries pour la trouver! (Si quelqu’un a une source qui authentifierait cette histoire, je suis preneur…)

2. Il y a seize possibilités (G= Garçon et F= Fille). Ce sont :

GGGG

GGGF

GGFG

GGFF

GFGG

GFGF

GFFG

GFFF

FGGG

FGGF

FGFG

FGFF

FFGG

FFGF

FFFG

FFFF

Dans huit cas sur seize, la proportion est 3 – 1 : ce qui est donc la distribution la plus probable.