OCamlPro remporte le concours FreeTON sur les Zk-SNARKs!

Le mois dernier, nous avions participé à un concours d’idées et d’implémentations de use-cases des zk-SNARKs sur la blockchain FreeTON. Nous avons le grand plaisir d’annoncer qu’OCamlPro a obtenu la première place à ce concours!

Anecdote mathématique et problème pour nos lectrices et lecteurs

Pour le use-case des Sudoku (de taille 4 dans notre implémentation), j’avais choisi d’encoder et de tester l’unicité de chacun des nombres présents dans une colonne, une ligne ou une boîte par la propriété que x + y + z + t = 1 + 2 + 3 + 4 = 10 et le produit x · y · z · t = 1 · 2 · 3· 4 = 4! = 24. Il est vrai que si x,y,z et t sont des entiers entre 1 et 4, alors les ensembles { x, y, z, t } et {1, 2, 3, 4} sont égaux. Qu’en est-il pour le Sudoku de taille 9? Peut-on se contenter de dire que la somme des 9 entiers vaut 45 et que leur produit vaut 9! pour garantir que ces 9 entiers entre 1 et 9 sont distincts?

J’ai écrit un programme pour chercher des contre-exemples, pour les premières valeurs de n (ce calcul ferait au passage un bon Project Euler!) et j’ai découvert que l’unicité de la solution est vraie jusqu’à n=8, et qu’il existe exactement un contre-exemple pour n=9 (et de plus en plus pour n plus grand). Je propose donc un petit défi pour nos lecteurs et lectrices: saurez-vous trouver ce contre-exemple de x_1, x_2, ..., x_9 de somme 45 et de produit 9! (9 factoriel)? Question bonus: Quel est le plus grand entier n pour lequel vous parvenez à calculer tous les contre-exemples en moins d’une minute?