Mathématiques avec Python et Ruby/Freudenthal sous Ruby

Le problème de Freudenthal est intéressant à traiter en Ruby parce qu'il peut se résoudre en manipulant des tableaux et ensembles et que pour Ruby, les tableaux peuvent se manipuler comme des ensembles et vice-versa. Le problème est d'ailleurs intéressant en soi parce qu'il porte sur la logique épistémique. En voici l'énoncé traduit du Néerlandais à l'Anglais puis au Français:

Énoncé

On choisit au hasard deux entiers x et y strictement supérieurs à 1, x étant le plus petit des deux, et on donne à Sam leur somme qui est inférieure à 100, et à Polly leur produit. Après un temps de réflexion suffisamment long, le dialogue suivant se déroule entre Sam et Polly:
Polly: Je ne sais pas qui sont x et y.
Sam: Je savais que tu ne savais pas!
Polly: Alors je sais qui sont x et y.
Sam: Alors je sais aussi!

Le but du problème est donc d'utiliser les connaissances qu'on a sur les connaissances de Polly et Sam pour savoir si on peut savoir quels sont x et y.

Il y a de nombreuses méthodes pour y arriver, et Ruby est en quelque sorte un langage "multiparadigme" où chacun peut utiliser sa propre logique (épistémique ou non) pour aborder le problème.

Digression arithmétique

Si on avait confié un nombre premier à Polly, elle n'aurait pas avoué son impuissance lors de sa première affirmation. Bien que ce ne soit nullement nécessaire pour résoudre ce problème, Ruby sait depuis la version 1.9 manipuler des nombres premiers. Avec

puts(Prime.prime?(p))

on peut savoir si p est premier, et avec

puts(Prime.prime_division(n))

on décompose n en facteurs premiers.

Les produits à partir des sommes

Plutôt que de manipuler des couples d'entiers x et y possibles, on va, comme dans la version Python, manipuler l'ensemble des produits possibles. Donc on aura besoin de l'outil permettant, à partir d'une somme s donnée à Sam, d'obtenir la liste prod(s) des produits donnés à Polly qui correspondent aux mêmes x et y:

def prod(n)
    t=[]
    (2..n-2).each{|x| t.push(x*(n-x))}
    return t.uniq
end

On peut décrire l'algorithme ci-dessus ainsi:

On crée un tableau vide t
Pour chaque nombre entre 2 et n-2, noté provisoirement x, on rajoute le produit de x par son complément à n dans le tableau t
Quand on a fini, on transforme t en ensemble, en enlevant les doublons.

Première affirmation

L'affirmation apporte une information: Le produit donné à Polly peut s'obtenir de plusieurs manières, sinon Polly connaîtrait les facteurs. Pour exploiter cette information, on va commencer par fabriquer l'énorme liste des produits possibles, puis ne garder que ceux qui apparaissent au moins deux fois dans la liste:

On ramasse les y entre 3 et 100; pour chacun d'entre eux on ramasse (collect) les x entre 2 et y-1; si la somme x+y est inférieure ou égale à 100, on rajoute le produit dans le tableau produit. Ensuite on constitue pour chaque p de ce tableau, l'ensemble des k égaux à p dans le tableau. Si cet ensemble contient un seul élément, on l'enlève (reject) du tableau des produits:

produits=[]
(3..100).collect{|y| (2..y-1).collect{|x| if x+y<=100 then produits.push(x*y) end}}


polly=produits.reject{|p| (produits.select{|k| k==p}).size<2}
puts(polly.size)

Ah oui! Il y en a beaucoup qui restent!

Deuxième affirmation

Si Sam sait que Polly ne sait pas, c'est parce que quelle que soit la décomposition en somme d'entiers de celui qu'on lui a dicté, le produit correspondant est dans la liste précédente. Sinon elle eût pu savoir qui sont x et y, pour ce que Sam en sait! Sam ne va donc garder que les sommes n pour lesquelles la liste prod(n) calculée avec la fonction ci-dessus ne contient que des éléments de la liste polly, donc si leur intersection est égale à prod(n) (en effet $A\subset B\Leftrightarrow A\cap B=A$ dans l'algèbre de Boole des ensembles):

sam=(4..100).select{|s| prod(s)&polly==prod(s)}
puts(sam)

Il reste plutôt peu de sommes possibles:

11	17	23	27	29	35	37	41	47	53

On sait ce que Sam sait, mais Sam dit "Ça me suffit pas encore!", et nous aussi!

Troisième affirmation

Si Polly sait maintenant quels sont x et y, c'est que parmi les sommes ci-dessus, il n'y a pas que des doublons (produits communs à plusieurs sommes). Il y a un produit propre à une des sommes de Sam ci-dessus. Pour en savoir plus, Polly va constituer pour chacun des 10 nombres s ci-dessus, la liste de ses produits prod(s), puis chercher tous les nombres communs à au moins deux de ces 10 listes (les doublons). Ruby peut en faire de même, mais après avoir aplati le tableau des prod(s) (qui est un tableau à deux dimensions), et en plaçant dans la liste des doublons, tous les nombres qui apparaissent plus d'une fois dans le tableau des produits:

produits=sam.map{|s| prod(s)}
listeprods=produits.flatten

doublons=listeprods.select{|p| (listeprods.select{|k| k==p}).size>1}

Ensuite Polly enlève à chaque liste de produits des sommes de sam, les doublons (par une soustraction d'ensembles), et en comptant le nombre d'éléments de chacun des ensembles obtenus,

produits.each{|p| puts((p-doublons).size)}

Polly constate effectivement la présence d'un et un seul singleton:

11	17	23	27	29	35	37	41	47	53
3	1	3	9	9	10	7	13	13	18

Quatrième affirmation

Puisque Sam sait aussi sa somme, on sait que sa somme est 17 et le produit de Polly, 52:

puts(sam[1])
puts(prod(17)-doublons)

À la recherche des x et y perdus

Maintenant qu'on connaît la somme et le produit de x et y, il reste à déterminer ceux-ci, ce qui peut se faire en résolvant l'équation du second degré $x^{2}-17x+52=0$ ou par une double boucle:

(3..100).collect{|y| (2..y-1).collect{|x| if x+y==17 and x*y==52 then puts(x,y) end}}

Les inconnues x et y sont maintenant connues!