L'existence du centième carré

par **Imod** » 22 Mai 2008, 17:35

Un problème tiré d'une série dont j'ai déjà proposé un exercice ( Le quadrilatère recouvert par les disques ) .

Sur un quadrillage 29X29 on a dessiné 99 carrés d'intérieurs disjoints de côté deux et dont les sommets sont des noeuds du quadrillage . Montrer qu'on peut en dessiner un centième !!!

Imod

par **nodgim** » 22 Mai 2008, 18:13

Pour un damier de (3n+2)*(3n+2) cases, on met au minimum (n+1)² carrés de 2*2.

par **Imod** » 22 Mai 2008, 18:18

Mais ici les 99 premiers carrés sont placés au hazard !!!

Imod

par **nodgim** » 22 Mai 2008, 18:22

Imod a écrit:Mais ici les 99 premiers carrés sont placés au hazard !!!

Imod

Oui, mais je positionne les carrés de telle manière qu'ils encombrent au maximun le damier. C'est à dire qu'on laisse un espace de 1 case entre eux; Si on laisse 2 cases, on donne la possiblité de mieux remplir le damier en bouchant les trous.

par **Imod** » 22 Mai 2008, 18:29

C'est sûrement vrai :we: mais il faut justifier !!!

Imod

par **nodgim** » 22 Mai 2008, 18:48

Imod a écrit:C'est sûrement vrai :we: mais il faut justifier !!!

Imod

Bon, là c'est une autre histoire :hum:

par **Imod** » 29 Mai 2008, 19:01

Un petit up avant que le problème ne disparaisse :zen:

Imod

par **nodgim** » 30 Mai 2008, 17:53

Une piste, mais encore à affiner:
Partager le damier en carrés de 3*3 et dire que, avec 99 carrés 2*2, au pire, tous les carrés 3*3 sont occupés; Et que même dans ces conditions, on peut encore ajouter un carré 2*2.
L'optimisation que j'ai annoncée est inspirée de ce principe.

par **scelerat** » 31 Mai 2008, 09:47

Chaque carre couvre 9 intersections (3 dans chaque sens). Supposons qu'on recouvre totalement le quadrillage. cela signifie qu'aucune des 28x28 intersections qui ne sont pas sur les bords n'est decouverte, sinon on pourrait y mettre un carre. Prenons une ligne quelconque, et suivons la de gauche a droite. Chaque nouveau carre qu'on rencontre couvre 2 ou 3 nouvelles intersections suivant qu'il est adjacent au precedent ou non. Pour couvrir les 28 intersections, il faut donc au minimum 8 carres de 3 et 2 de 2, soit 10 carres. Pour chacun de ces carres, et suivant le meme raisonnement, la colonne qui passe par son centre contient au minimum 10 carres. Le nombre total de carres ne peut etre inferieur a 100. :++:

par **Imod** » 31 Mai 2008, 16:38

scelerat a écrit:Pour chacun de ces carres, et suivant le meme raisonnement, la colonne qui passe par son centre contient au minimum 10 carres. Le nombre total de carres ne peut etre inferieur a 100. :++:

Le début est convaincant mais je ne vois pas pourquoi dix carrés sur chaque ligne et dix carrés sur chaque colonne passant par le centre d'un carré entraînent cent carrés en tout ? Le même carré pouvant à priori être compté deux fois .

Imod

par **scelerat** » 02 Juin 2008, 12:33

Imod a écrit:Le début est convaincant mais je ne vois pas pourquoi dix carrés sur chaque ligne et dix carrés sur chaque colonne passant par le centre d'un carré entraînent cent carrés en tout ? Le même carré pouvant à priori être compté deux fois .
Imod

Oui, je corrige : dix carres sur une ligne quelconque, donc sur chacune des 10 lignes 1,4,7,...,28 de l'interieur du quadrillage.

par **Imod** » 02 Juin 2008, 16:16

En effet :++:

Une petite illustration avec un quadrillage 8X8 :

Imod

L'existence du centième carré

L'existence du centième carré

Qui est en ligne