Posts Tagged ‘solution’
Résoudre une énigme, solution au problème de Freundenthal en 7 points
décembre 9, 2008La semaine dernière, je vous ai parlé du problème de Freundenthal (lire l’article). J’espère que vous avez apprécié la complexité du problème et particulièrement la première citation de Syvie. Voici une solution possible du problème avec SAS.
Rappel : Les données du problème
On choisit deux entiers X et Y, avec 1 < X < Y et X + Y <= 100.
On indique à Patricia le produit P de X et Y.
On indique à Sylvie la somme S de X et Y.
Le dialogue est alors le suivant :
Patricia : ”Je ne sais pas quels sont les nombres X et Y.”
Sylvie : ”Je savais que vous ne connaissiez pas X et Y.”
Patricia : ”Eh bien alors, maintenant, je connais X et Y.
Sylvie : ”Eh bien, moi aussi je les connais maintenant.”
1. Générer un data set contenant toutes les combinaisons de base possible
On choisit deux entiers X et Y, avec 1 < X < Y et X + Y <= 100.
On indique à Patricia le produit P de X et Y.
On indique à Sylvie la somme S de X et Y.
data step1; do x=2 to 49; do y=3 to 98; p=x*y; s=x+y; if x+y =<100 and x<y then output; end; end; run;
Le minimum pour x est 2 et pour y est 3 : Sachant que le plus petit nombre doit être strictement supérieur à 1 et que y doit être strictement supérieur à x, la valeur de x est au minimum 2 et celle de y est au minimum 3.
Le maximum pour x est 49 : Sachant que la somme de x et y ne peut pas dépasser 100 et que x doit être toujours strictement inférieur à y, la valeur de x est au maximum 49.
Le maximum pour x est 98 : Sachant que la somme de x et y ne peut pas dépasser 100 et que la plus petite valeur de x est 2, la valeur maximale de y=98.
Au final, on se retrouve avec 2352 combinaisons possibles.
2. Comprendre la première phrase de Patricia
Patricia nous dit : « Je ne sais pas quels sont les nombres x et y ».
En d’autres termes le produit connu par Patricia est calculable de plusieurs manières.
Si un produit est calculable de plusieurs manières, Patricia ne peut pas savoir quelles sont les valeurs de x et y.
Exemple où Patricia pourrait utiliser sa phrase : Si Patricia avait p=20, il y aurait deux solutions possibles x=2, y=10 et x=4, y=5.
Exemple où Patricia ne pourrait pas utiliser sa phrase : Si Patricia avait le nombre p=27, elle saurait les valeurs de x et y, à savoir x=3 et y=9.
3. Interpréter en SAS la première phrase de Patricia
Ici sont extraites toutes les combinaisons de x et y pour lesquelles un produit apparaît plusieurs fois. On se retrouve avec 574 combinaisons.
proc sql; create table patricia_1 as select * from step1 group by p having count(*) gt 1; quit;
4. Comprendre la première phrase de Sylvie
Sylvie nous dit : ”Je savais que vous ne connaissiez pas X et Y.”.
Pour expliquer cette phrase de Sylvie, je vous propose de passer par un exemple. Supposons que la somme de x et y connue par Sylvie est égale à 12 (s=12).
Cette somme est calculable à partir de plusieurs combinaisons : 2+10, 3+9, 4+8 et 5+7. Pour chacune de ces combinaisons, on obtient les produits suivants : 20, 27, 32 et 35.
- Pour obtenir le produit 20, Patricia a 2 possibilités : 4*5 et 2*10.
- Pour obtenir 27, il y a également 1 possiblité : 3*9.
- Pour obtenir 32, il y a 2 produits possibles : 2*16 et 4*8
- Enfin pour obtenir 35, il y a 1 possiblité : 5*7
Il faudrait que les 4 produits puissent s’obtenir avec plusieurs combinaisons pour faire partie des réponses possibles.
Parmi toutes les x et y qui donnent le nombre s, tous forment un produit calculable d’une autre manière.
5. Interpréter sous SAS de la citation de Sylvie
L’interprétation de la citation se fait en quatre étapes :
- Pour chaque somme, trouver tous les produits possibles.
- Ajouter à chaque produit toutes les autres combinaisons donnant le même produit.
- Savoir pour chaque combinaison de somme, le nombre de produits associés
- Ne prendre que les sommes où tous les produits sont calculables d’au moins deux manières.
Etape 1 : La première étape est notre data set STEP1 généré précédemment.
Etape 2 : Une combinaison MANY-TO-MANY
Chaque somme peut apparaître plusieurs fois dans le data set STEP1 car il peut y avoir plusieurs manières de l’obtenir. Dans la précédente section, on a vu qu’il y avait 4 combinaisons de x et y pour obtenir la somme 12.
Chaque produit peut apparaître plusieurs fois dans le data set STEP1 car il peut y avoir plusieurs manières de l’obtenir. Dans la précédente section, on a vu qu’il y avait 2 combinaisons de x et y pour obtenir la le produit 20 et une seule pour obtenir le produit 27.
Il s’agit donc de faire un merge many-to-many du data set STEP1 par lui même. On passe alors à 7006 lignes d’observations.
Prenont la ligne où s=12, x=2, y=10 pour exemple. Le produit qu’elle renvoie est calculable de 2 manière différente. C’est à dire qu’il y a une autre somme qui donne le même produit. Il s’agit de s=9 quand x=4 et y=5. Il faut donc doubler l’information pour chacune de ces sommes.
STEP1 STEP1 s s_x s_y p p p_x p_y 12 2 10 20 20 2 10 9 4 5 20 20 4 5
Au final on voudrait :
STEP2 s s_x s_y p p_x p_y 12 2 10 20 2 10 12 2 10 20 4 5 9 4 5 20 2 10 9 4 5 20 4 5
En SAS, cela donne :
proc sql; create table step2 as select a.*, px, py from step0 a, (select x as px, y as py, p from step1) b where a.p=b.p; quit;
Imprimez le résultat pour p=20 et vous verrez qu’on obtient la réponse attendue.
Etape 3 : A présent, il s’agit de savoir pour chaque combinaison de somme et produit, le nombre d’occurences.
proc sql; create table step3a as select *, count(*) as cnt from step3 group by s, p; quit;
Lorsque s=12, on obtient :
x y p s px py cnt 2 10 20 12 2 10 2 2 10 20 12 4 5 2 3 9 27 12 3 9 1 4 8 32 12 2 16 2 4 8 32 12 4 8 2 5 7 35 12 5 7 1
Au lieu de sélectionner toutes les observations, on peut se contenter de S, X, Y, P et la variable CNT. On a alors nos 2352 lignes d’origine.
proc sql; create table step3b as select distinct s, x, y, p, count(*) as cnt from step3 group by s, p; quit;
Pour s=12, on a :
s x y p cnt 12 2 10 20 2 12 3 9 27 1 12 4 8 32 2 12 5 7 35 1
Etape 4 : La dernière étape concernant la première citation de Sylvie consiste à identifier les sommes où tous les produits associées sont calculables d’au moins deux manière.
Dans l’étape data qui suit, j’ai choisi de passer par un compteur. Ce compteur est représenté par la variable FLAG. Il est réinitialisé pour chaque nouvelle somme (variable S). Si SAS rencontre une fois la valeur CNT=1, le compteur est incrémenté. Pour la dernière observation de la somme
data step4 (keep=s); set step3b; by s; if first.s then flag=0; if cnt=1 then flag+1; if last.s and flag=0 then output; run;
Le data step STEP4 contient 10 observations.
s 11 17 23 27 29 35 37 41 47 53
Il est donc ensuite de se concentrer sur la troisième phrase du dialogue.
6. Patricia : « Eh bien alors, maintenant je connais X et Y »
Sachant p, et sachant que s ne peut être qu’une des 10 valeurs trouvées dans l’étape 4 (STEP4), Patricia est capable de trouver quelle combinaison est la bonne. On en conclut que parmi les possibilités extraites dans le data set PATRICIA_1, il ne faut garder que celles où S n’apparaît qu’une fois pour un P donné.
proc sql; create table patricia_2 as select * from patricia_1 where s in (select s from step4) group by p having count(*)=1; quit;
On se retrouve avec 86 observations.
7. Sylvie : « Eh bien moi aussi je les connais maintenant »
Si parmi les resultats restant, Sylvie est capable de trouver la réponse c’est parce qu’il ne reste plus qu’une valeur possible de P pour la somme dont elle a la connaissance.
A partir du data set PATRICIA_2, on extrait les observations où la valeur de S n’apparaît qu’une fois.
proc sql; select x, y, s, p from patricia_2 group by s having count(*)=1; quit;
Seul un cas est extrait. Dès lors, la réponse à l’énigme de Freundenthal est x=4 et y=13.
x y s p 4 13 17 52
La référence SAS 