tirelire

Nous proposons ici des solutions de certains des problèmes d'optimisation proposés par ailleurs.

Mise en garde :

Il n'est pas nécessaire de connaître ces solutions pour poser les problèmes. Dans tous les cas, on peut se contenter de chercher une bonne disposition des nombres ou des points selon la règle proposée, sans chercher à prouver que la disposition obtenue est la meilleure possible.

Certains maîtres se sentiront tout de même plus à l'aise s'ils ont l'impression d'avoir fait le tour du problème avant de le proposer à leurs élèves.

On ne saurait trop insister cependant sur le fait que le questionnement introduit par les problèmes d'optimisation est plus important que la réponse finale.

Prenons l'exemple du problème n° 7, "les voisins multiples".

Quand une classe cherche ce problème, les élèves sont à plusieurs reprises convaincus d'avoir trouvé la meilleure réponse possible. Si un élève a réussi à obtenir 50 et que personne ne trouve mieux pendant quelques minutes, toute la classe est persuadée que 50 est le minimum. Quand un autre élève trouve 36 puis 30 ou 24, chacune de ces réponses est à son tour considérée comme la meilleure possible… Le rôle du maître est alors de mettre en évidence le fait que la conviction d'avoir atteint l'optimum, bien que forte, a été démentie à chaque fois.

Il s'agit pour l'essentiel de faire comprendre la différence qu'il y a entre

  • "j'ai l'impression qu'il n'est pas possible de faire mieux parce que je n'y arrive pas" et
  • "je sais qu'il est impossible de faire mieux, je peux expliquer pourquoi".

Pour que cette différence soit bien comprise il est utile que certains des problèmes soient clos, la preuve étant au besoin énoncée par le maître, mais d'autres problèmes peuvent rester ouverts. Ceux qui sont clos peuvent l'être de façon différée, plusieurs jours ou semaines après la recherche.

Notons par ailleurs que les problèmes pour lesquels on aura prouvé que l'optimum est atteint n'ont a priori plus d'intérêt dans un fichier fond de classe. On peut tout de même les y laisser, cela donnera des indices sur le degré d'adhésion des élèves à la preuve proposée. Il n'est pas dit qu'on ne verra pas des élèves chercher à placer plus de 12 points dans un problème ou le maître pense avoir prouvé que c'est impossible.

Quand nous ne proposons pas de solution, c'est soit parce que nous ne la connaissons pas (problème "pas de carré") soit parce que nous ne savons pas l'exprimer de façon suffisamment élémentaire (problème "2000"). Les propositions de lecteurs seront accueillies avec gratitude ici

Pas trois points alignés.

solution1 solution2

Les deux figures ci-dessus montrent chacune dix points placés sur les intersections sans alignement de trois points.

 

Pour prouver qu'il est impossible de placer plus de 10 points, on peut s'appuyer sur la remarque suivante :

solution3

Le nombre total de points placés sur la grille s'obtient en ajoutant le nombre de points placés sur chaque ligne. Comme aucun des cinq nombres ne peut dépasser 2, la somme ne dépassera pas 10.

 

Remarque : pour des grilles nettement plus grandes ce problème n'est pas résolu à ce jour.

Pour en savoir plus.

Si on tient à expliquer cette preuve aux élèves, la présentation suivante peut être utile (et peut être reprise pour les autres problèmes ce qui contribue à montrer ce qu'ils ont en commun) :

On écrit au tableau des nombres représentant le nombre de points placés sur la grille.

On entoure en vert les nombres de points qu'on sait placer sans alignement de trois points.

On barre ensuite en rouge les nombres de points dont on sait qu'ils sont impossibles à réaliser : 26 parce qu'il n'y a que 25 intersections, 25 parce qu'il est clair que si toutes les intersections sont utilisées il y aura des alignements de 3 points.

solution4

Les valeurs 26 et 25 peuvent sembler simplistes mais elles permettent de marquer la différence essentielle entre les nombres entourés en vert et ceux barrés en rouge.

  • Pour dire qu'une valeur est possible, il suffit de le réaliser.
  • Pour dire qu'une valeur est impossible on ne s'appuie pas sur un exemple dessiné mais sur un raisonnement.

La question est alors de savoir quels autres nombres on peut barrer, le raisonnement ligne par ligne permet de barrer tous les nombres supérieurs à 10.

Le schéma ci-dessous est alors une bonne formulation de la réponse au problème :

solution5

Etiquettes.

solution1a

La figure ci-dessus montre qu'il est possible de placer 11 étiquettes 5x7 sur la grille 18 x 24.

La grille complète contient 18 x 24 = 432 petits carreaux.

Chaqué étiquette contient 35 petits carreaux.

13 x 35 = 455 ce qui montre qu'il est impossible de placer 13 étiquettes puiqu'il n'y a pas assez de carreaux dans la grille.

A ce stade, la conclusion provisoire est qu'il est possible de placer 11 étiquettes (on l'a fait) et qu'il est impossible de placer 13 étiquettes (on l'a expliqué).

solution3b

Pour 12 étiquettes on ne sait pas. Le nombre de carreaux disponibles est suffisant puisque 12 x 35 = 420 mais ça ne prouve pas qu'il est possible de placer 12 étiquettes.

Par exemple, une grille de dimensions 4 x 200 ne permet de placer aucune étiquette bien que le nombre total de carreaux soit 800.

 

Remarque : un maître qui souhaite une conclusion simple choisira de poser le problème sur une grille 17 x 24 à la place de notre grille 18 x 24.

En effet, la disposition de 11 étiquettes proposée ci-dessus peut être reproduite sur la grille 17 24. De plus le nombre total de carreaux disponibles est alors 17 24 = 408, il est donc impossible de placer 12 étiquettes (qui totalisent 420 carreaux).

Télécharger des grilles 24x17

Nous allons maintenant montrer que sur une grille 24 x 18 il n'est pas possible de placer 12 étiquettes, ce qui permettra de conclure : il est possible de placer 11 étiquettes comme le montre le schéma ci-dessus et il est impossible d'en placer plus de 11.

solution2a

Intéressons nous à une des colonnes de 18 carreaux de la grille, par exemple celle qui est coloriée en rouge.

Imaginons un découpage d'étiquettes. Combien de carreaux de la colonne rouge sont à l'intérieur des étiquettes ?

Comme les étiquettes sont découpées en suivant les lignes du quadrillage, si une étiquettes utilise des carreaux de cette colonne elle en utilise 5 ou 7.

Le nombre total de carreaux de la colonne rouge situés est donc obtenu en ajoutant des 5 et des 7

Or il n'est pas possible d'obtenir 18 comme somme de nombres égaux à 5 ou à 7. Il suffit d'essayer toutes les valeurs possibles pour s'en convaincre :

  • Si on n'utilise aucun 7 la plus grande valeur possible sera 3 x 5 = 15
  • Si on n'utilise un 7 la plus grande valeur possible sera 7 + 2 x 5 = 17
  • Si on n'utilise deux 7 la plus grande valeur possible sera 2 x 7 = 14
  • Aucune valeur ne convient en utilisant plus de deux 7.

Il y aura donc au moins une carreau non utilisé dans la colonne rouge le nombre de carreau réellement utilisés ne peut dépasser 17.

Il en est de même dans chacune des autres colonnes, le nombre de carreaux réellement utilisés en tout ne peut donc pas dépasser 17 x 24 = 408. Or, pour placer 12 étiquettes, il faudrait utiliser 420 carreaux, il est donc impossible de placer 12 étiquettes sur la grille 18 x 24.

Le plus grand périmètre

solution1b

Comme le montre la figure ci-dessus, il est possible de tracer une figure dont le périmètre est 34.

solution2b

Quand on fait le tour d'une figure fermée tracée sur la grille, on passe sur autant de segments rouges que de points bleus.

En effet, si on commence par un point on passe successivement sur un point, un segment, un point, un segment, un point, un segment, en terminant par un segment.

Comme il y a 35 intersections sur la grille, il est impossible d'utiliser plus de 35 points bleus.

Il est donc imposible d'obtenir un périmètre supérieur à 35.

Est-il possible d'obtenir un périmètre égal à 35 ?

solution3a

Faisons le tour d'une figure fermée en coloriant les différents segments selon la direction dans laquelle on se déplace :

Rouge si on se déplace vers la droite, vert si on se déplace vers la gauche bleu vers le bas et jaune vers le haut.

Pour revenir au point de départ, il faut faire autant de pas vers la droite que vers la gauche. Il y a donc autant de segments rouges que de segments verts. Il faut également autant de segments bleus que de jaunes.

le nombre total de segments parcourus est donc égal au double du nombre de segments rouges plus le double du nombre de segments bleus. C'est un nombre pair.

 

Le nombre de segments sur le tour de la figure (autrement dit le périmètre) est pair, il ne peut donc pas être égal à 35.

Le périmètre ne peut pas être supérieur à 35 ni égal à 35, il ne peut donc pas être supérieur à 34.

La valeur 34 obtenue sur la figure proposée plus haut est donc le maximum.

Les voisins multiples

5 10 2 8 4 12 6 3 9

La liste ci-dessus respecte toutes les règles, et le plus grand nombre est 12.

 

essayons de faire une liste respectant les règles en utilisant exclusivement des nombres plus petits que 12.

Les nombre que l'on peut envisager d'utiliser sont : 2 3 4 5 7 8 9 10 et 11

Parmi ceux-ci, il est impossible d'utiliser 7 car il ne peut avoir aucun voisin (aucun des autres nombres disponibles n'est multiple de 7 ni diviseur de 7).

Pour la même raison il est impossible d'utiliser 11.

Il ne reste donc que 8 nombres utilisables, il est donc impossible de faire une liste de 9 nombres tous plus petits que 12 en respectant les règles de ce problème.

La liste proposée plus haut est donc la meilleure possible.

Les intersections

Un segment ne peut avoir qu'une intersection avec un autre segment.

Donc chaque côté du quadrilatère bleu ne peut pas couper plus de 4 fois le quadrilatère rouge (une fois pour chaque côté rouge).

Il ne peut pas y avoir plus de 4 x 4 = 16 intersections entre les deux quadrilatères.

 

Un segment ne peut pas avoir plus de deux intersections avec un cercle donc chaque quadrilatère ne peut pas couper plus de 8 fois le cercle.

Le nombre total d'intersections ne peut donc pas dépasser 16 + 8 + 8 = 32

solution1c

Sur la figure ci-contre, il y a 32 intersections.

On vient par ailleurs d'expliquer qu'on ne peut pas avoir plus de 32 intersections.

Le plus grand nombre possible d'intersections est donc 32.

 

Solutions de quelques autres problèmes.