La semaine dernière, nous nous interrogions sur le nombre de solutions au problème des huit reines. Il existe douze solutions essentiellement distinctes, chacune pouvant générer huit configurations par rotations et réflexions, ce qui devrait donner 12 x 8 = 96. L’explication réside dans le fait qu’une des douze solutions de base possède une symétrie centrale. Elle ne change pas lorsqu’on la fait pivoter de 180°. De même, une rotation de 270° donne la même configuration qu’une rotation de 90°.Cette solution symétrique ne génère que deux configurations distinctes par rotation et deux par réflexion, soit quatre au lieu de huit. Le total est donc de 11 x 8 + 4 = 92.Concernant le problème des cavaliers de Guarini, chaque cavalier a besoin d’un minimum de deux mouvements pour atteindre un autre coin de l’échiquier 3×3.La solution requiert donc au moins huit mouvements. En réalité, il en faut le double, soit seize. Pour mieux visualiser les déplacements nécessaires, il est utile de transformer l’échiquier en un graphe octogonal. Chaque nœud représente une case et chaque arête un mouvement possible du cavalier d’une case à l’autre. dans la position initiale, les cavaliers occupent des nœuds alternés.Pourquoi huit nœuds alors que l’échiquier 3×3 compte neuf cases ? La case centrale n’est jamais accessible à aucun cavalier. Elle est donc inexistante pour les déplacements possibles.

Le dernier problème de la semaine dernière consistait à trouver un parcours complet du cavalier sur un échiquier 3×4 en partant d’un coin.

Combien de solutions distinctes existe-t-il ? Et si le cavalier part d’une autre case ?

Graphes, trains et relations

En parlant des graphes et de leur utilité pour aborder des situations où des éléments sont connectés ou liés de diverses manières, voici quelques problèmes qui se simplifient avec une représentation « graphique » appropriée :

1. Démontrer que dans un groupe de deux personnes ou plus, au moins deux ont le même nombre d’amis dans le groupe.
2. Une façon de connecter les quinze communautés autonomes péninsulaires par un futur réseau de voies à très haute vitesse serait centralisée : de Madrid partent des voies rectilignes vers les capitales des quatorze autres communautés. Mais si l’on se rend compte qu’il n’est pas indispensable de passer par Madrid pour aller, par exemple, d’Oviedo à Bilbao, et que l’on souhaite minimiser la longueur totale des voies construites, comment aborder le problème ?
3. Ana et Blas assistent à une fête avec quatre autres couples. En se rencontrant, certains se serrent la main, d’autres s’embrassent. À la fin de la fête, Blas demande aux personnes présentes combien de mains elles ont serrées en saluant. Il reçoit neuf réponses différentes. À combien de personnes Ana a-t-elle serré la main ?

Problèmes de Graphes et Solutions

Le Problème des Huit Reines

Le texte mentionne le problème des huit reines comme point de départ. Il souligne qu’il existe initialement douze solutions distinctes, produisant 96 configurations via rotations et réflexions. Cependant, une solution symétrique réduit ce nombre à quatre configurations en raison de sa symétrie, ce qui donne un total de 92 solutions distinctes.

Le Problème des Cavaliers de Guarini

Le texte aborde également le problème des cavaliers de Guarini sur un échiquier 3×3. Il explique qu’il faut au moins deux mouvements pour qu’un cavalier atteigne un autre coin, nécessitant un minimum de huit mouvements. En réalité, il en faut seize. L’échiquier est modélisé comme un graphe octogonal pour visualiser les mouvements, la case centrale étant inaccessible.

Parcours du Cavalier sur un Échiquier 3×4

Le dernier problème présenté est celui de trouver un parcours complet du cavalier sur un échiquier 3×4, en commençant d’un coin. Le texte ne donne pas le nombre de solutions pour ce problème ni si la position de départ affecte le nombre de solutions.

Graphes, Trains et Relations

Le texte propose ensuite plusieurs problèmes qui peuvent être résolus en utilisant la théorie des graphes:

1. Problème d’amitié: Démontrer que dans un groupe de deux personnes ou plus, au moins deux ont le même nombre d’amis.
2. Réseau ferroviaire: Comment minimiser la longueur totale des voies pour connecter quinze communautés autonomes par un réseau à grande vitesse, en évitant le passage obligatoire par Madrid.
3. Poignée de mains: Déterminer combien de personnes Ana a salué sachant que Blas a demandé à différents invités combien de poignées de mains ils ont échangées et a obtenu neuf réponses différentes.

FAQ

Qu’est-ce que la théorie des graphes ? La théorie des graphes est l’étude des graphes,qui sont des structures mathématiques utilisées pour modéliser des relations entre des objets.

comment les graphes sont-ils utilisés ? Ils sont utilisés pour résoudre des problèmes de connexion, d’optimisation, de planification et d’analyze de réseaux, entre autres.

Qu’est-ce qu’un graphe octogonal ? Un graphe octogonal est une représentation d’un échiquier 3×3 où les cases sont représentées par des nœuds et les mouvements possibles du cavalier par des arêtes.

Tableau Récapitulatif

| Problème | Solution/Concept |

| :—————————– | :———————————————————————————— |

| Huit Reines | 92 solutions distinctes, symétrie impliquée |

| Cavaliers de Guarini (3×3) | requiert 16 mouvements, modélisation en graphe octogonal |

| Parcours du Cavalier (3×4) | Non spécifié (nombre de solutions et dépendance de la position de départ non précisés) |

| Problème d’amitié | Au moins deux personnes avec le même nombre d’amis |

| Réseau ferroviaire | Minimisation de la longueur du réseau, optimisation des parcours |

| Poignée de mains | Déduction du nombre de poignées de mains pour Ana |