Discussion :

[Nemerle]

[édité une fois]

Soit 5 nombres distincts a<b<c<d<e compris entre 1 et 10.
Serge en connait la somme
Pierre en connait le produit
Corinne en connait la somme des carrés
Valérie connait la valeur v=(a+b+c)(d+e)

On demande à chacun à partir de leur unique valeur s'ils peuvent trouver les valeurs de a,b,c,d et e. On leur laisse une heure chacun de leur coté.

Au bout de la 1ière heure: ils se recontrent, mais personne n'indique que les valeurs sont trouvées. On leur laisse à nouveau une heure chacun de leur coté.
Au bout de la 2nde heure: ils se recontrent, mais personne n'indique que les valeurs sont trouvées. On leur laisse à nouveau une heure chacun de leur coté.
...
Au bout de la 23ième heure: ils se recontrent, mais personne n'indique que les valeurs sont trouvées. A ce moment, leurs visages s'illuminent et chacun indique qu'il connait a,b,c,d, et e.

Saurez-vous trouvez a,b,c,d,e ???

[fumidu]

Je crois que je vois comment faire : énumerer toutes les possibilités, puis éliminer tous les cas impossibles au fur et à mesure que les heures passent suivant des raisonnements du genre : tel combinaison est la seule à donner cette somme, donc si serge n'a pas trouvé, c'est que ce n'est pas ça...
Mais bon, ça me fait un peu peur de faire ça à la main, parce que le nombre de solutions possibles, soit C(5,10) ça fait 252 quand même...

Il y a ptet une méthode plus maligne ?

[oiffrig]

Je dirais plutôt qu'il y a A(10, 5) solutions possibles ce qui fait 30240, mais que l'on peut en fait réduire à C(10, 3) × C(7, 2) = 2520 (voir la remarque)

Mis à part ça, j'aurais deux questions :
- Que se disent-ils en se rencontrant ?
- Peut-on considérer qu'une solution a été trouvée si elle fait partie d'un ensemble de 120 (que l'on peut réduire à 10, voir la remarque) quintuplets (a, b, c, d, e) tous connus ? (Je suppose que non, mais je demande quand même au cas où)

Et une remarque : Les quintuplets solutions sont au nombre de 12
Pourquoi ? Tout simplement parce qu'il y a une notion d'ordre dans les valeurs de nos inconnues (sinon la valeur qu'a Valérie changerait), on peut cependant permuter a, b et c, ainsi que d et e, ce qui laisse 3! × 2! = 12 possibilités. On peut donc réduire nos ensembles de possibilités.

[ol9245]

au premier tour, ils savent que la somme ni le produit ni etc. ne sont uniques. chacun repart en ayant éliminé les solutions qui donne une somme unique, ou un produit unique, etc.

au deuxième tour, ils savent maintenant qu'il y a plus de deux somms identiques et plus que deux produitsidentiques etc.

et ainsi de suite

la solution est la combinaison de nombre dont la somme est présente au moins 23 fos dans les 30240 combinaisons possibles, le produit est aussi présent au moins 23 fois dans toutes les combinaisons possibles etc.

[Zavonen]

Sauf erreur de ma part 5 nombres distincts entre 1 et 10, ça peut s'identifier
au nombre de parties à 5 éléments d'un ensemble à 10 éléments car on peut toujours les supposer rangés par ordre croissant.
Je dirais donc a priori C5,10 = (10*9*8*7*6)/5!=252
Ah non! S,C,P, sont invariants par toute permutation mais pas V!
C'est donc C2,10*C3,8= 45*56=2520
Ensuite, le raisonnement suppose que chacun est intelligent d'une part et sait que les autres le sont aussi.
Ainsi il y a 4 fonctions S pour Serge, P pour Pierre, etc...
Si un ou plusieurs des 4 joueurs a une valeur possédant un unique antécédent par sa fonction, (par exemple un extremum absolu unique) il(s) trouvent.
Par exemple S=15 possède une seule solution.
Donc au fur et à mesure que le jeu avance on peut à chaque fois éliminer tous ces cas, on se retrouve donc avec un nombre des possibles qui diminue à chaque étape.
Les problèmes de ce type ont souvent été présentés dans American Scientific (Pour La Science) soit par Martin Gardner, soit par Douglas Hofstadter.
Il existe une autre manière de voir, au moyen de la théorie de l'information qui permet de mesurer quantitativement l'approche de la solution. J'y reviendrai si j'ai le temps.

[fumidu]

Pour le nombre de solutions à considérer au départ, je crois que c'est oiffrig qui a raison. Il faut choisir 5 nombres parmi 10, sachant que a, b et c sont permutables, ainsi que d et e.
Ca fait donc littéralement :

N = (10*9*8*7*6) / ( (3*2*1) * (2*1) ) = 2520

Perso, à la main, je n'ai pas le courage...

[ol9245]

n'aimant pas réfléchir (il est quand meme 1h du mat à Bangkok) j'ai choisi la force brute. et il y a bien 30240 solutions

par contre toutes sont présentes dnas plus de 23 combinaisons différentes, sauf la dernière... à suivre !!

[Zavonen]

J'ai pu seulement réfléchir à une heuristique.
Ne considérer d'abord que S,P,C et oublier totalement V
Pour ces trois là il n'y a que 512 possibilités distinguables.
On peut donc commencer par faire le ménage en interprétant qu'il ne réagissent pas et en écrémant à chaque fois. On doit alors arriver à un nombre de solutions possibles stationnaire.
A ce stade, il faut développer les possibles chaque 5-uples donnant naissance, non pas à 120 mais à 10 possibilités.
On reprend alors l'écrémage en faisant entrer en jeu V.
C'est juste une idée.
A+

[ol9245]

on ne peut pas trouvr abcde individuellement car leur permutation donne le même résultat à toutes les opérations.
Si je réduis l'énoncé à chercher l'ensemble {a b c d e} cad aux permutations près, alors au 1er tour on élimine toutes les combinaisons qui ont exactement 120 possibilités dans S, P, C ou V (il y a moins de permutations pour V). de fil en aiguille, on élimine les combinaisons qui ont jusqu'à 23*120 réalisations pour S,P,C ... c'est vrai que V est différent. ou faut-il couper ?

Peut-être que après avoir élinimner tout ça, V permetta de résoudre au moins abc d'un côté et de de l'autre mais de toutes façon on ne saura pas qui est a b c parmi ces 3, ni qui est d e parmi ces deux.

...

bon, ben je vous laisse. je pars pour 10 jours sans Internet (ou presque). A Bientôt.

[pseudocode]

5 inconnues et 5 equations... ca parrait réalisable

Le seul probleme etant d'ecrire mathematiquement la derniere equation: "au bout de 23 essais, on peut résoudre les 4 autres equations".

je cherche...

[Nemerle]

La remarque de Zavonen concernant Pour la science est juste: en particulier dans le pour la science en français de ce mois-ci, vous trouverez un article de Delahaye sur ce problème!

[fumidu]

Soit 5 nombres distincts a,b,c,d,e compris entre 1 et 10.
Serge en connait la somme
Pierre en connait le produit
Corinne en connait la somme des carrés
Valérie connait la valeur v=(a+b+c)(d+e)

Je viens de finir de lire le dernier ******* (un magasine, indice : ce n'est pas Closer ) , ou j'ai trouvé quasiment la même énigme. La seule différence est qu'ils rajoutent l'hypothèse :
a < b < c < d < e
Ca ne change pas grand chose au raisonnement, mais ça change le nombre de quintuplets à considérer au départ !
Et maintenant, motus !

ps : confirmerais-tu, Nemerle, avant que j'envoie tout le monde dans une impasse ?

[Nemerle]

La seule différence est qu'ils rajoutent l'hypothèse :
a < b < c < d < e

je confirme bien sûr, mais CE N'EST PAS UNE HYPOTHESE supplémentaire!!!

Quand j'ai dit "5 nombres distincts", c'est à vous de fixer votre notation: a < b < c < d < e, ou a > b > c > d > e, où comme vous voulez !!!

[fumidu]

Sauf erreur de ma part, il me semble que si, c'est une hypothèse en plus, à cause de v=(a+b+c)(d+e)
Les nombres tous distincts, mais ne sont pas forcement permutables !
a < b < c < d < e entraine 1 <= a <= 6
alors que
a > b > c > d > e entraine 5 <= a <= 10

(n'hésitez pas à me dire si je devrais plutôt me mettre à la broderie ! je ne suis pas très bien réveillé ce matin)

[Nemerle]

Là tu me sèches , tu as entièrement raison!

C'est vrai, je n'aurais pas du écrire (a+b+c)(d+e), c'était de la fénéantise: j'aurais du écrire " la somme de 3 de ces nombres multiplié par la somme des 2 autres"... mais c'était plus long

[fumidu]

Dans ce cas, il me semble qu'il faut bien préciser les hypothèses de départ :
Soit on prend 5 nombres distincts compris entre 1 et 10, et on dit que Valerie connait le produit de la somme de trois d'entre eux par la somme des deux autres.

ou

On prend 5 nombres distincts compris entre 1 et 10, on les ordonne et on dit que Valerie connait le produit de la somme des 3 plus petits par la somme des 2 plus grands.

Les deux cas ne sont pas pareils il me semble.
Je propose de rester sur a < b < c < d < e et v = (a+b+c)*(d+e)

[Zavonen]

Résumons ...
On cherche (a,b,c,d,e) avec 1<=a<b<c<d<e<=10
le nombre des possibilités est 252 (corrigé)
Pour chaque 5-uple le calcul des fonctions S,C,P ne donne qu'une valeur quel que soit l'ordre.
Pour V, par contre c'est plus compliqué, il y a 10 valeurs possibles
donc il y a bien pour tout 5-uple x=(a,b,c,d,e)
S(x)
C(x)
P(x)
V1(x) V2(x) ........V10(X) (les 10 possibilités de V(x)
On peut donc remplir un tableau à 2 dimensions
l'indice i correspond à un 5-uple xi
l'indice colonne correspond à cela:
colonne 0: S(xi)
colonne 1: C(xi)
colonne 2: P(xi)
colonne 3: V1(xi)
....................
colonne 12:V10(xi)
Le processus d'élimination:
S peut répondre dans le cas d'un indice ligne où la valeur correspondante dans la colonne 0, n'intervient qu'une seule fois
Idem pour C et P.
Pour le pauvre V les choses sont plus complexes...
Il doit examiner la valeur qu'il connait, la factoriser de toutes les façons possibles en produit de 2 facteurs pq et il sort
quand il peut trouver un unique xi
tel que p soit somme de deux composantes qcq et q des 3 autres
L'application à répétition de l'écrémage sur S,C et P simultanément conduit en 5 itérations à 120 candidats possibles (non négligeable)
A ce niveau on se trouve avec une matrice de 120 lignes et 12 colonnes, et le processus d'élimination de V consiste à rechercher sa valeur dans une ligne entre les colonnes 3 et 12. Si cette valeur ne se retrouve dans aucune autre ligne il a trouvé.
J'ai mis tout cela en oeuvre, malheureusement j'arrive à un système stationnaire où je ne peux plus éliminer de lignes parce que le cas de figure décrit auparavant ne se produit pas.
Donc je sèche ...
Soit l'analyse n'est pas bonne, soit mon pgm est ....dique

[fumidu]

Je ne trouve que 252 quintuplets au départ, soit C(10,5). Comment tu arrives à 512 ?
Et si on reste sur v = (a+b+c)*(d+e), il n'y a qu'une seule valeur de v, ce qui est nettement plus simple à manipuler, non ?

[Zavonen]

Oui bien sûr 252 et non pas 512 ...comme je l'avais dit dans mon premier post.

[Nemerle]

Zavonen, peux-tu expliquer ces dix valeurs de v?

Pour moi, en prenant l'exemple de v, Valérie a reçue une valeur numérique; elle doit regarder fval^(-1)(v) où fval est la fct (a,b,c,d,e)-->(a+b+c)(d+e). Elle n'arrive pas à conclure, donc fval^(-1)(v) a plus d'un élément.

Par exemple, 54 est une valeur possible, car 54=(1+2+3)(4+5)=(1+3+5)(2+4); par contre on est sûr que v<>264, car 264=(7+8+9)(6+5) et pas autrement.

Pour nous, l'étape 1 consiste à déterminer toutes les valeurs possibles de v (et s,p,c aussi), avec prise en compte de la condition a<b<c<... lors de la détermination de fval^(-1)(v). Disons que c'est l'ensemble V1.

Soit les fct Som(a,b,c,d,e)=a+b+c+d+e, Prod(a,b,c,d,e)=abcde, Car(a,b,c,d,e)=aa+bb+cc+dd+ee.

A l'étape suivante, il faut ôter les v vérifiant l'une des 3 conditions suivantes:
- pour tout (a,b,c,d,e) de fval^(-1)(v), Som^(-1)(a+b+c+d+e) est de cardinal 1
- pour tout (a,b,c,d,e) de fval^(-1)(v), Prod^(-1)(a+b+c+d+e) est de cardinal 1
- pour tout (a,b,c,d,e) de fval^(-1)(v), Car^(-1)(a+b+c+d+e) est de cardinal 1

............