Noël approchant...
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
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
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
-- Schnoebelen, Philippe
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
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 :-)
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. 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.
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:
On voit que les associations se répètent d'une ligne sur l'autre.