Noël approchant...

davidd · November 2018

Bonjour à toutes et à tous,

Des amis m'ont soumis un problème que je n'ai pas réussi à résoudre formellement (n'ayant hélas pas le niveau mathématique suffisant). Je pense qu'il doit être possible de le résoudre par combinatoire.

Dans notre groupe d'amis, nous avons 10 adultes (5 couples) et 10 enfants (répartis inégalement).

On note Pnm l'un des parents avec n={1,2} rang de l'adulte dans le couple et m={A..E} lettre associée à la famille

On note Enm l'enfant d'un couple n={1...} rang de l'enfant dans la famille et m={A..E} lettre associée à la famille

p1A -> E1A,E2A

P2A -> E1A,E2A

p1B -> E1B,E2B,E3B

p2B -> E1B,E2B,E3B

p1C -> E1C,E2C

p2C -> E1C,E2C

p1D -> E1D

p2D -> E1D

p1E -> E1E,E2E

p2E -> E1E,E2E

Le but est que que chaque adulte offre à Noël un cadeau à l'un des enfants, sachant :

1/ On ne peut être associé avec l'un de ses propres enfants

2/ on ne doit jamais être associé deux fois au même enfant

J'ai essayé de le résoudre de manière empirique avec un programme mais comme j'utilise de l'aléatoire pour associer parent et enfant, j'arrive souvent sur une boucle sans fin (quand il n'y a plus assez de choix).

Quelqu'un ici serait-il susceptible de me donner une solution à ce problème, idéalement avec un algorithme que je puisse traduire sous forme d'un programme informatique (le St Graal serait de l'avoir en python :-) )

Merci à toutes et à tous!

--
David

nicolas.patrois · November 2018

Au pire tu peux tenter toutes les combinaisons avec une fonction bien choisie de la bibliothèque itertools et dès que l’une convient…

YvesM · November 2018

Bonjour,

De tête, est-ce que cette solution convient, sinon pourquoi ?

P1A=E2B
P2A=E3B

P1B=E2A
P2B=E2C

P1C=E2E
P2C=E1B

P1D=E1E
P2D=E1A

P1E=E1D
P2E=E1C

davidd · November 2018

Il me faudrait une solution exhaustive pour pouvoir l'appliquer pendant toutes les années qui viennent :-)
Empiriquement, je peux effectivement écrire "à la main" toutes les solutions possibles.

Mais surtout par curiosité, j'aimerais connaître la solution mathématique qui donne toutes les combinaisons :-)

Math Coss · November 2018

Voici une réalisation de l'idée de Nicolas Patrois. Elle donne $427\,680$ solutions parmi les $10!=3\,628\,800$ permutations possibles d'une liste à $10$ éléments.

Cela suggère un problème plus général : pour chaque entier $k\in\{1,\dots,n\}$, on se donne une partie $A_k$ (« images interdites ») ; combien y a-t-il de permutations $\sigma$ dans $\mathfrak{S}_n$ telles que $\sigma(k)\notin A_k$ pour tout $k$. Par exemple, si $A_k=\{k\}$ pour tout $k$, on retrouve le problème des dérangements.

#! /usr/bin/python
# -*- coding: utf-8 -*-

import math
import itertools

adultes = ['P%s%s'% (a,b) for b in ['A','B','C','D','E'] for a in [1,2]]
enfants = ['E%s%s'% (a,b) for b in ['A','B','C','D','E'] for a in [1,2]]
enfants[8] = 'E3B'
#print enfants

solutions = []
for p in itertools.permutations(enfants):
    if all(adultes[k][2]!=p[k][2] for k in range(10)):
        s = [(adultes[k],p[k]) for k in range(10)]
        solutions.append(s)

print "Nombre d'appariements possibles : 10! = %s" % math.factorial(10)
print "Nombre de solutions : %s" % len(solutions)
print "Exemple de solution : %s" % solutions[1245]

PS : En fait, ce n'est pas la bonne façon de poser le problème (même si elle marche). Il vaudrait mieux raisonner en termes de graphes. Ah, voilà : on fait un graphe biparti avec $10$ parents et $10$ enfants. On met une arête entre un parent et un enfant s'ils n'ont pas de lien de parenté. Il s'agit de trouver un recouvrement du graphe par des arêtes disjointes (un pavage par des « dominos »). C'est donc un problème de dimères.

davidd · November 2018

Magnifique , je suis "paré" pour les 427680 Noël qui viennent ;-)

Merci beaucoup.

[EDIT]

Après vérification, il semble que l'une des contraintes du problème ne soit pas respectée par la solution :

L'association Adulte --> Enfant doit être unique
Si je prends les dix premières solutions proposées par le programme:

[('P1A', 'E1B'), ('P2A', 'E2B'), ('P1B', 'E1A'), ('P2B', 'E2A'), ('P1C', 'E1D'), ('P2C', 'E2D'), ('P1D', 'E1C'), ('P2D', 'E2E'), ('P1E', 'E2C'), ('P2E', 'E3B')]
[('P1A', 'E1B'), ('P2A', 'E2B'), ('P1B', 'E1A'), ('P2B', 'E2A'), ('P1C', 'E1D'), ('P2C', 'E2D'), ('P1D', 'E1C'), ('P2D', 'E2E'), ('P1E', 'E3B'), ('P2E', 'E2C')]
[('P1A', 'E1B'), ('P2A', 'E2B'), ('P1B', 'E1A'), ('P2B', 'E2A'), ('P1C', 'E1D'), ('P2C', 'E2D'), ('P1D', 'E2C'), ('P2D', 'E2E'), ('P1E', 'E1C'), ('P2E', 'E3B')]
[('P1A', 'E1B'), ('P2A', 'E2B'), ('P1B', 'E1A'), ('P2B', 'E2A'), ('P1C', 'E1D'), ('P2C', 'E2D'), ('P1D', 'E2C'), ('P2D', 'E2E'), ('P1E', 'E3B'), ('P2E', 'E1C')]
[('P1A', 'E1B'), ('P2A', 'E2B'), ('P1B', 'E1A'), ('P2B', 'E2A'), ('P1C', 'E1D'), ('P2C', 'E2D'), ('P1D', 'E3B'), ('P2D', 'E2E'), ('P1E', 'E1C'), ('P2E', 'E2C')]
[('P1A', 'E1B'), ('P2A', 'E2B'), ('P1B', 'E1A'), ('P2B', 'E2A'), ('P1C', 'E1D'), ('P2C', 'E2D'), ('P1D', 'E3B'), ('P2D', 'E2E'), ('P1E', 'E2C'), ('P2E', 'E1C')]
[('P1A', 'E1B'), ('P2A', 'E2B'), ('P1B', 'E1A'), ('P2B', 'E2A'), ('P1C', 'E1D'), ('P2C', 'E2D'), ('P1D', 'E2E'), ('P2D', 'E1C'), ('P1E', 'E2C'), ('P2E', 'E3B')]
[('P1A', 'E1B'), ('P2A', 'E2B'), ('P1B', 'E1A'), ('P2B', 'E2A'), ('P1C', 'E1D'), ('P2C', 'E2D'), ('P1D', 'E2E'), ('P2D', 'E1C'), ('P1E', 'E3B'), ('P2E', 'E2C')]
[('P1A', 'E1B'), ('P2A', 'E2B'), ('P1B', 'E1A'), ('P2B', 'E2A'), ('P1C', 'E1D'), ('P2C', 'E2D'), ('P1D', 'E2E'), ('P2D', 'E2C'), ('P1E', 'E1C'), ('P2E', 'E3B')]
[('P1A', 'E1B'), ('P2A', 'E2B'), ('P1B', 'E1A'), ('P2B', 'E2A'), ('P1C', 'E1D'), ('P2C', 'E2D'), ('P1D', 'E2E'), ('P2D', 'E2C'), ('P1E', 'E3B'), ('P2E', 'E1C')]

On voit que les associations se répètent d'une ligne sur l'autre.

Noël approchant...

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 8