Ok

En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies. Ces derniers assurent le bon fonctionnement de nos services. En savoir plus.

17/03/2014

Candy maths

Difficile d’ignorer Candy Crush, difficile de ne pas y jouer et encore plus difficile de ne pas tomber dans l’addiction. C’est un jeu de bonbons virtuels. Il semble bien que ce jeu séduise plus les femmes que les hommes. Téléchargeable gratuitement sur smartphones, tablettes et Facebook, Candy Crush était joué 700 millions de fois chaque jour dans le monde en décembre dernier.

candy-crush.jpg?w=1024&h=812

Le problème semble simple, il suffit d’aligner le plus de bonbons par 3, 4 ou 5. Chaque mouvement change la configuration du jeu, il faut donc anticiper les alignements futurs et c’est ici que l’on tombe sur un sacré problème de math. Un chercheur australien a démontré que ce problème est de la classe des problèmes NP-complets donc très complexes.

Toby Walsh, le chercheur australien a étudié le jeu et découvert qu'il faisait partie d'une classe de problèmes mathématiques dits NP-difficiles et que si on ne limitait pas la taille du tableau de bonbons ce problème devient NP-complet.

Je n’entrerai pas ici dans l’explication sur les problèmes P et NP, disons que les NP-Complets sont des problèmes aux solutions difficiles à trouver mais faciles à prouver. On peut citer, le problème du voyageur de commerce, Les problèmes de coloration de graphe, le problème du sac à dos

Walsh se demande s'il serait possible de tirer profit du temps que les gens passent à résoudre les problèmes de Candy Crush. Les adeptes cumulent plusieurs millions d'heures de jeu. Peut-être pourrait-on en profiter pour glisser quelques problèmes NP-difficiles concrets au milieu du jeu et ainsi faire avancer les mathématiques sur un des problèmes à 1 million de dollars.

Commentaires

NP-complet ç'est dur à digérer. Avec moi, le son ne passe pas.

Écrit par : Pop | 18/03/2014

J'en profite pour signaler le dernier prix Turing
http://lefenetrou.blogspot.fr/2014/03/le-prix-turing-2013-est-decerne-leslie.html

Quant aux jeux "vidéo" je ne sais pourquoi, mais je n'y ai aucun goût.

Écrit par : Aredius | 25/03/2014

Salut Aredius,
Finies les vacances de ski ? Pas trouvé le théorème de Quimper.

Écrit par : Joël | 25/03/2014

Est-ce que tu as essayé 2048 ? Je ne sais pas s'il est NP-Complets mais il est tout aussi addictif! Des chiffres en plus ça devrait te plaire!

Écrit par : Gaëlle | 26/03/2014

Aussitôt dit aussitôt fait... Du coup on se couche à point d'heure...

Écrit par : Joël | 27/03/2014

J'ai essayé candy machin... Perte de temps et finalement pas si addictif que ça, je ne dois pas faire partie du troupeau.
Après quelques jours je l'ai viré...
Se coucher à point d'heure pour ça, non merci LOL

Écrit par : Françoise | 02/04/2014

Les commentaires sont fermés.