Remplir un carré nXn avec moins de n serpents
Bonjour à tous :-D
Un problème trouvé sur un autre site et que je trouve plutôt intéressant .
On veut remplir une grille carrée $n\times n$ avec des serpents de deux sortes , les bleus qui montent et les rouges qui descendent ( on lit de gauche à droite comme d'habitude ) . En fait il y a deux couleurs en plus correspondants aux serpents de nature indéterminée ( les verts du dessin et les jaunes qui seraient horizontaux ) . Chaque serpent a l'épaisseur d'une case , il est constitué de cases contiguës partageant un côté , il ne peut pas traverser un autre serpent .
Peut-on recouvrir le carré avec moins de $n$ serpents ?
Une illustration avec $8$ serpents pour un carré de côté $8$ .
Domi
Un problème trouvé sur un autre site et que je trouve plutôt intéressant .
On veut remplir une grille carrée $n\times n$ avec des serpents de deux sortes , les bleus qui montent et les rouges qui descendent ( on lit de gauche à droite comme d'habitude ) . En fait il y a deux couleurs en plus correspondants aux serpents de nature indéterminée ( les verts du dessin et les jaunes qui seraient horizontaux ) . Chaque serpent a l'épaisseur d'une case , il est constitué de cases contiguës partageant un côté , il ne peut pas traverser un autre serpent .
Peut-on recouvrir le carré avec moins de $n$ serpents ?
Une illustration avec $8$ serpents pour un carré de côté $8$ .
Domi
Réponses
-
Hello Dom,
je ne comprends pas bien: peux-tu donner une définition précise d'un serpent de nature indéterminée ? Sont-ce des serpents verticaux ou horizontaux, ou alors peuvent-ils à la fois monter et descendre (auquel cas, un serpent zigzaguant suffit)? Les autorisent-tu pour remplir le carré ? -
Les serpents bleus montent , les rouges descendent , si tu considères une barre horizontale ou verticale , tu ne pourras pas préciser s'il s'agit d'un bleu ou d'un rouge mais il est accepté ainsi que les cases uniques .
Domi -
Salut (chaleureux)
On peut (je peux) dire que non, en effet suivant un serpent il est facile de trouver que le minimum de nombres est le même que celui avec un carré et des serpents maximales formes V sur les coins, c'est $\ge n$. -
Bonjour,
Remplissons une grille rectangulaire $m×n$ avec des serpents ($m \leq n) $.
Il faut montrer que le nombre minimum de serpents est $m$. C'est évident pour $m=1$ et pour $m=2$, ensuite . . . -
En effet si $m\leq n$ il faut au moins $m$ serpents pour remplir une grille $m\times n$ , il n'y a plus qu'à le prouver et ce n'est pas facile .
Domi -
Je précise que j'ai une solution ( voire deux ) et que c'est l'illustration proposée qui m'a donné l'idée .
Domi -
Bonjour Domi,
ton dernier message est ambigu: as-tu, contemplant ton dessin, compris qu'il fallait au moins $8$ serpents et en as donné une preuve (voire deux) ou, au contraire, vu comment le modifier d'une (voire deux) manière(s) pour t'en sortir avec $7$ serpents?
Amicalement
Paul -
J'ai compris pourquoi il fallait $8$ serpents ou encore comment mettre de l'ordre dans cette fosse aux serpents .
Domi -
Une petite remontée ( il y avait un message subliminal dans ma dernière intervention ) :-D
Domi -
Bonsoir à tous,
et merci Domi!
Je prends le parti de définir beaucoup, mais de ne pas entrer dans le détail de la preuve de chaque affirmation. Chacune me semble simple à démontrer et si certaine ne l'est pas pour le lecteur, j'y reviendrai quitte à conclure que j'ai écrit une bêtise.
Définitions 1:
Fosse:= Matrice carrée pavée de serpents avec les contraintes de Domi. Je m'écarte du dessin de Domi en ce que tous mes serpents sont, comme les siens, monochromes mais que deux quelconques d'entre eux ont des couleurs distinctes.
Taille d"une fosse:= nombre de lignes de sa matrice.
Cardinal d"un fosse:= nombre de serpents qui la pavent.
But: Prouver $P$:= le cardinal d'une fosse est supérieur ou égal à sa taille.
Moyen pour atteindre ce but: prouver ($P$ et $Q$) où $Q$ s'exprime via les définitions suivantes:
Définitions 2:
Pout tout $n>0$, pour toute fosse $f$ de taille $n$, pour tout serpent $s$ de $f$,
Bordantes de $f$ := $L_1,L_n,C_1,C_n$ de $f$
Bordure de $f$:= réunion des bordantes de $f$
L de $f$:= réunion d'une ligne et d'une colonne bordantes de $f$
sous-fosse de $f$:= $f$ privée d'un de ses L,
$s$ est
bordant s'il est inclus dans la bordure,
trouant si ses extrêmités sont dans la bordure,
diagonal si ses extrêmités sont diagonalement opposées.
$Q$:= pour tout $n>0$, dans toute fosse de taille $n$ et de cardinal $n$ il existe un serpent trouant.
Fini pour ce soir! Sommeil.Je voulais tout de même en dire plus.Puisses-tu Domi (ou ton prochain) me dire "Bon, ça va, t'as trouvé, pas besoin de continuer!"
Amicalement
Paul -
Bonjour Paul
Désolé , une fosse sans serpent "trouant" .
Domi -
Irréfutable!
Je sors -
Il ne faut pas désespérer , laisse reposer :-D
Domi -
Comme il n'y a plus de réactions , je donne ma façon de voir le problème .
On peut ranger les serpents en disant qu'un serpent est sous un autre s'il a une case sur la même colonne mais sur une ligne en dessous de l'autre . On peut compléter ce rangement pour en faire un ordre total ( pas unique en général ) . Après il faut regarder ce qui se passe quand on empile les serpents en commençant par ceux des niveaux inférieurs .
Domi -
Salut Domi,
Je crois en ta jolie idée et regrette de ne l'avoir pas eue! Du coup,il te revient de montrer qu'elle résout le problème, ce qui me libère du temps pour fouetter d'autres questions :-D. Je te promets d'avance mon (tu).
Amicalement
Paul -
En fait l'idée est assez visuelle , on empile les serpents en commençant par ceux de rang inférieur . Le premier serpent ne peut pas avoir plus d'une case sur la deuxième ligne de la grille . On continue par récurrence : les $k$ premiers serpents ne peuvent pas avoir plus de $k$ cases sur la ligne $k+1$ . Alors $n-1$ serpents ne peuvent pas remplir plus de $n-1$ cases de la dernière ligne du carré $n\times n$ .
Amicalement
Domi -
Bravo!
Paul
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 8 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 3
+2 Invités