Damier

Énoncé

Soit un damier de dimensions 10×10 auquel on a retiré la case du coin supérieur droit et celle du coin inférieur gauche. Est-il possible de couvrir le damier avec des dominos de dimensions 2×1 ?

Solution

Considérons que le damier est colorié comme c'est généralement le cas : une case sur deux est noire, et l'autre est blanche. Les deux cases du coin supérieur droit et du coin inférieur gauche sont de la même couleur (ici, noire). Après les avoir retirées, le damier comporte donc 48 cases noires et 50 cases blanches. Or, un domino recouvre nécessairement deux cases de couleurs différentes. Il n'est donc pas possible de recouvrir toutes les cases restantes avec des dominos.

Le même argument aurait fonctionné pour tout damier auquel on aurait retiré 2 cases de même couleur. À l'inverse, si l'on retire 2 cases de couleurs différentes, il est toujours possible de couvrir le reste du damier avec des dominos. Ce résultat est appelé théorème de Gomory (1973).

À l'aveugle

Énoncé

Vous avez les yeux bandés. On vous donne un paquet de 52 cartes dont 23 ont leur face vers le haut. Vous le savez, mais vous ne savez pas où sont les 23 cartes dans le paquet. Sans vous débander les yeux, vous devez séparer le paquet en deux sous-paquets dont chacun a le même nombre de cartes face vers le haut. Vous avez pour cela le droit de retourner autant de cartes que vous le souhaitez.

Solution

La solution consiste à prendre les 23 premières cartes du paquet (ou bien 23 autres) pour former un premier sous-paquet, noté A, et à retourner ce sous-paquet. Vous obtenez en tout 2 sous-paquets, A et B. Prouvons qu'ils ont le même nombre de cartes face vers le haut. Soit x le nombre de cartes face vers le haut dans le paquet A avant retournement. Le reste du paquet, B, contient 23−x cartes face vers le haut. Lorsqu'on retourne le paquet A, celui ne contient plus x cartes face vers le haut mais 23−x cartes face vers le haut (puisque A contient en tout 23 cartes). A et B ont donc le même nombre de cartes face vers le haut.

La mouche et les deux trains

Énoncé

Deux villes distantes de 100 km sont reliées par une voie de chemin de fer à double sens. Deux trains voyageant à 10 km/h quittent chacune des deux villes en direction de l'autre. Une mouche volant à 15 km/h commence alors un aller-retour ininterrompu entre ces deux trains. Quelle distance aura parcouru la mouche au moment où les deux trains vont se croiser ?

Solution

Les trains vont parcourir chacun 50 km avant de se croiser. Ils se croiseront donc au bout de 5 heures. Durant ce temps, la mouche aura volé 5×15=75 km.

Loups et moutons

Énoncé

Il y a 99 loups et 1 mouton. Tout loup veut manger le mouton, mais s'il le mange il se transforme lui-même en mouton, et risque donc d'être mangé à son tour. Les loups ne veulent pas mourir : ils ne vont donc pas manger le mouton s'ils savent qu'ils vont être mangés ensuite. Tous les loups adoptent la meilleure stratégie. Le mouton est-il mangé ?

Solution

S'il n'y avait que n=1 loup, le loup mangerait le mouton, car il saurait qu'il ne serait pas mangé ensuite. S'il y avait n=2 loups, aucun ne mangerait le mouton. En effet, si un loup mangeait le mouton, il se transformerait en mouton et serait mangé par le seul loup restant (cas n=1). S'il y avait n=3 loups, un loup mangerait le mouton. En effet, il se transformerait alors en mouton, mais il ne resterait alors que 2 loups. Et on sait que lorsqu'il n'y a que 2 loups et 1 mouton, personne ne mange le mouton (cas n=2). De façon générale, on s'aperçoit que le mouton est mangé lorsque n est impair et qu'il n'est pas mangé lorsque n est pair. Ici, pour n=99, le mouton est mangé.

Poignées de main

Énoncé

13 vieux amis se réunissent à l'occasion d'une soirée. Au début de celle-ci, certains se serrent la main, mais tout le monde n'a pas serré la main à tout le monde. Prouver qu'il y a 2 personnes qui ont serré la main au même nombre de personnes.

Solution

La réponse est une application du principe des tiroirs. Chaque invité de la soirée a serré la main à entre 0 et 12 personnes : cela fait 13 possibilités. Pour que chacun des 13 invités serre la main à un nombre différent de personnes, il faudrait que toutes ces possibilités soient exploitées. Or s'il y a un invité X qui a serré la main à 12 personnes, c'est-à-dire à tous les autres, alors personne n'a serré la main à 0 personnes, car tout le monde a serré la main à X.

Chapeaux rouges et bleus

Énoncé

100 nains sont en file indienne. Chaque nain porte un chapeau, de couleur rouge ou bleue, mais ne le voit pas. Il peut cependant voir les chapeaux de tous les nains devant lui dans la file. Le défi est le suivant : chacun leur tour, et en partant du dernier nain, les nains vont devoir deviner la couleur de leur chapeau et la dire à voie haute. Ils peuvent, avant la pose des chapeaux, se concerter sur une stratégie. Quelle stratégie peuvent-ils adopter pour qu'au moins 99 d'entre eux devinent correctement la couleur de leur chapeau ?

Solution

Puisqu'il faut qu'au moins 99 des nains devinent correctement la couleur de leurs chapeaux, on devine facilement que c'est le premier nain à s'exprimer qui peut se tromper. Ce nain est cependant crucial : c'est lui qui va donner suffisamment d'information pour que tous les autres nains puissent deviner la couleur de leur chapeau. La stratégie est la suivante : le premier nain va dire « bleu » si le nombre de chapeaux bleus parmi les 99 nains devant lui est pair, « rouge » sinon. Entendant cela, le deuxième nain va à son tour compter le nombre de chapeaux bleus parmi les 98 nains devant lui. Si celui-ci a la même parité que pour le premier nain, alors le nombre de chapeaux bleus n'a pas varié et le chapeau du deuxième nain est rouge. Sinon, puisque le nombre de chapeaux bleus a varié, c'est que le chapeau du deuxième nain est bleu. Le deuxième nain peut donc deviner correctement la couleur de son chapeau. Puis, ayant entendu l'information donnée par le premier nain et la couleur du chapeau du deuxième nain, le troisième nain va pouvoir connaître la parité du nombre de chapeaux bleus parmi lui et les 97 nains devant lui : il s'agira de celle indiquée par le premier nain si le deuxième nain avait un chapeau rouge, et son inverse sinon. Il va donc à son tour pouvoir deviner la couleur de son chapeau. De façon générale, le n-ème nain va pouvoir deviner la couleur de son chapeau. Et ainsi de suite.

Fourmis

Énoncé

100 fourmis, que l'on modélise comme des points, se déplacent sur un fil d'un mètre de long, à raison d'un mètre par heure. Lorsque deux fourmis se rencontrent, chacune repart dans le sens d'où elle venait. Lorsqu'une fourmi arrive au bord du fil, elle tombe dans le vide. Montrer qu'au bout d'une heure, toutes les fourmis sont tombées du fil.

Solution

L'astuce consiste à remarquer que tout se passe comme ci les fourmis se traversaient lorsqu'elles se rencontraient. Pour le voir, attachons à chaque fourmi un ballon d'une certaine couleur, et disons que les fourmis s'échangent le ballon lorsqu'elles se rencontrent. Alors les ballons vont en ligne droite, et vont aussi à un mètre par heure. En une heure, tous les ballons sont donc tombés, et les fourmis avec.

Combien ?

Énoncé

Le long d'une ligne, m balles arrivent de la gauche en se déplaçant vers la droite et n autres arrivent de la droite en se déplaçant vers la gauche. Les collisions sont élastiques. Combien va-t-il y avoir de collisions ?

Solution

L'effet d'une collision sur la distribution des positions et des vitesses des balles n'a aucune influence. En effet, deux balles qui rebondissent l'une contre l'autre aboutit à la même « vidéo » que deux balles qui se traversent (au rayon des balles près). Or, dans une situation où toutes les balles se traverseraient, il y aurait m×n contacts. Il s'agit donc de la solution cherchée ici.

Une ivresse mortelle

Énoncé

Il y a 10 rats et 1000 bouteilles de vin dont une empoisonnée. Si un rat boit de la bouteille empoisonnée, il meurt au bout d’une heure. Votre but est de déterminer quelle est la bouteille empoisonnée en donnant aux rats à boire des bouteilles de vin selon la combinaison que vous souhaitez puis en constatant quels sont les rats morts au bout d’une heure. Comment faites-vous ?

Solution

L'idée ici est de faire correspondre une bouteille de vin avec un sous-ensemble des 10 rats. En effet, il y a 10 rats donc 2^10=1024 sous-ensembles possibles de rats, donc plus que le nombre de bouteilles. En pratique, on numérote les rats de 1 à 10, et les bouteilles de 1 à 1000, puis pour la bouteille numéro k, on écrit k en écriture binaire ; comme k est inférieur à 2^10, son écriture binaire comportera au maximum 10 chiffres et s’écrira donc a_1, a_2,…, a_10, avec a_p valant 0 ou 1. Puis pour chaque entier p entre 1 et 10, on donnera à boire de la bouteille k au rat numéro p si a_p=1. À la fin, on constate quels sont les rats morts, et on trouve ainsi l’écriture binaire associée : b_1, b_2…b_10, avec b_p=1 si le rat p est mort et 0 sinon, puis on convertit ce nombre en base décimale et on trouve ainsi la bouteille empoisonnée.

Prisonniers

Énoncé

100 prisonniers sont chacun dans leur cellule, surveillés par le gardien de la prison. Parfois, le gardien appelle un prisonnier au hasard, l'emmène dans une salle secrète, puis le raccompagne à sa cellule. La salle secrète contient une lumière, qui est éteinte au début. Un prisonnier entrant dans la salle secrète a le droit d'allumer ou d'éteindre la lumière. Quelle stratégie les prisonniers peuvent-ils établir pour que, à un moment donné, un prisonnier comprenne que tous les prisonniers sont passés dans la salle secrète ? Les prisonniers ont le droit de communiquer pour établir leur stratégie au début, mais plus quand le jeu commence.

Solution

La stratégie consiste à donner à un prisonnier le rôle de compteur. Les autres prisonniers se signalent à lui en allumant la lumière. Plus précisément, lorsqu'un prisonnier qui n'est pas compteur arrive dans la salle secrète, s'il trouve la lumière éteinte et qu'il ne l'a encore jamais allumée, alors il l'allume. Le compteur, lui, lorsqu'il trouve la lumière allumée, l'éteint et retient qu'il y a un nain en plus qui est passé dans la salle. C'est finalement le compteur qui finit par comprendre que tous les prisonniers sont passés dans la salle secrète.

Ampoules

Énoncé

100 ampoules sont numérotées de 1 à 100 et ont chacune un interrupteur. Elles sont éteintes au début. 100 électriciens, numérotés eux aussi de 1 à 100, viennent faire des réparations. L'électricien numéro j appuie sur l'interrupteur des ampoules dont le numéro est un multiple de j : j, 2j, 3j... Combien d'ampoules sont allumées à la fin ?

Solution

L'ampoule numéro i est modifiée par chaque électricien ayant un numéro j qui divise i. Or, tout nombre entier qui n'est pas un carré a un nombre pair de diviseurs : en effet, si k est un diviseur de i alors i/k en est un autre, et les diviseurs peuvent ainsi être divisés en deux groupes de même taille. Ce raisonnement ne s'applique pas lorsque i=a², car alors a et i/a=a sont les mêmes nombres. Lorsque i n'est pas un carré, l'ampoule i est donc modifiée un nombre pair de fois et elle est éteinte à la fin. Lorsque i est un carré, elle est modifiée un nombre impair de fois et est allumée à la fin. Comme il y a 10 carrés entre 1 et 100 (1, 4, 9, 16, ..., 100), il y a 10 ampoules allumées à la fin.

Tournoi de tennis

Énoncé

Un tournoi de tennis en simple est organisé avec 3000 participants. Il se déroule par élimination directe (à chaque tour, si le nombre de joueurs est impair, un joueur est qualifié automatiquement pour le prochain tour). Combien de matchs seront joués pour désigner le gagnant ?

Solution

Chaque match permet d’éliminer 1 participant, or il y a 2999 participants éliminés, donc 2999 matchs sont joués.

Nez violets

Énoncé

Dans un village, un jour, le nez de certains villageois devient violet. Les villageois ne savent pas combien d'entre eux ont été touchés, mais ils savent qu'il y a au moins une victime. Ils ne peuvent pas voir leur propre nez, mais ils voient le nez de leurs concitoyens. Un villageois qui apprend que son nez est violet quitte le village pendant la nuit, par honte de sa différence. Le maire constate qu'aucun villageois n'est parti la première nuit. Ni la deuxième. Pendant une semaine, aucun villageois ne part. La septième nuit, tous les villageois qui étaient violets fuient le village. Combien y'avait-il de villageois violets ?

Solution

S'il n'y avait qu'un villageois au nez violet, alors celui-ci ne verrait aucun autre villageois avec le nez violet, et pourtant il saurait qu'il y a au moins un villageois qui a le nez violet. Il pourrait donc en conclure qu'il a le nez violet et il quitterait le village dès la première nuit. Comme il ne se passe rien la première nuit, il y a au moins deux villageois qui ont le nez violet, et tous les villageois en sont conscients. Le deuxième jour, si un villageois ne voit qu'un autre villageois au nez violet, il sait donc qu'il a lui aussi le nez violet. Comme il ne se passe rien la deuxième nuit, il y a au moins trois villageois qui ont le nez violet. Le même raisonnement se poursuit jusqu'au septième jour. On en déduit qu'il y a sept villageois qui ont le nez violet.

Salaire moyen

Énoncé

3 amis de longue date se retrouvent et discutent de leurs emplois. Aucun d'entre eux ne veut dévoiler son salaire, mais ils aimeraient toutefois connaître la moyenne de leurs salaires. Ils ne peuvent pas utiliser d'aide externe, que ce soit une autre personne ou un objet. Comment faire ?

Solution

La solution repose sur un principe de cryptologie. La première personne va inventer un nombre x (la clé de cryptage), y ajouter son salaire s1, puis communiquer le résultat de la somme x+s1 à la deuxième personne (la troisième personne n'écoutant pas). Ensuite, la deuxième personne va ajouter son salaire s2 et va communiquer x+s1+s2 à la troisième personne. De même, la troisième personne ajoute s3 et communique x+s1+s2+s3 à la première personne. Enfin, la première personne soustrait la clé de cryptage x, qu'elle est la seule à connaître, et obtient s1+s2+s3. Elle peut alors faire connaître la moyenne des salaires (s1+s2+s3)/3 à tout le monde.

Lingot

Énoncé

Vous avez un lingot d'or de taille 7, et vous voulez vous en servir pour payer votre serviteur pendant une semaine, en le payant tous les jours de manière identique. Vous ne pouvez faire que 2 coupes sur le lingot. Comment faire ?

Solution

Le principe consiste à lui donner des bouts petits au début, puis à lui échanger contre des bouts un peu plus gros, puis à tout lui donner. Plus précisément, vous coupez le lingot en bouts de taille 1, 2 et 4. Le premier jour, vous lui donnez le bout de taille 1. Le deuxième, vous lui reprenez et vous lui donnez le bout de taille 2. Le troisième, vous lui donnez les bouts de taille 1 et 2. Le quatrième, vous lui reprenez tout et lui donnez le bout de taille 4. Le cinquième, vous lui donnez le bout de taille 1. Le sixième, vous lui reprenez le bout de taille 1 et vous lui donnez le bout de taille 2. Le septième et dernier jour, vous lui donnez le bout de taille 1.

Comptage de chambres

Énoncé

Vous êtes dans un hôtel circulaire comportant n chambres. Au début, certaines sont allumées et d'autres sont éteintes. Vous pouvez vous déplacer de chambre en chambre, et allumer ou éteindre la lumière. Vous n'avez aucun moyen de distinguer les chambres les unes des autres, si ce n'est en regardant si la lumière est allumée ou non. Comment trouver n ?

Solution

On démarre dans une certaine chambre, qu'on appelle le point de départ. L'idée consiste à se déplacer d'une chambre vers la droite, changer l'état de la lumière, puis revenir à son point de départ pour voir si l'état a changé. Si oui, alors n=1 et on peut s'arrêter. Sinon, on répète le processus en se déplaçant de 2 chambres vers la droite. Si lorsqu'on revient au point de départ, l'état a changé, alors n=2 et on peut s'arrêter. Et on continue ainsi jusqu'à trouver n.

Simulation de pièce de monnaie

Énoncé

Vous diposez d'un générateur aléatoire de nombre réels dont la distribution de probabilité est fixée mais inconnue. Servez-vous en pour construire un simulateur de pièce de monnaie, c'est-à-dire une machine qui renvoie Pile avec probabilité 1/2 et Face avec probabilité 1/2.

Solution

Pour simuler une pièce de monnaie, il suffit de tirer deux nombres grâce au générateur dont nous disposons. Si le premier est inférieur au second, on renvoie Pile ; sinon, on renvoie Face. Il y a bel et bien une chance sur deux que le premier nombre soit inférieur au second, car les deux tirages se font suivant la même distribution de probabilité.