Quelques problèmes historiques

Des problèmes de transport¶

Les 7 ponts de Königsberg¶

A Kœnigsberg, en Poméranie, il y a une île appelée Kneiphof; le fleuve qui l’entoure se divise en deux bras, sur lesquels sont jetés les sept ponts \(a\), \(b\), \(c\), \(d\), \(e\), \(f\), \(g\). Cela posé, peut-on arranger son parcours de telle sorte que l’on passe sur chaque pont, et, que l’on ne puisse y passer qu’une seule fois? Cela semble possible, disent les uns; impossible, disent les autres; cependant personne n’a la certitude de son sentiment.

Donner la liste de tous les chemins passant une et une seule fois par chaque pont, lorsque l'on part initialement de la rive \(D\) (on peut passer plusieurs fois par une même rive).

Attention, il y a beaucoup de cas, il faut les lister de manière logique : expliquer votre méthode.
Le problème des 7 ponts de Königsberg semble-t-il admettre une solution ?
Combien de ponts au minimum doit-on ajouter pour qu'il soit possible de parcourir la ville en passant une et une seule fois par tous les ponts ? Quel est le point de départ et le point d'arrivée de votre parcours ?

Le problème du voyageur de commerce¶

Un livreur doit déposer des courriers dans cinq villes : Nantes, La Rochelle, Limoges,Strasbourg, Cahors. Initialement, sa fourgonette se trouve à La Rochelle. Il doit organiser son trajet de manière à passer par toutes les villes en le moins de temps possible. Il doit également terminer son trajet à La Rochelle, où il habite.

On indique dans le tableau ci-dessus les durées des trajets entre deux villes : si \(i\) et \(j\) sont deux indices de ligne et de colonne valides, alors la case à l'intersection de la ligne \(i\) et de la colonne \(j\) du tableau indique la durée nécessaire pour effectuer le trajet depuis la ville \(i\) à la ville \(j\) (dans ce sens). Par exemple, au départ de La Rochelle, il lui faut \(18,2\) heures pour se rendre à Strasbourg.

Certaines cases du tableau sont vides. Est-ce un problème ?
Combien existe-t-il de trajets possibles pour le livreur ?
Déterminer le trajet le plus rapide pour délivrer tous les colis. Expliquer votre méthode.

Des problèmes d'organisation¶

Un dîner presque parfait¶

Al-Khwârizmî (A), Babbage (B), Church (C), Dijkstra (D), Goldwasser (G), Hopper (H), Johnson (J), Lovelace (L) sont conviées au dîner de reception du prix Turing. Malheureusement, toutes les personnes ne s'apprécient pas forcément.

On indique dans le tableau l'état des relations entre les personnages, une croix indiquant que les personnes ne se supportent pas l'une l'autre et ne veulent en aucun cas être assis à la même table.

Représenter le graphe correspondant à la situation de l'énoncé. Chaque sommet représentera une personne, on indiquera le fait que deux personnes ne peuvent pas s'assoir à la même table à l'aide d'une arête reliant les sommets concernés.
Expliquer pourquoi il est nécessaire d'utiliser au moins quatre tables afin que toutes les personnes soient assises sans personne à leur table qu'elles ne supporteraient pas.
En coloriant le graphe avec un certain nombre de couleurs, proposer un plan de tables pour le dîner : toutes les personnes doivent apprécier leur soirée. Deux sommets coloriés avec la même couleur ne peuvent donc pas être reliés par une arête. Combien de tables est-il nécessaire d'utiliser au minimum ?

Planification d'examens¶

M. Moncoucut s'arrache les cheveux pour organiser les épreuves de bac blanc de spécialité au lycée. Il lui faut organiser les épreuves de NSI, Mathématiques, Physique-Chimie, SVT, AMC, SES, HLP, et HGGSP. D'après les données du lycée, les élèves de terminales ont choisi les doublettes suivantes :

NSI et Mathématiques
NSI et SES
Mathématiques et Physique-chimie
Mathématiques et SVT
Physique-Chimie et SVT
SES et AMC
SES et HLP
SES et HGGSP
HGGSP et AMC
HGGSP et HLP

Quel est le nombre maximum d’épreuves que l'on peut mettre en parallèle ?
Une épreuve occupe une demi-journée. Quel est le temps minimal nécessaire pour ces épreuves (en demi-journées) ?

Problèmes divers¶

La chèvre, la salade et le loup¶

Une chèvre, une salade et un loup se trouvent sur la rive d’un fleuve ; un passeur souhaite les transporter sur l’autre rive mais, sa barque étant trop petite, il ne peut transporter qu’un seul d’entre eux à la fois.

Comment doit-il procéder afin de ne jamais laisser ensemble et sans surveillance le loup et la chèvre, ainsi que la chèvre et le salade ?

Indication. Cette situation peut être modélisée à l’aide d’un graphe. On notera \(P\) le passeur, \(C\) la chèvre, \(S\) la salade et \(L\) le loup.

Les sommets du graphe seront alors les couples précisant qui est sur la rive initiale, qui est sur l’autre rive.

Par exemple, le couple \((PCS,L)\) signifie que le passeur est sur la rive initiale avec la chèvre et le chou (qui sont donc sous surveillance), alors que le loup est sur l’autre rive.
Une arête relie deux sommets lorsque le passeur peut passer d’une situation à l’autre.

Par exemple, en transportant la chèvre, le passeur passe du sommet \((PCS,L)\) au sommet \((S,PCL)\) : les deux sommets sont donc reliés par une arête.

Pour résoudre le problème on pourra donc :

énumérer les sommets du graphe (certaines configurations sont interdites) ;
déterminer les arêtes du graphes ;
identifier le sommet qui correspond à la situation initiale du problème et le sommet qui correspond à la situation du problème résolu (le passeur, la chèvre, la salade et le loup sont sur l'autre rive).

Quel est le lien entre ces deux sommets ?

Le jeu des allumettes¶

On dispose au centre de la table deux tas de trois allumettes allumettes. Chaque joueur peut, à tour de rôle, prendre une ou deux allumettes d'un des deux tas. Le joueur qui prend la dernière allumette a perdu la partie.

Le premier joueur est-il certain de gagner, certain de perdre, ou bien cela dépend-il des coups de son adversaire ?

Indication. Faire la liste de tous les états possibles pour les tas d'allumettes, ainsi que les liens entre les états selon que l'on prend une, ou deux allumettes. Représenter ces informations sous forme de graphes. Quel(s) état(s) sont perdants à coup sûr ?
On ajoute une allumette à un des tas. Ainsi, initiallement au centre de la table il y a un tas de quatre allumettes et un tas de trois allumettes.

Le premier joueur est-il certain de gagner ?