Géométrie sur Z^2

sheeper

Bonjour, comment résoudre :
Dans $ \Z^2 $, chaque nœud a 4 voisins, si $ n $ nœuds sont occupés alors :
au moins $ \sqrt{n} $ sites ont au moins un voisin libre.

Merci

Lucas

Soit $R$ le plus petit rectangle qui contienne tes $n$ sites occupés. $R$ a au moins deux côtés (disons le haut et le bas) de longueur plus grande que $\sqrt{n}$.

Prenons un site du côté haut. Quitte à descendre, tu vas finir par tomber sur un libre voisin d'un site occupé. Ca t'en donne $\sqrt{n}$ différents.

Lucas

Oups, j'ai supposé que l'ensemble de sites occupés était connexe. Je pense que tu peux faire ma manip composante connexe par composante connexe.

Eric Chopin

Perso je n'ai pas tout saisi de l'enoncé. Avec un nombre fini de noeuds occupés je vois
mal comment on peut avoir moins qu'une infinité de noeuds avec un voisin libre...
Il doit manquer quelque chose...


eric

Lucas

Eric, j'avais compris comme toi mais je pense qu'il faut lire "$\sqrt{n}$ sites occupés qui ont un voisin libre".

sheeper

Lucas écrivait:

---

> Soit $R$ le plus petit rectangle qui contienne tes $n$ sites occupés. $R$ a au moins deux côtés (disons le haut et le bas) de longueur plus grande que $\sqrt{n}$.
> Prenons un site du côté haut. Quitte à descendre, tu vas finir par tomber sur un libre voisin d'un site occupé. Ca t'en donne $\sqrt{n}$ différents.

Merci, mais comment savoir qu'un coté du rectangle est d'au moins $ \sqrt{n}$ ?

Lucas

Sinon il aurait strictement moins que $n=\sqrt{n}\times \sqrt{n}$ sites, et donc il ne contiendrait pas l'ensemble de tes points occupés.