problème des convives

Imaginez quatre couples qui prennent place autour d'une table ronde. Ce problème des convives, aussi appelé « problème des ménages », impose aux convives une alternance régulière entre hommes et femmes, mais chacun doit éviter les deux sièges voisins de son partenaire. Le défi consiste à compter toutes les dispositions qui respectent simultanément ces deux règles. La table étant circulaire, tourner toute la disposition ne crée pas une nouvelle solution : seule la structure relative des places compte.

Le problème des convives demande de dénombrer les placements de n couples autour d'une table circulaire. La lettre n désigne le nombre de couples, donc il y a 2n personnes. On impose une alternance entre les hommes et les femmes, puis on interdit à chaque personne de s'asseoir à côté de son partenaire.

Pour compter sans ambiguïté, on peut fixer la position d'une femme et considérer identiques deux placements obtenus par rotation complète de la table. Après avoir placé les femmes, les hommes occupent les intervalles qui les séparent. Chaque homme doit alors éviter les deux intervalles touchant sa partenaire. Le nombre de placements dépend de n et s'exprime par des relations de récurrence, plutôt que par une simple factorielle.

La convention de comptage doit être annoncée : autoriser les rotations multiplierait chaque résultat par le nombre de sièges, tandis qu'une réflexion peut être considérée comme identique ou différente selon le problème. Le problème est aussi décrit par des graphes, dans lesquels une disposition valide devient un cycle hamiltonien soumis aux interdictions de voisinage.

Considérons quatre couples, notés A-a, B-b, C-c et D-d. Fixons l'ordre des femmes autour de la table : A, B, C, D. Les quatre intervalles sont A-B, B-C, C-D et D-A.

Chaque homme doit éviter les deux intervalles qui touchent sa partenaire : a peut aller dans B-C ou C-D, b dans C-D ou D-A, c dans D-A ou A-B, et d dans A-B ou B-C. En essayant ces intervalles sans en réutiliser un, seules deux affectations complètes survivent : c dans A-B, d dans B-C, a dans C-D et b dans D-A ; ou d dans A-B, a dans B-C, b dans C-D et c dans D-A.
La première donne A, c, B, d, C, a, D, b ; la seconde donne A, d, B, a, C, b, D, c. Dans les deux cas, aucun homme n'est voisin de sa partenaire et l'alternance est respectée. Il y a donc exactement 2 placements valides pour cet ordre fixé des femmes.

Les femmes peuvent être ordonnées de 6 façons autour de la table lorsque la position de A est fixée. Le total correspondant à cette convention est $3!times2=123!\; \backslash \backslash times\; 2=12$. Un contrôle consiste à reprendre chacun des 6 ordres féminins et à vérifier les deux voisins de chaque partenaire.

Pour un petit nombre de couples, on fixe une personne, on énumère les ordres possibles des autres femmes, puis on teste les intervalles disponibles pour les hommes. Cette méthode exhaustive convient lorsque le nombre de cas reste assez réduit pour être vérifié à la main.

Pour davantage de couples, une relation de récurrence ou un programme de dénombrement devient préférable. Le critère de choix est le nombre de dispositions à explorer : une liste complète devient vite impraticable, alors qu'une récurrence réutilise les sous-problèmes déjà comptés.

Le problème des convives ne se confond pas avec le simple placement alterné. Dans ce dernier cas, les partenaires peuvent être voisins ; ici, la disposition est rejetée dès qu'un couple occupe deux sièges adjacents. Par exemple, A, a, B, b, C, c, D, d alterne bien les genres, mais ne constitue pas une solution.

Il ne se confond pas non plus avec un arrangement en ligne. Une table circulaire rend voisins le premier et le dernier siège, alors qu'ils seraient séparés dans une file. Une disposition valide en ligne doit donc encore être contrôlée sur cette jonction avant d'être comptée ici.

Le cas d'un seul couple est impossible : avec seulement deux sièges, les partenaires sont nécessairement voisins. Le symptôme est un nombre de solutions égal à zéro ; il faut au moins trois couples pour que la question devienne non triviale.

Le nombre annoncé dépend de la convention de symétrie. Si les rotations de la table sont distinguées, le total du cas de quatre couples devient 12 × 8 = 96, car huit sièges peuvent recevoir la position de référence. Si les réflexions sont aussi identifiées, il faut encore préciser l'action retenue avant de diviser : une disposition peut posséder une symétrie et ne pas avoir une orbite de taille uniforme.

L'alternance seule ne suffit jamais. Le piège consiste à vérifier seulement le genre du voisin immédiat ; il faut examiner les deux côtés de chaque personne et traiter la jonction finale comme un voisinage ordinaire.

La reformulation en théorie des graphes transforme les convives et les sièges en sommets reliés par des arêtes autorisées ou interdites. Elle permet de voir une disposition comme un cycle hamiltonien, c'est-à-dire un cycle qui passe une fois par chaque sommet, puis d'étudier le comptage avec les outils de la combinatoire des graphes. Pour prolonger cette perspective, l'article Classer les nœuds montre comment la théorie des nœuds analyse des structures où les liens entre arrangements deviennent essentiels.