- Quand: 8 juillet 2021 à 13h, en replay sur https://www.youtube.com/watch?v=uOW3HpsTuGY.
- Intrigue: Dans ce Café-in, vous allez apprendre deux jeux/énigmes amusant(e)s (j’espère) auxquels vous pourrez jouer avec vos familles et amis.
- Etant donné un échiquier, sauriez vous couvrir toutes ses cases à l’aide de dominos, exceptées celles de deux coins opposés ?
- Considérons un échiquier classique (8 cases par 8) dont chaque case peut être soit saine soit infectée. Supposez que, si au moins 2 des 4 voisins d’une case infectée sont saines, alors la case infectée devient saine. Quel est le nombre minimum de cases qui doivent être saines initialement pour éradiquer complètement l’infection de l’échiquier ? Vous pouvez tester ce jeu ici : https://scratch.mit.edu/projects/517390361/
A travers ces jeux, nous discuterons de questions importantes dans le travail des chercheurs comme « y a t-il une solution ? », « combien y a-t-il de solutions ? », « est-ce que cette solution est optimale ? » … Précisément, je répondrai à ces questions dans le cas des deux jeux proposés en présentant de très belles preuves de la littérature (oui, des preuves peuvent être « belles »: élégantes et simples). Pour finir, je présenterai une généralisation du second problème et montrerai brièvement ses relations avec le jeu de la vie de John Conway qui, malgré des règles très simples, permet de simuler n’importe quel ordinateur.
- Biographie: Nicolas Nisse est CR Inria dans l’équipe COATI. Ses sujets de recherche portent sur l’algorithmique des graphes avec des applications dans les réseaux de télécommunication, routiers, sociaux… En particulier, son travail s’appuie sur la théorie des jeux combinatoires dans les graphes. Nicolas Nisse est ingénieur Supélec, a effectué sa thèse à l’université Paris-Sud 11 puis un postdoc à l’université du Chili (Santiago, Chili) et un postdoc dans l’équipe Mascotte (devenue COATI). Il est également membre de Terra Numerica.
- En savoir plus sur MASTIC et C@fé-in.
Category: Popularization
Le défi des 1001 graphes
An article by Nathann Cohen and David Coudert, entitled Le défi des 1001 graphes, has been published in Interstices (in french). It relates our approach to address (and win) the Flinders Hamiltonian Cycle Problem (FHCP) Challenge organized by the Flinders Hamiltonian Cycle Project (Flinders University, Adelaide, Australia).
Le défi des 1001 graphes
An article by Nathann Cohen and David Coudert, entitled Le défi des 1001 graphes, has been published in Interstices (in french). It relates our approach to address (and win) the Flinders Hamiltonian Cycle Problem (FHCP) Challenge organized by the Flinders Hamiltonian Cycle Project (Flinders University, Adelaide, Australia).