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é.