Echec N1

[Imod]

Certaines cases d'un échiquier de taille nXn sont atteintes par le terrible virus Echec N1 . Le virus se propage en contaminant toute case partageant au moins deux côtés avec des cases malades . Si après quelque temps tout l'échiquier est atteint , montrer qu'initialement au moins n cases étaient contaminées .



Bon courage :zen:

Imod

[nodgim]

Il faut, en plus, qu'elles soient disposées en diagonale!

[Doraki]

Pas nécessairement en diagonale.
Ni même en permutation.

[Imod]

En effet , quelques exemples :



Imod

[nodgim]

Oui, en effet.... :doh:

[le_fabien]

Là c'est chaud! :hum:

[Doraki]

Comme d'habitude, y'a une preuve à la simplicité surprenante...

[miikou]

doraki : ne serait ce pas demontrer qu'avec cet algo de propagation on obtient tjs un carré de meme coté que le nombre initial de cases contaminées ?

nb : ou alors on reste a letat initial, je precise car jvois que tu repond et je present que tu vas me le faire remarquer ;)

[Doraki]

Euh en toute généralité, t'es pas forcé d'obtenir des carrés.

Si je prends 2 cases contaminées éloignées l'une de l'autre, bah il se passe rien et j'obtiens 2 carrés à la fin. (ah zut, grillé)
Si je prends 2 cases sur une même ligne et séparées par 1seule case, j'obtiens un rectangle 1x3 donc pas un carré.
Si je prends 4 cases toutes comprises dans un carré 3x3, je peux obtenir un carré 3x3 mais pas un carré 4x4.

Si t'avais dit "qu'avec cet algo si on obtient un carré alors c'est un carré de coté <= au nombre de cases contaminées" ben.. c'est juste une reformulation du problème ?

[miikou]

:) je dois pas avoir les idées claires

[nodgim]

Soit un rectangle a*b infecté. Une case infectée supplémentaire bien placée augmente le rectangle de 2 manières différentes:
-Soit (a+2)*b ou a*(b+2)
-Soit (a+1)*(b+1).

Le carré est un cas particulier, qui conduit évidemment à un minimum de n cases infectées pour un carré de coté n.

[Doraki]

Et en augmentant un rectangle avec un rectangle bien placé on peut rien avoir de mieux ?

[Imod]

Bon un petit indice !

Par rapport à la situation initiale , un certain paramètre ne peux que diminuer pour finir à 4n si tout le carré est infecté :we:

Imod

[nodgim]

Et en augmentant un rectangle avec un rectangle bien placé on peut rien avoir de mieux ?

Ben non, tu as un contre-exemple ?

[Patastronch]

Une idée simple (avec 100% de manque de rigueur) :

1/ Deux virus sont connexe (feront parti d'un meme bloc infecté à partir d'une certaine étape) si la distance qui les sépare est de 2 au plus (une diagonale = 2 de distance) ou qu'il existe un chemin de virus connexe les reliant
2/ Un ensemble de virus peut contaminer apres un nombre fini d'étape au plus le rectangle minimum qui les englobe tous.

Avec ces 2 "conjectures" on en déduit que pour tout contaminer il faut au moins un virux dans 2 coins opposées (distance 2n) et qu'ils soient connexe. Pour rendre connexe ces 2 virus il va falloir les relier par d'autre virus soit n-2 virus, ce qui fait un total d'un minimum "théorique" de n virus.

La diagonale comporte n cases et est une solution réalisable au problème, donc n virus est bien un minimum à notre problème.

[Imod]

C'est un peu la même idée que nodgim et en effet ça marche :++: . Une autre idée plus rapide mais un "brin" astucieuse . On considère la frontière de l'ensemble des cases infectées . A chaque contamination on diminue ou on conserve le périmètre et comme à la fin le périmètre est 4n , il était supérieur ou égal à 4n au départ .

Imod

[Patastronch]

Une petite faille dans mon raisonnement :
A**
**A
*A*
Si A sont des virus il étaient pas connexe d'apres la définition précedente pourtant feront un jour parti du meme bloc infecté à une certaine étape.

Il faut corriger la notion de connéxité :

2 virus sont connexe si leur distance vaut au plus 2.
2 virus sont connecté si leur ensemble connexe a une distance de 2 au plus.
Un ensemble connexe est le rectangle minimum englobant un maximum de virus connexe.
Un ensemble connecté est le rectangle minimal englobant un maximum de virus connecté.

L'idée => Une solution réalisable est un ensemble connecté de taille nxn.
Il faut donc créer un ensemble connexe dans 2 coins oppposés et rajouter des ensembles connexe pour que ces 2 ensemble connexes soient connectés. Apres meme blabla.

[Patastronch]

C'est un peu la même idée que nodgim et en effet ça marche :++: . Une autre idée plus rapide mais un "brin" astucieuse . On considère la frontière de l'ensemble des cases infectées . A chaque contamination on diminue ou on conserve le périmètre et comme à la fin le périmètre est 4n , il était supérieur ou égal à 4n au départ .

Imod

Arf, j'ai loupé ce pseudo invariant pourtant si flagrant !