Défi Turing : 180 exercices de programmation

Accueil

- Inscription - Enoncés -

Qu'est-ce que le Défi Turing ?

Le Défi Turing est une série d'énigmes mathématiques qui pourront difficilement être résolues sans un programme informatique. Attention ! Votre programme devra trouver la réponse en moins d'une minute !
Un nouveau problème sera proposé chaque dimanche. Pour en savoir plus, consultez la FAQ.

Problème 180 : La contagion

Au début (étape 0), avant de lancer un programme informatique, on « contamine » un certain nombre de cases d'une grille 5×7.
Ensuite, l’ordinateur simule une contagion.
Étape après étape, chaque case non contaminée adjacente par un côté à exactement deux cases contaminées est contaminée à son tour (les contaminées le restent, malheureusement !).
Il existe une jolie démonstration* du fait qu’il faut « contaminer » au minimum 6 cases non adjacentes deux à deux au début pour que les 35 cases de la grille puissent être contaminées après un certain nombre d’étapes.
Dans ce cas, une contamination totale – si elle se produit – a nécessairement lieu en au plus 29 étapes.

Exemple


La grille ci-dessus permet une contamination totale en 10 étapes.
Soit N(k) le nombre de grilles de départ ayant exactement 6 cases non adjacentes contaminées, et amenant à une contamination totale en k étapes.

Que vaut la somme des k x N(k), pour k = 1, ..., 29 ?

* On peut facilement se convaincre que durant le processus de contamination, le périmètre total de la zone contaminée est invariant. Le périmètre de la grille étant de 24 et celui d’une case de 4, il faut donc au moins 24/4 = 6 cases (non adjacentes) pour aboutir à une contamination complète.

Le problème 181 sera mis en ligne le 02/10/2016, à 0h00.

A qui s'adresse ce défi ?

Ce défi est destiné aux programmeurs débutants et aux amateurs d'énigmes mathématiques.

Comment participer ?

Pour suivre votre progression dans le classement, inscrivez-vous pour rejoindre les 566 membres actuels. Seuls les membres pourront laisser des commentaires sur les problèmes qu'ils auront résolus, et comparer leurs solutions.
Il est cependant possible de voir tous les problèmes sans s'inscrire, mais alors vous ne pourrez pas proposer de réponse et vous ne participerez donc pas aux classements.

Connexion à l'espace membre

Identifiant :
Mot de passe :

 



Didier Müller
31.12.12