Rectangle interdit

Enoncé du problème

Sur une grille n x n, on noircit k des n² cases de telle sorte que 4 des k cases choisies ne soient jamais les sommets d'un rectangle ayant ses côtés parallèles à ceux de l'échiquier. Quelle est la plus grande valeur de k pour laquelle ceci est possible ?

Solution admissible		Solution non admissible

Premier algorithme

1. Déterminer une case x au hasard.
2. Si la case x est noire, la rendre blanche. Aller à 4.
3. Si la case x n'est pas noire, la noircir après avoir vérifié qu'elle n'est pas le quatrième coin d'un rectangle.
4. Calculer le nombre de cases noires et garder le meilleur résultat obtenu en mémoire.
5. Retourner à 1.

Second algorithme

1. Poser p=1.
2. Déterminer une case x au hasard.
3. Si la case x est noire, la rendre blanche avec une probabilité p. Aller à 5.
4. Si la case x n'est pas noire, la noircir après avoir vérifié qu'elle n'est pas le quatrième coin d'un rectangle.
5. Calculer le nombre de cases noires et garder le meilleur résultat obtenu en mémoire.
6. Diminuer la probabilité p.
7. Retourner à 2.

Exercice

Programmez les algorithmes décrits ci-dessus dans Mathematica et comparez leur efficacité. Pour n=7, la valeur maximale de k est 21. Fonctions Mathematica utiles: For, Graphics, If, Module, Print, Random, RandSeed, Show, Raster.

Didier Müller, 28.12.06