Petits arrangements 3

Des groupes plus grands

Piste bleue 16 juillet 2013  - Ecrit par  Equipe de la rubrique « En sortant de l’école » Voir les commentaires (2)

Dans les problèmes des deux articles précédents (I et II) nous avons parlé de regroupements par paires. Dans cet article, nous allons utiliser des arrangements d’objets en groupes qui ne sont pas forcément des paires.

Les solutions des problèmes clés 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. Les solutions des autres problèmes ne sont données qu’une quinzaine de jours après la parution de l’article pour vous laisser le temps de les chercher.


Problème 1. Dix nombres

Dix nombres dont la somme est égale à 100 sont placés sur un cercle. La somme de trois nombres consécutifs quelconques parmi ces dix nombres est supérieure ou égale à 28. Montrez que les dix nombres placés sur le cercle sont tous inférieurs ou égaux à 16.

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

Choisissons un des dix nombres placés sur le cercle
et notons $\ a$ ce nombre. Les neuf nombres restant peuvent être divisés en trois groupes de telle façon que chaque groupe soit composé de trois nombres consécutifs sur le cercle. La somme des nombres dans chaque groupe est supérieure ou égale à 28. Donc,
\[ a \leq 100 \ – 3 × 28 = 16. \]
Par conséquent, chacun des dix nombres placés sur le cercle est inférieur ou égal à 16.


Dans la solution du problème 1, nous avons considéré des groupes formés de trois éléments chacun. Pour résoudre les trois problèmes suivants, nous aurons
affaire à des groupes de quatre éléments.

Problème 2. Une feuille à petits carreaux

Une feuille carrée à petits carreaux (la longueur des côtés des carreaux
est égale à 1) est découpée en un certain nombre de carrés dont les côtés font partie du quadrillage. Montrez que la longueur totale des lignes
du découpage est divisible par 4
.

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

Considérons un carré quelconque $\ Q$ quadrillé en carreaux dont la longueur des côtés est égale à 1 et notons $\ l(Q)$ la longueur totale des côtés des petits carreaux
du quadrillage du carré $\ Q$,
sauf des côtés de ce quadrillage qui constituent le bord de $\ Q$.
Montrons que $\ l(Q)$ est divisible par 4. En effet, les côtés
ne se trouvant pas
sur le bord de $\ Q$ peuvent être partagés en groupes de quatre, chaque groupe étant formé d’un côté et de ses trois images par les trois rotations
autour du centre de $\; Q$ d’un quart, un demi et trois-quarts de
tour.
La somme des longueurs des côtés dans chaque groupe est égale à 4.
Donc, $\ l(Q)$ est divisible par 4.

Notons $P$ notre feuille carrée
et notons
\[ P_1, P_2, \ldots, P_n \]
les carrés du découpage. La longueur totale des lignes du découpage est égale à
\[ l(P) – l(P_1) – l(P_2) – \ldots – l(P_n). \]
Puisque chacun des nombres
$\; l(P)$, $l(P_1)$, $l(P_2)$, $\ldots$, $l(P_n)$ est divisible par 4,
la longueur totale des lignes du découpage est aussi divisible par 4.

Problème 3. Douze nombres

Considérons douze nombres réels $x_1, x_2, \ldots, x_{12}$ tels que
\[ \displaylines{ x_2(x_1 – x_2 + x_3) < 0, \cr x_3(x_2 – x_3 + x_4) < 0, \cr \ldots \cr x_{11}(x_{10} – x_{11} + x_{12}) < 0. } \]
Montrez que, parmi ces douze nombres,
trois au moins sont
strictement négatifs
.

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

Partageons les douze nombres $x_1, x_2, \ldots, x_{12}$
en trois groupes de quatre nombres chacun :
\[ \displaylines{ x_1, x_2, x_3, x_4, \cr x_5, x_6, x_7, x_8, \cr x_9, x_{10}, x_{11}, x_{12}. } \]
Montrons que chacun de ces trois groupes contient au moins un nombre strictement négatif. Supposons que tous les nombres
\[ x_1, x_2, x_3, x_4 \]
soient positifs ou nuls. On a
\[ x_2 \geq 0 \; \text{et} \; x_2(x_1 – x_2 + x_3) < 0, \]
d’où
\[ x_1 + x_3 < x_2. \]
De même, les inégalités
\[ x_3 \geq 0 \; \text{et} \; x_3(x_2 – x_3 + x_4)<0 \]
impliquent l’inégalité
\[ x_2 + x_4 < x_3. \]
La somme des deux inégalités obtenues donne
\[ x_1 + x_4 < 0. \]
Cette contradiction montre que, parmi les nombres
\[ x_1, x_2, x_3, x_4, \]
il y a au moins un nombre strictement négatif.

De façon similaire, parmi les nombres
\[ x_5, x_6, x_7, x_8, \]
il y a au moins un nombre strictement négatif et, parmi les nombres
\[ x_9, x_{10}, x_{11}, x_{12}, \]
il y a aussi au moins un nombre strictement négatif. Par conséquent, parmi nos douze nombres, il y a au moins trois nombres strictement négatifs.

Problème 4. Des rois sur l’échiquier

Combien de rois au maximum peut-on placer sur l’échiquier
de $8 \times 8$ cases de telle façon qu’aucun roi ne puisse prendre
un autre ? (Un roi peut en prendre un autre si les deux rois
se trouvent dans des cases
ayant un côté ou un sommet en commun.)

Solution

La réponse est $16$.

Il est facile de placer $\;16$ rois sur l’échiquier
de la façon demandée. Pour cela, partageons les $\;64$ cases de l’échiquier en $\;16$ groupes de $\;4$ cases formant des carrés $\; 2 \times 2$ cases. On peut alors placer un roi
dans le coin en haut à gauche de chacun de ces $\;16$ carrés
$\;2 \times 2$.

Supposons maintenant que l’on ait placé au moins $\;17$ rois
sur l’échiquier en sorte qu’aucun ne puisse en prendre
un autre. Parmi ces rois, au moins deux se trouvent dans un même carré
$\;2 \times 2$, puisque l’échiquier est partagé en $\;16$ carrés.
Mais deux cases quelconques appartenant au même carré
$\;2 \times 2$ ont un côté ou un sommet en commun.
Cette contradiction montre qu’il est impossible de placer plus de $\;16$ rois en respectant les conditions.


Dans les solutions des problèmes suivants, nous considérerons des groupes plus grands.

Problème 5. Un 15-gone régulier

Sept sommets d’un 15-gone régulier sont coloriés en vert. Montrez que, parmi ces sept sommets verts, on peut en choisir trois qui forment les sommets d’un triangle isocèle.

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

Partageons les 15 sommets du 15-gone régulier en trois groupes de 5 sommets de telle façon que les sommets de chaque groupe forment les sommets d’un pentagone régulier. Parmi les sept sommets verts, au moins trois sommets appartiennent au même groupe. Il reste à remarquer que trois sommets quelconques d’un pentagone régulier forment les sommets d’un triangle isocèle.

Problème 6. Mille et un nombres

On a mille et un nombres entiers strictement positifs qui vérifient la propriété suivante : pour tout nombre entier $\; i$ entre 2 et 20, la somme de $\; i$ nombres quelconques parmi nos mille et un nombres est divisible par $\; i$. Montrez que la somme des mille et un nombres est divisible par 1001.

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

On a
\[ 1001 = 7 \times 11 \times 13. \]
Montrons que la somme de tous nos nombres est divisible par 7. Regroupons nos nombres en groupes de 7 nombres chacun. La somme des nombres dans chaque groupe est divisible par 7, donc la somme des mille et un nombres est aussi divisible par 7. De façon similaire, on montre que cette somme est divisible par 11 et 13. Par conséquent, la somme étudiée est divisible par
$\ 7 \times 11 \times 13$, c’est-à-dire par 1001.


Souvent, on partage des objets en groupes qui n’ont pas tous le même nombre d’objets. En fait, nous avons déjà considéré des partages « non équitables » ; par exemple, dans la solution du problème 1, on a partagé les dix nombres en quatre groupes : un groupe d’un nombre et trois groupes de trois nombres. Dans la solution du problème suivant, on aura affaire à deux groupes ayant des nombres différents d’éléments.

Problème 7. L’histoire de signes

Dans la case qui se trouve en bas à gauche d’un tableau de $3 \times 3$ cases,
on a placé le nombre $–1$. Dans chacune des huit autres cases de ce tableau, on a placé le nombre $\; 1$.
On peut choisir une ligne, une colonne ou une grande diagonale du tableau et changer le signe de chaque nombre qui se trouve dans la ligne, la colonne ou la grande diagonale choisie. Peut-on, en répétant l’opération autorisée plusieurs fois, obtenir neuf nombres $\; 1$ dans le tableau ?

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

Partageons les neuf cases du tableau en deux groupes : le premier groupe formé des quatre cases qui se trouvent aux coins du tableau et le deuxième groupe formé des cinq autres cases.

Chaque opération autorisée soit ne change pas les signes des nombres qui se trouvent dans les cases du premier groupe, soit change les signes d’exactement deux nombres qui se trouvent dans les cases du premier groupe. Donc, les opérations autorisées ne changent pas la parité du nombre de $–1$ dans les cases du premier groupe.
Au départ, les cases du premier groupe contiennent un nombre $–1$
et trois nombres $\; 1$. Par conséquent, à tout moment des opérations, on aura
au moins un nombre $–1$ dans les cases du premier groupe.
Il est donc impossible, en utilisant les opérations autorisées,
d’obtenir neuf nombres $\; 1$ dans le tableau.


L’idée de la solution du problème 7 est très proche de l’idée de coloriage :
souvent, pour résoudre des problèmes concernant des tableaux,
il est utile de colorier les cases en plusieurs couleurs.

Problème 8. Une seule lettre L

Peut-on découper l’échiquier de $9 \times 9$ cases en une figure
de 3 cases formant la lettre $L$ (voir le dessin ci-dessous) et plusieurs figures
de la forme d’un le rectangle de $1 \times 3$ ?

Solution

Non, un tel découpage n’existe pas.
Supposons que l’on ait découpé l’échiquier $\; 9 \times 9$ de la façon demandée. Notons $L$ la seule figure non rectangulaire du découpage.
Parmi les trois cases de $L$,
il y a deux cases qui n’ont pas de côté commun ; notons-les $\; a$ et $\; b$.
La droite reliant les centres de $\; a$ et $\; b$ est parallèle
à une grande diagonale de l’échiquier ; notons $\; d$ cette diagonale.
Numérotons les diagonales parallèles à $\; d$ de façon consécutive
par des nombres entiers de $\;1$ à $\;17$.
(La première et la dernière de ces diagonales
sont constituée chacune d’une seule case.)
Pour chacune des $\;17$ diagonales, plaçons
dans toutes ses cases le reste de la division
par $\;3$ du numéro de la diagonale
(la seule case de la première diagonale contient un $\;1$,
les cases de la deuxième diagonale contiennent des $\;2$,
les cases de la troisième diagonale contiennent des $\;0$, etc).
Le dessin ci-dessous représente la situation où la diagonale $\; d$
relie le coin en haut à gauche de l’échiquier avec le coin en bas à droite ;
dans ce cas,
les cases blanches contiennent des $\; 0$, les cases jaunes contiennent
des $\; 1$ et les cases rouges contiennent des $\; 2$.

Dans chaque colonne de l’échiquier, il y a trois cases
contenant des $\;0$, trois cases contenant des $\;1$ et trois cases contenant des $\;2$. Il y a donc au total autant de $\;0$ de $\;1$ et de $\;2$ sur l’échiquier. De plus, chaque figure rectangulaire du découpage a
une case contenant un $\;0$, une case contenant un $\;1$ et une case contenant un $\;2$.
Par conséquent, la figure $L$ doit aussi avoir
une case contenant un $\;0$, une case contenant un $\;1$ et une case contenant un $\;2$.
Mais, les nombres dans les cases $\; a$ et $\; b$ sont égaux !
Cette contradiction montre que l’on ne peut pas découper
l’échiquier de $\; 9 \times 9$ cases de la façon demandée.


Voici encore un problème dont la solution utilise
un partage non équilibré.

Problème 9. Dix-sept poids

Une collection de dix-sept poids vérifie la propriété suivante : chaque poids de la collection pèse un nombre entier de grammes qui est inférieur ou égal à 30. On a une balance à fléau et on peut mettre un ou plusieurs poids de la collection seulement sur un plateau de la balance. Montrez que, à l’aide de ces dix-sept poids, on peut peser au plus 468 poids différents.

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

Séparons toutes les collections que l’on peut former avec nos dix-sept poids en deux groupes : le premier groupe est constitué des collections ayant au plus 15 poids chacune, le deuxième groupe est constitué des autres collections.

Pour chaque collection du premier groupe, le poids total (en grammes) de la collection est un nombre entier entre $\; 1$ et $\; 15 \times 30$.
Donc, les collections du premier groupe permettent de peser au plus 450 poids différents.

Le deuxième groupe consiste en 17 collections de 16 poids chacune et une collection de 17 poids. Donc, les collections du deuxième groupe permettent de peser au plus 18 poids différents.

Par conséquent, à l’aide de nos dix-sept poids, on peut peser au plus 468 poids différents.


Dans la solution du dernier problème de l’article, nous allons former des groupes deux fois.

Problème 10. Trois, quatre ou sept

Parmi les nombres entiers 1, 2, … , 100, on a choisi 31 nombres. Montrez que, parmi les nombres choisis, on peut en trouver deux qui diffèrent de 3, 4 ou 7.

Solution (à lire).

Montrons d’abord l’énoncé suivant :
si, parmi 10 nombres entiers consécutifs, on a choisi plusieurs nombres de telle façon que jamais deux d’entre eux ne diffèrent de 3, 4 ou 7, alors on a choisi au plus 3 nombres. En effet, considérons 10 nombres entiers consécutifs
\[ n, n + 1, n + 2, n + 3, n + 4, n + 5, n + 6, n + 7, n + 8, n + 9, \]
et supposons que, parmi ces nombres, on ait choisi au moins quatre nombres de telle façon que jamais deux d’entre eux ne diffèrent de 3, 4 ou 7. Partageons nos 10 nombres en quatre groupes :
\[ \displaylines{ n, n + 3, n + 7, \cr n + 1, n + 4, n + 8, \cr n + 2, n + 5, n + 9, \cr n + 6. } \]
Chaque groupe ne peut contenir qu’un seul des nombres choisis. Donc, exactement 4 nombres ont été choisis (un nombre par groupe) et le nombre $\; n + 6$ se trouve parmi eux.

Puisque le nombre $\; n + 6$ a été choisi,
le nombre choisi dans le troisième groupe est $\; n + 5$, car
\[ (n + 6) – (n + 2) = 4 \; \text{et} \; (n + 9 ) – (n + 6) = 3. \]

Ceci implique que le nombre choisi dans le deuxième groupe est $\; n + 4$, car
\[ (n + 5) – (n + 1) = 4 \; \text{et} \; (n + 8) – (n + 5) = 3. \]
Dans ce cas, aucun nombre du premier groupe n’a pas pu être choisi, car
\[ (n + 4) – n = 4, (n + 6) – (n + 3) = 3 \; \text{et} \; (n + 7) – (n + 4) = 3. \]
Cette contradiction montre que, si parmi 10 nombres entiers consécutifs, on a choisi plusieurs nombres de telle façon que jamais deux d’entre eux ne diffèrent de 3, 4 ou 7, alors on a choisi au plus 3 nombres.

Regroupons maintenant les nombres entiers 1, 2, … , 100 en dix groupes
(de 1 à 10, de 11 à 20, etc.), chaque groupe étant composé de dix nombres consécutifs. Puisque l’on a choisi 31 nombres, au moins quatre des nombres choisis se trouvent dans le même groupe. Donc, parmi les nombres choisis, il y en a deux qui diffèrent de 3, 4 ou 7.


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

Problème 1. Vingt-cinq nombres

On a 25 nombres. La somme de quatre nombres quelconques,
choisis parmi ceux-ci, est positive. Montrez que la somme
des 25 nombres est positive
.

Problème 2. En forme de T

Peut-on découper l’échiquier de $10 \times 10$ cases en figures
de 4 cases formant la lettre $T$ ?

Problème 3. Beaucoup de nouvelles

Dans un groupe de 100 élèves, chacun connaît une nouvelle
et toutes ces nouvelles sont différentes. Pendant une conversation
téléphonique, deux élèves peuvent parler de toutes les nouvelles
qu’ils connaissent au moment de la conversation. Montrez que l’on peut organiser
196 conversations téléphoniques de telle façon que, après ces conversations,
chacun des 100 élèves connaîtra toutes les cents nouvelles
.

Problème 4. Divisible par 1000

Dans une ligne, on a écrit 21 nombres entiers strictement positifs.
Montrez que l’on peut mettre des parenthèses et des signes
d’addition et de multiplication entre ces nombres
de telle façon que la valeur de l’expression
obtenue soit divisible par 1000
.

Problème 5. Quatre, cinq ou neuf

Parmi les nombres entiers 1, 2, … , 1200, on a choisi 372 nombres
de telle façon que jamais deux d’entre eux ne diffèrent de 4, 5 ou 9.
Montrez que le nombre 600 est parmi les nombres choisis
.

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 : I et II, 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 3» — Images des Mathématiques, CNRS, 2013

Commentaire sur l'article

  • Petits arrangements 3

    le 17 juillet 2013 à 11:53, par Bruno LANGLOIS

    Les lecteurs attentifs d’Images des Maths auront aperçu la solution au problème 2 dans cet article récent :)

    Répondre à ce message
  • Petits arrangements 3

    le 18 juillet 2013 à 15:34, par Bruno LANGLOIS

    J’avais lu trop rapidement l’énoncé du problème n°8 et ai cherché à répondre à la question suivante : peut-on découper l’échiquier de $9\times9$ cases en utilisant uniquement le $L$-triomino ?

    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