Petits arrangements

Regroupements par paires

Piste bleue Le 26 avril 2016  - Ecrit par  Equipe de la rubrique « En sortant de l’école » Voir les commentaires (8)

Beaucoup de problèmes mathématiques peuvent être résolus à l’aide d’un partage astucieux des éléments de l’ensemble étudié en plusieurs parties. La série de trois articles que nous vous proposons est consacrée à cette idée importante. Le premier article porte sur des partages très simples : les regroupements par paires.
Dans un deuxième article, nous verrons que le regroupement par paires peut être utilisé pour comparer le nombre d’éléments de deux ensembles.
Enfin dans un troisième article, nous utiliserons des arrangements d’objets en groupes qui ne sont pas forcément des paires.

Les solutions des problèmes de l’article sont dans des blocs dépliants,
pour vous donner la possibilité d’essayer de résoudre ces problèmes
vous-mêmes.
Il est fortement conseillé de lire les solutions
avant de poursuivre la lecture de l’article.

(Rediffusion d’un article publié le 8 mai 2013).


Problème 1. Dominos sur un échiquier

Peut-on recouvrir un échiquier de
9 × 9 cases par des dominos en sorte que chaque domino couvre deux cases et que les dominos ne se chevauchent pas ?

Solution (à lire avant de poursuivre la lecture de l’article).

Non, ceci est impossible. En effet, supposons que l’on ait réussi à recouvrir l’échiquier 9 × 9 par des dominos de la façon demandée. Chaque domino couvrant deux cases, les cases de l’échiquier se trouvent regroupées par paires. Ceci implique que le nombre total de cases de l’échiquier est pair. Or l’échiquier
9 × 9 contient 81 cases, et le nombre 81 est impair. Cette contradiction montre que l’on ne peut pas recouvrir l’échiquier 9 × 9 par des dominos de la façon demandée.


L’observation principale utilisée dans la solution du problème 1 est la suivante : si certains objets peuvent être regroupés par paires, alors le nombre d’objets considérés est pair. Cette idée nous aidera à résoudre aussi le problème suivant.

Problème 2. Un carré parfait

La petite sœur de Laure a choisi un nombre entier strictement positif $N$ et a fait une liste de tous ses diviseurs positifs (y compris 1 et $N$). Elle dit à Laure que le nombre de diviseurs positifs de $N$ est impair. Laure affirme alors que
le nombre $N$ est forcément le carré d’un nombre entier.
Laure a-t-elle nécessairement raison ?

Solution (à lire avant de poursuivre la lecture de l’article).

Oui, Laure a raison. Regroupons chaque diviseur positif $d$ de $N$ avec le diviseur
$N/d$. En général, ces deux diviseurs $d$ et $N/d$ sont distincts, mais si $N = d^2$, ils sont confondus. Ainsi, si $N$ n’est pas un carré parfait, tous ses diviseurs positifs sont regroupés par paires. Par contre, si $N$ est un carré parfait, alors tous ses diviseurs positifs sont regroupés par paires sauf un : la racine carrée de $N$. Donc, le nombre de diviseurs positifs de $N$ est pair si $N$ n’est pas un carré parfait
et impair s’il en est un.


Essayez maintenant de résoudre encore deux problèmes en utilisant la même idée.

Problème 3. Les numéros chanceux

Le numéro d’un ticket est composé de 6 chiffres (il peut commencer par un ou plusieurs zéros). Un tel numéro est dit chanceux si la somme de ses trois premiers chiffres est égale à la somme de ses trois derniers chiffres. Montrez que le nombre de numéros chanceux est pair.

Solution.

Soit $R$ un numéro chanceux. En remplaçant chaque chiffre $r$ de $R$
par $9 - r$, on obtient un numéro $\overline R$.
Remarquons que le numéro $\overline R$ est également chanceux.
De plus, $\overline R$ est différent de $R$ (chaque chiffre de
$\overline R$ est différent du chiffre correspondant de $R$).
Donc les numéros chanceux peuvent être regroupés par paires
$(R,{\overline R})$. Par conséquent, le nombre de numéros chanceux est pair.

Problème 4. École de cuisine

Dans une école de cuisine, il y a 100 élèves. Tous les matins, le directeur de l’école désigne une équipe de trois élèves qui doit préparer le déjeuner pour toute l’école. À un certain moment, le directeur de l’école affirme que tout élève de l’école a fait équipe avec tout autre élève exactement une fois. Montrez que le directeur se trompe.

Solution.

Considérons un élève $E$ de l’école. S’il a fait équipe
avec tout autre élève exactement une fois, les autres élèves de l’école
peuvent être regroupés par paires, chaque paire étant formée
d’élèves $A$ et $B$ tels que les élèves $E$, $A$ et $B$
ont formé une équipe. Dans ce cas, le nombre d’autres élèves
doit être pair, or ce nombre est égal à $99$.
Cette contradiction montre que le directeur se trompe.


Passons maintenant à des problèmes un peu plus compliqués.

Problème 5. Une grande diagonale

La grande diagonale $D$ relie l’angle en bas à gauche à l’angle en haut à droite d’un tableau de 25 × 25 cases. Dans chaque case du tableau, on a placé un des nombres 1, 2, … , 25 de telle façon que :

  • deux cases quelconques symétriques par rapport à $D$ contiennent des nombres égaux ;
  • dans chaque ligne du tableau, tous les nombres soient deux à deux distincts.
    Montrez que tous les nombres placés dans les cases de la grande
    diagonale $D$ sont deux à deux distincts.

Solution (à lire avant de poursuivre la lecture de l’article).

Puisque, dans chaque ligne du tableau, tous les nombres sont deux à deux distincts, le tableau contient vingt-cinq nombres 1, vingt-cinq nombres 2, … , vingt-cinq nombres 25. Les nombres 1 placés dans le tableau en dehors de la grande diagonale $D$ peuvent être regroupés par paires : les deux nombres de chaque paire se trouvent dans des cases symétriques par rapport à $D$. Donc, la quantité de nombres 1 placés dans le tableau en dehors de $D$ est paire. Par conséquent, au moins un nombre 1 est placé dans une case de $D$.
De façon similaire, on montre que les cases de la grande diagonale $D$ contiennent au moins un nombre 2, au moins un nombre 3, … , au moins un nombre 25. Puisque la grande diagonale $D$ est formée de 25 cases, on voit que tous les nombres placés dans les cases de $D$ sont deux à deux distincts.


Remarquons que, dans la solution du problème 5, le regroupement par paires concerne seulement une partie des nombres placés dans le tableau (les nombres placés en dehors de la grande diagonale $D$). Voici encore quelques problèmes dont la solution utilise la même idée.

Problème 6. Des petits cubes

Plusieurs petits cubes de même taille sont collés entre eux. Tous les recollements se font entre faces entières de petits cubes. Est-ce que la surface de l’objet obtenu peut être composée de 2013 faces de petits cubes ?

Solution.

Notons $\; n$ le nombre de petits cubes. Le nombre total
de faces de ces cubes (avant le recollement) est égal à $\; 6n$.
En particulier, ce nombre est pair.
Les faces utilisées dans le recollement sont naturellement regroupées
par paires, chaque paire étant formée de deux faces recollées
l’une à l’autre.
Donc, le nombre de faces utilisées dans le recollement est pair.
Par conséquent, le nombre de faces sur le surface de l’objet obtenu
est, lui aussi, pair et ne peut être égal à 2013.

Problème 7. Vingt et un pions

Vingt et un pions sont placés dans certaines cases d’un damier de 9 × 9 cases (au plus un pion par case) de telle façon que l’ensemble des pions soit symétrique par rapport à chacune des deux diagonales du damier. Montrez qu’un pion est placé dans la case centrale du damier.

Solution.

Choisissons une diagonale $D_1$ du damier et montrons
que le nombre de pions sur cette diagonale est impair.
En effet, l’ensemble de tous les pions est symétrique par rapport à $D_1$.
Donc, les pions placés en dehors de $D_1$
peuvent être regroupés par paires : les deux pions de chaque paire se
trouvent dans des cases symétriques par rapport à $D_1$. Donc,
le nombre de pions
placés en dehors de $D_1$ est pair.
Puisque le nombre total de pions est impair, ceci implique
que le nombre de pions sur la diagonale $D_1$ est impair.
L’ensemble des pions est également symétrique par rapport à l’autre
diagonale $D_2$ du damier. Donc, l’ensemble des pions
placés sur $D_1$ est symétrique par rapport au centre du damier.
Cet ensemble étant formé d’un nombre impair de pions,
on obtient que l’un de ces pions doit se trouver dans la case centrale du damier.


L’idée de regroupement par paires peut aussi être utilisée dans d’autres contextes (pas forcément pour montrer que le nombre d’objets considérés est pair).

Problème 8. Des pièces de monnaie

Cent pièces de monnaie, parmi lesquelles il n’y a que des pièces de 1 ou 2 euros, sont alignées sur une table. La valeur totale de ces cent pièces est strictement supérieure à 150 euros. Montrez que, parmi ces pièces de monnaie, on peut trouver deux pièces voisines de 2 euros.

Solution (à lire avant de poursuivre la lecture de l’article).

Remarquons que la valeur totale des cent pièces de monnaie est égale à $100 + N$, où $N$ est le nombre de pièces de 2 euros dans notre collection. Puisque la valeur totale des cent pièces de monnaie est strictement supérieure à 150 euros,
on a $N > 50$.
Regroupons les cents pièces de monnaie en 50 paires :
la première pièce avec la deuxième, la troisième avec la quatrième,
et ainsi de suite.
Puisque $N > 50$, il existe au moins une paire
dont les deux pièces sont de 2 euros.

Problème 9. Une table pour cent personnes

Cent personnes sont assises et régulièrement réparties autour d’une table ronde. Parmi ces cent personnes, les femmes sont plus nombreuses que les hommes. Montrez que, à cette table, on peut trouver deux femmes assises l’une en face de l’autre.

Solution.

Regroupons par paires les cent personnes assises autour de la table :
chaque paire est formée de deux personnes assises l’une en face de l’autre.
Si aucune paire n’est formée de deux femmes, le nombre de femmes
assises autour de la table
est inférieur ou égal au nombre d’hommes à cette table,
ce qui contredit l’hypothèse.

Problème 10. Divisible par p

Soit $p$ un nombre premier strictement supérieur à 2. Soient $m$ et $n$ deux nombres entiers tels que
\[ \frac{m}{n} = 1 + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{p - 1}\;. \]
Montrer que le nombre $m$ est divisible par $p$.

Solution.

Le nombre $p$ est impair, donc le nombre de termes
dans la suite
\[ 1, \; \frac{1}{2}, \; \frac{1}{3}, \; \ldots \; \frac{1}{p - 1} \]
est pair.
Regroupons ces termes
par paires :
$1$ et $\frac{1}{p - 1}$, $\frac{1}{2}$ et $\frac{1}{p - 2}$ etc.
Dans chaque paire, la somme des deux nombres
est de la forme $\frac{p}{i(p - i)}$, où
$i$ est un nombre entier entre $1$ et $p - 1$.
Donc,
\[ \frac{m}{n} = \frac{pa}{1 \cdot 2 \cdot \ldots \cdot (p - 1)}, \]
où $a$ est un nombre entier.
Puisque $p$ est premier, le nombre $1 \cdot 2 \cdot \ldots \cdot (p - 1)$
n’est pas divisible par $p$.
Par conséquent, $m$ est divisible par $p$.


Dans la solution du problème suivant, à nouveau, le regroupement par paires ne concerne qu’une partie des objets considérés.

Problème 11. Encore des numéros chanceux

Montrez que la somme de tous les numéros chanceux (voir le problème 3) est divisible par 13.

Solution (à lire).

Nous dirons qu’un numéro chanceux est un doublon s’il est de la forme
\[ ABCABC, \]
où les lettres $A$, $B$ et $C$ désignent des chiffres (qui ne sont pas nécessairement deux à deux différents).
Remarquons que
\[ ABCABC = 1000 \times ABC + ABC = 1001 \times ABC. \]
Donc, chaque doublon est divisible par 1001. Puisque
\[ 1001 = 7 \times 11 \times 13, \]
ceci implique que chaque doublon est divisible par 13.

Un numéro chanceux qui n’est pas un doublon n’est pas forcément divisible par 13. Mais les numéros chanceux autres que les doublons peuvent être regroupés par paires :
\[ ABCDEF \]
forme une paire avec
\[ DEFABC. \]
Remarquons que
\[ ABCDEF + DEFABC = 1001(ABC + DEF). \]
Donc, dans chaque paire, la somme des deux numéros est divisible par 13.

Par conséquent, la somme de tous les numéros chanceux est divisible par 13.


Problèmes à résoudre par vous-mêmes

Problème 1. Un polygone symétrique

Considérons un polygone qui a 101 sommets et un axe de symétrie.
Montrez que cet axe passe par au moins un sommet du polygone
.

Problème 2. Divisible par 999

Montrez que la somme des numéros chanceux (voir les problèmes 3 et 11) est divisible par 999.

Problème 3. Trois diviseurs

Parmi les nombres entiers positifs ayant exactement trois diviseurs positifs chacun, trouvez le nombre le plus proche de 1000.

Problème 4. Tableau de 9 × 10 cases

Frédéric a mis les nombres entiers de 1 à 90 dans les cases d’un tableau rectangulaire composé de 9 lignes horizontales ayant chacune exactement 10 cases.
Chaque case du tableau contient un nombre, et chaque nombre entier entre 1 et 90 apparaît une fois dans le tableau. Frédéric affirme que deux cases quelconques
symétriques par rapport à l’axe de symétrie vertical du tableau contiennent des nombres de même parité. Montrez que Frédéric se trompe
.

Problème 5. Mille lampes

Dans un couloir d’école, il y a mille lampes numérotées de 1 à 1000 avec un interrupteur au-dessous de chaque lampe. Un beau matin, toutes les lampes sont allumées. Le premier élève passe alors par le couloir en appuyant sur tous les interrupteurs. Toutes les lampes sont donc éteintes après son passage. Ensuite, le deuxième élève passe en appuyant sur les interrupteurs ayant un numéro pair. Ainsi il rallume une lampe sur deux. Le troisième élève passe en appuyant sur les interrupteurs dont le numéro est divisible par 3, le quatrième appuie sur les interrupteurs dont le numéro est divisible par 4, etc. Combien de lampes sont-elles allumées après le passage du millième élève ?

Post-scriptum :

Les lecteurs sont invités à nous proposer leurs solutions des « Problèmes à résoudre par vous-mêmes ». Les solutions peuvent être rédigées comme commentaires sur l’article ou envoyées à l’adresse suivante :
ensortantdelecole images.math.cnrs.fr
Les meilleures solutions seront publiées dans la rubrique.

L’équipe de la rubrique remercie Nikita Itenberg pour les illustrations qu’il a faites pour cet article.

NDLR : Retrouvez les autres articles sur le sujet ici : II et III, et les autres articles de la rubrique : En sortant de l’école.

Partager cet article

Pour citer cet article :

Equipe de la rubrique « En sortant de l’école » — «Petits arrangements» — Images des Mathématiques, CNRS, 2016

Commentaire sur l'article

  • Petits arrangements

    le 13 mai 2013 à 00:10, par Michèle Audin

    Jolis problèmes, bravo.

    Pourquoi, la prochaine fois, ne pas mettre les solutions des problèmes dans des blocs dépliants ? Ça permettrait d’y réfléchir une seconde avant de voir la solution !

    Amicalement

    Michèle

    Répondre à ce message
  • un problème analogue

    le 21 mai 2013 à 06:03, par DAAMOUCH

    Bonjour,
    Je vous propose un problème dont la solution utilise la même idée :

    Peut-on recouvrir un échiquier de 8× 8 cases, sachant qu’on a éliminé la première case de la première ligne et la dernière case de la dernière ligne, par des dominos en sorte que chaque domino couvre deux cases et que les dominos ne se chevauchent pas ?

    Remarquons que la solution est difficile si on n’utilise pas les couleurs des cases.

    Merci

    Répondre à ce message
    • un problème analogue

      le 22 mai 2013 à 22:24, par Ilia Itenberg

      Merci beaucoup pour la proposition. Effectivement, ce problème est très proche du thème de l’article (et plus précisement, du thème de la deuxième partie de l’article ; cette deuxième partie sera mise en ligne au début du mois de juin).

      Répondre à ce message
  • Petits arrangements

    le 1er août 2013 à 14:52, par Tino

    Pour le problème 3, il y a une solution bien plus triviale, non ? je peux former les paires de nombres tel que : (123042 ;042123). il y donc forcément un nombre pair de nombres chanceux.

    Répondre à ce message
    • Petits arrangements

      le 4 septembre 2013 à 00:48, par Ilia Itenberg

      Le problème de ce raisonnement est le suivant : chaque nombre de la forme abcabc n’est regroupé avec aucun autre nombre.

      Répondre à ce message
  • Proposition de solution au problème n°5

    le 1er mai à 21:56, par QuentinC

    L’élève k appuie sur l’interrupteur de la lampe n si et seulement si n est un multiple de k, ou autrement dit si n est divisible par k.
    Donc, la lampe n change d’état autant de fois que n a de diviseurs.

    Appuyer un nombre pair de fois sur un interrupteur ne change pas l’état final de la lampe. Les lampes qui sont éteintes à la fin sont donc celles qui ont été basculées un nombre impair de fois.
    ON sait qu’un nombre n ne peut avoir un nombre impair de diviseur que si et seulement si c’est un carré parfait (merci pour le rappel, cf. problème 2)

    Par conséquent la lampe n est éteinte si n est un carré parfait, et allumée sinon.

    Il existe exactement ceil(sqrt(n)) carrés parfaits <= n (le nombre 1 compte aussi comme carré parfait).
    Soit donc 32 carrés parfaits jusqu’à 1000.

    Il y a donc 32 lampes éteintes et 968 lampes allumées.

    Répondre à ce message
    • Proposition de solution au problème n°5

      le 3 mai à 10:56, par Sébastien Kernivinen

      Bonjour Quentin,
      Vous n’êtes pas très loin d’un résultat correct ; il y a une (petite) erreur dans votre réponse.
      Le nombre de carrés parfaits inférieurs ou égal à $n$ est la partie entière de $\sqrt n$ ce qu’on peut noter $\left\lfloor {\sqrt n } \right\rfloor $.
      En tenant compte de cette remarque, la réponse obtenue est : « 969 lampes allumées ».

      Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM