1) Quel que soit la grille de depart, le résultat final est toujours une série de rectangles (qui peuvent etre carrés ou meme juste uni-cellulaire, séparé par au moins 2 cases blanches dans toutes les directions.

2) pour un état final d'un rectangle de a*b par example, il suffit de commencer par une série de cellules (1,0,1,0,1,0,1) sur 2 cotés contigus. (0=morte, 1=vivantes):
- a/2 +1 sur un coté
- b/2 +1 sur l'autre
- et -1 parce que le coin est commun.
On peut aussi placer les cellules en diagonale pour commencer et en pointillé pour finir le coté le plus long.

En regle generale on a besoin de int(a+b+1)/2 cellules de depart, pour chaque rectangle final.

Salut Ebichu,

Tant que la partie connexe n'est pas convexe, on peut la compléter jusqu'au convexe, c'est à dire un rectangle.

En partant d'une unique cellule, formant un rectangle (L,l)=(1,1) on peut l'agrandir par une cellule disposée à une case blanche de distance, et qui donnera (L+2,l) ou (L,l+2).

Pour obtenir un rectangle impair (L,l) il faudra donc n=(L+1)/2 + (l-1)/2=(L+l)/2 cellules.
Pour un rectangle pair, ajouter 1 cellule.

En fait, on peut disposer les cellules sur le demi périmètre du rectangle à obtenir, de sorte qu'on puisse toujours sauter d'une cellule à la suivante en passant par une seule case blanche (horizontale ou verticale). Ou alors les poser en diagonale.

@nodgim : je suis d'accord avec ta première phrase, mais comment la démontrer ? De plus, l'état final n'est pas forcément connexe : dans ce cas, quelle est sa forme ?

Pour la question 2), ta méthode démontre que ce nombre est suffisant. Mais pourquoi est-il nécessaire ?

@masab : je ne suis pas tout à fait d'accord avec la première partie de phrase que tu mets en gras. Il faut préciser : quand je regarde les deux parties noires de droite sur ton exemple, je ne vois pas les 2 cellules dont tu parles.

La preuve que tu donnes est insuffisante pour que je comprenne : qu'appelles-tu "local", et comment passer du local au global ?

Le reste est intéressant... mais hors-sujet. Par contre tu ne réponds pas à la question 2.

@tous : l'intérêt de l'énigme ne réside pas seulement dans l'observation de ce qui se passe, ce qui n'est pas si difficile, mais dans sa démonstration. Attention, je serai pointilleux Ça en vaut néanmoins le coup : il y a au moins un raisonnement qui est simple, élégant et difficile à trouver.

Effectivement il y a une erreur dans ma rédaction : il faut rectifier en
2 rectangles quelconques devant être distants d'au moins 2 cellules mortes
c-à-d
pour passer d'un rectangle à l'autre par une suite de cellules on doit passer sur au moins 2 cellules mortes (2 cellules consécutives doivent avoir un côté commun).

En ce qui concerne le bord :
appelons petit segment le côté d'une cellule ;
dans un état final, 2 petits segments consécutifs du bord doivent
* soit être alignés
* soit formé un angle droit, à l'intérieur duquel on a une cellule vivante
C'est ce que j'appelle propriété locale du bord.
Ceci entraîne que l'état final est un limité par un polygône convexe.
Ce ne peut être qu'un rectangle.

Il me reste effectivement la question 2.
Il suffit de la résoudre pour un rectangle axb (a cellules horizontalement, b cellules verticalement). On note n le plus petit entier >= (a+b)/2.
Alors n cellules vivantes bien choisies admettent ce rectangle pour état final.
Et on ne peut mieux faire...

Bonjour

Le problème est assez facile à dévisser par tâtonnement .

On appelle distance entre deux cellules la distance Manhattan entre leurs centres et distance entre deux figures la plus petite distance entre deux cases des deux figures .

Les états finaux sont les réunions de rectangles distants de plus de 2 .

Le nombre de cellules nécessaires pour envahir un rectangle mXn est E((m+n+1)/2) .

On peut facilement construire une position initiale possible en plaçant une cellule sur chaque case d'une bissectrice et de rajouter une cellule une case sur deux sur la longueur où arrive la bissectrice .

On ne peut pas faire mieux , en effet le périmètre de la figure ne varie pas durant la prolifération .

Vasimolo

En effet le périmètre peut diminuer quand il y a une case à l'intérieur , heureusement ça ne change rien à la conclusion

Pour la première partie , toute case entre deux cellules distantes de 2 doit être envahie , ce qui ne laisse aucune place à un angle rentrant .

Vasimolo

Sur un quadrillage , c'est assez évident , non ?

Vasimolo

Je n'ai rien contre les démonstrations un peu pointues , au contraire

On peut dessiner un polygone qui n'est pas un rectangle sans angle rentrant et dont les côtés suivent les lignes d'un quadrillage ?

Il faudrait aussi expliquer pourquoi chaque rectangle ne peut pas être troué , pour moi c'est clair mais je ne suis pas contre un argument "canon" qui tue le problème 

Vasimolo

Je vois bien une cellule comme un cube sans couvercle et développé: les 4 cases voisines sont donc occupées par les 4 faces latérales du cube. Là où il y a recouvrement de faces, il y a naissance d'une cellule. S'il y a connexité de cellules + faces recouvertes, alors on va pouvoir agrandir ce connexe s'il n'est pas déja convexe, puisque dans un angle rentrant, il y a recouvrement.

Bon je crois quand même qu'il y a un argument canon en faveur des rectangles distants d'au moins 3 . On considère un rectangle maximal dans chaque composante connexe de l'état final . On remarque qu'il ne peut y avoir aucune cellule voisine ou à distance 2 du bord de chaque rectangle ( sinon le rectangle n'est pas maximal ) .



Bref les composantes connexes sont des rectangles .

Vasimolo

Sympa le pb. pas eu trop le temps en vacances malheureusement.

Quelques idées.

Si état final 1 pièce alors c'est un rectangle car c'est la seule figure a angle droit dont la somme absolue des angles est 360° (4 angles droits) et si la figure a plus de 360° il y a au moins un ajout possible car un angle est ouvert

Possible que le résultat final soit plusieurs rectangles séparés par 2 colonnes minimum sur les côtés et dont les sommets sont disjoints.



Pour un rectangle m,p avec p>=m

Il existe k tel que
(K-1)n +k-2 <p <= kn +k-1
Et le minimum initial est kn

Il est trivial que ca suffit car les carrés adjacents se collent

Pas la place de démontrer la réciproque dans la marge du smartphone ... Ca faisait plaisir d'au moins participer à ce problème sympa. .


Pour la réciproque on commence par le cas carré avant de généraliser.Par recurence ca semble clair en remarquant que si le carré de taille n est atteignable ajouter une cellule permet de passer à un carré n+1