Un défi par semaine

Septembre 2016, 2e défi

Le 9 septembre 2016  - Ecrit par  Ana Rechtman Voir les commentaires (5)

Nous vous proposons un défi du calendrier mathématique 2016 chaque vendredi et sa solution la semaine suivante.

Semaine 37 :

Le plan d’un musée indique le nombre d’œuvres à voir dans chaque salle. Louis désire visiter $6$ de ces salles ; quel est le nombre maximum d’œuvres qu’il pourra regarder ?

PNG - 27.8 ko

Solution du 1er défi de Septembre :

Enoncé

La réponse est $n=3$ et $n=7$.

Supposons que $n^2-12n+46$ soit un nombre premier différent de 2 donc impair. Dans ce cas, comme $2$ divise $12$ et $46$, $n^2$ ne peut être pair et donc $n$ non plus. Ainsi soit $n^2-12n+46=2$, soit $n$ est impair. Si l’on est dans le premier cas, on obtient successivement :

$n^2-12n+44 = 0$

$n = \frac{12\pm \sqrt{144-4\times 44}}{2}.$

Ces valeurs possibles n’étant pas entières, on se trouve nécessairement dans le cas où $n$ est impair. Le nombre $n^2-10n+23$ est donc pair et ainsi égal à 2 car c’est l’unique nombre premier pair. L’entier $n$ vérifie alors successivement :

$n^2-10n+23 = 2$

$n^2-10n+21 = 0$

$(n-3)(n-7) = 0.$

Les valeurs possibles pour $n$ sont donc nécessairement $3$ et $7$. En substituant ces valeurs dans les trois expressions initiales, on obtient bien trois nombres premiers : pour $n=3$, les trois nombres en question valent $2$, $13$ et $19$ et pour $n=7$ on obtient $2$, $11$ et $17$.

Post-scriptum :

Calendrier mathématique 2016 - Sous la direction d’Ana Rechtman, Maxime Bourrigan - Textes : Aubin Arroyo, Fabiola Manjarrez et Ana Rechtman.
2015, Presses universitaires de Strasbourg. Tous droits réservés.

Partager cet article

Pour citer cet article :

Ana Rechtman — «Septembre 2016, 2e défi» — Images des Mathématiques, CNRS, 2016

Commentaire sur l'article

  • Septembre 2016, 2e défi

    le 9 septembre à 08:17, par Al_louarn

    Répartissons les salles en couches, selon la distance (Manhattan) à l’entrée :
    couche $1$ : $\{2\}$
    couche $2$ : $\{6,4\}$
    couche $3$ : $\{12,10,3\}$
    couche $4$ : $\{8,5,1\}$
    couche $5$ : $\{11,9\}$
    couche $6$ : $\{7\}$

    Louis doit passer par toutes les couches pour aller de l’entrée à la sortie. Mais comme il veut voir $6$ salles et qu’il y a $6$ couches, il doit visiter exactement une salle par couche.

    Par exemple il peut choisir le chemin $[2,6,12,8,9,7]$, donc le nombre maximal d’oeuvres qu’il peut voir vérifie $n \geq 2 + 6 + 12 + 8 + 9 + 7$, soit $n \geq 44$.

    On peut majorer $n$ en prenant la meilleure salle de chaque couche : $n \leq 2 + 6 + 12 + 8 + 11 + 7$, soit $n \leq 46$. Mais ça ne donne pas un chemin valide puisque les salles $8$ et $11$ ne sont pas connectées. On peut donc améliorer cette majoration en remplaçant, dans l’une des couches à plusieurs salles, la meilleure salle par la deuxième meilleure salle, de façon à minimiser le nombre d’oeuvres perdues :
    $n \leq 46 - min(6-4, 12-10, 8-5, 11-9)$, soit $n \leq 44$.

    Conclusion : $n=44$ et le chemin $[2,6,12,8,9,7]$ est optimal.

    Répondre à ce message
    • Septembre 2016, 2e défi

      le 9 septembre à 08:54, par Al_louarn

      Précision : pour trouver ce chemin j’ai utilisé un algorithme glouton. A chaque étape on choisit la meilleure seule entre celle située au sud (si elle existe) et celle située à l’est (si elle existe) de la salle courante. Comme le musée est un rectangle $3 \times 4$ dont l’entrée et la sortie sont respectivement situés aux coins nord-ouest et sud-est, on obtient à coup sûr un chemin passant par exactement $3 + 4 - 1 = 6$ salles. L’algorithme ne trouve pas toujours un chemin optimal, mais donne déjà un bon minorant de $n$.

      Répondre à ce message
      • Septembre 2016, 2e défi

        le 9 septembre à 18:50, par Daniate

        Bonsoir,

        Vous pouvez obtenir le chemin optimal avec l’algorithme de Dijsksta en remplaçant le nombre de salles par leur complément à 12 (par exemple). Mais n’est-ce pas écraser une mouche avec un marteau pilon ?

        Il n’y a que 10 chemins et sachant qu’un chemin peut être amélioré en remplaçant une salle par celle qui lui est contiguë en diagonale SO-NE, on supprime rapidement 1, puis 3, puis 4, puis 10. Il reste 2 chemins puisque 5-9 est inférieur à 5-11 et comme 8+9>5+11 il vient 2-6-12-8-9-7.

        Répondre à ce message
        • Septembre 2016, 2e défi

          le 10 septembre à 12:48, par Niak

          Puisque vous parlez d’approches gloutonnes (c’est également le cas de Dijkstra), il me semble que l’approche algorithmique la plus appropriée pour ce problème reste la programmation dynamique. Dans la mesure où l’on ne peut visiter que 6 salles, il faut à chaque pas aller vers la droite ou le bas. Si l’on note $a_{i,j}$ les valeurs de la matrice de l’énoncé, remplissons (par exemple ligne après ligne) une nouvelle matrice dont les valeurs vérifient $b_{i,j} = a_{i,j} + \max(b_{i-1,j},b_{i,j-1})$ (prendre $0$ pour les valeurs dont les indices sortent du tableau). En décorant de plus ces valeurs d’une flèche indiquant la direction d’où provient le $\max$ de la formule, on obtient :

          $[2, \rightarrow 6, \rightarrow 9, \rightarrow10]\\ [\downarrow 8, \rightarrow 20, \rightarrow 25, \rightarrow 36]\\ [\downarrow 18, \downarrow 28, \rightarrow 37, \rightarrow 44]$

          Chaque case contient la somme maximale d’un chemin jusqu’à elle-même depuis l’entrée. Pour retrouver le chemin optimal (unique ici), il suffit de remonter les flèches depuis la case finale.

          Répondre à ce message
          • Septembre 2016, 2e défi

            le 13 septembre à 09:38, par Daniate

            Bonjour,
            Merci pour votre remarque qui me permet de découvrir une technique que j’ignorais et qui est pleine de bon sens. L’algorithmique m’est tombé dessus dans mes dernières années d’enseignement sans que j’y trouve le moindre plaisir, le pensum Dijkstra étant au programme je l’ai assimilé mais sans aller plus loin.

            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