[L1] Situation de recherche

[Mizuki777]

Bonsoir,

Je ne pas vraiment comment résoudre ce problème et je sollicite votre aide.

Je parle de l'ex 3, je pensais en recherchant un peu que la réponse était racine de n et avait prévu de le prouver par reccurence pour tous les carrés de taille n.

Sauf que j'ai l'impression cela ne répond que partiellement à la réponse

[Mizuki777]

https://image.noelshack.com/fichiers/20 ... 234630.jpg

[Pseuda]

Bonjour,

Quelques pistes. Il faut que les cases en coin soient colorées (tu vois pourquoi ?).

Il faut que parmi les cases qui bordent le carré, 1 sur 2 soient colorées. On peut distinguer n pair et n impair.

On suppose qu'on a bien colorié un bord. On colorie en allant vers l'autre bord. Il n'y a pas beaucoup de choix.

[pascal16]

je ne sais pas si l'énoncé est à interpréter, mais
si tu as une ligne sur 3 de complètement contaminée, rien ne bouge.
si tu as une zone carrée k*k de contaminée, rien ne bouge

Mais alors où est le minimum pour provoquer une contamination totale ?

[Ben314]

Salut,

(1) Il faut que les cases en coin soient colorées (tu vois pourquoi ?).
(2) Il faut que parmi les cases qui bordent le carré, 1 sur 2 soient colorées.

Perso, non seulement je ne vois pas pourquoi mais en plus l'exemple simple où au départ on a colorié la diagonale me fait dire que (1) et (2) sont faux.

Perso, je conjecturerais plus que très fort que pour colorier entièrement un carré nxn, il faut qu'au départ il y ait au moins n cases de coloriées.
Avec exactement n cases, il y a au moins deux solutions évidentes : soit colorier une diagonale entière, soit colorier une case sur deux le long de deux cotés adjacents du carré (en commençant et en terminant par une case coloriée).
Par contre, pour le moment, je ne vois pas d'argument simple pour montrer que n est la valeur minimale.
Il faut peut être partir de la constatation évidente que, si deux lignes (ou colonnes) consécutives sont entièrement vides au départ, elles resteront vides, mais ça n'est pas suffisant pour conclure.

[Pseuda]

Salut,

(1) Il faut que les cases en coin soient colorées (tu vois pourquoi ?).
(2) Il faut que parmi les cases qui bordent le carré, 1 sur 2 soient colorées.

Perso, non seulement je ne vois pas pourquoi mais en plus l'exemple simple où au départ on a colorié la diagonale me fait dire que (1) et (2) sont faux.

Comme d'habitude, il y a ambiguïté sur l'énoncé. Qu'appelle-t-on "bordée" ? de part et d'autre, i.e. encadrée ? ou pas forcément ?

Quand on "borde" un enfant dans son lit, c'est de part et d'autre ....

Cela fait partie de la situation de recherche .... : Deux énoncés en un !

[pascal16]

c'est là que le "pour être certain" de l'énoncé est discutable.
a-t-on le choix du placement des cases colorées ?
sinon, on tombe sur (n-1)²+1

[Ben314]

Pour moi, les seules "vagues" ambiguïté de l'énoncé, c'est :
1) Les cases qui "bordent" une autre, est-ce que c'est uniquement celles qui ont un segment en commun ou bien aussi celle qui n'ont qu'un sommet en commun ?
Mais, perso, je mettrais plus de 9 chance sur 10 qu'il faille le comprendre sous la forme "un segment commun".
2) Le processus est-il récursif ou pas ? i.e. est ce qu'on colorie uniquement celle qui sont bordée par deux cases au départ coloriées ou bien aussi celle qui sont bordée par 2 cases coloriées ultérieurement ?
Et là, je mettrais plus de 99 chance sur 100 qu'il faille le comprendre sous la forme récursive vu que sinon, l'énoncé est sans grand intérêt.

Parce que sinon, concernant le fait de savoir si on peut choisir ou pas l'emplacement des cases coloriées au départ, il me semble qu'au niveau du Français, vu la formulation de la phrase, il n'y a pas la moindre ambiguïté : on te demande combien il faut en colorier au minimum pour qu'au final tout soit colorié ce qui signifie on ne peut plus clairement que la seule chose qui compte, c'est le nombre de case que tu colorie : à toi de voir quelle disposition permet de rendre ce nombre le plus petit possible.

[Mizuki777]

D'abord merci à tous d'avoir répondu, il semblerait que l'énoncé soit quelque peu ambigüe pour certains,

Ben314 se rapproche le plus de l'énoncé pour qu'une case soit dite " bordée" il faut qu'elle soit encerclé par 2 cases MINIMUM colorée ( par le haut, la gauche, la droite, ou le bas )

Et, oui le processus est récursif . Mon hypothèse est que cela colorie toute les cases lorsque on colorie seuleument les cases de la diagonale, seuleument maintenant il faut que je réussisse à le prouver mathématiquement et là je bloque ...

Merci à tous d'avance

Merci à tous pour l'aide d'avance
[/code]

Pour moi, les seules "vagues" ambiguïté de l'énoncé, c'est :
1) Les cases qui "bordent" une autre, est-ce que c'est uniquement celles qui ont un segment en commun ou bien aussi celle qui n'ont qu'un sommet en commun ?
Mais, perso, je mettrais plus de 9 chance sur 10 qu'il faille le comprendre sous la forme "un segment commun".
2) Le processus est-il récursif ou pas ? i.e. est ce qu'on colorie uniquement celle qui sont bordée par deux cases au départ coloriées ou bien aussi celle qui sont bordée par 2 cases coloriées ultérieurement ?
Et là, je mettrais plus de 99 chance sur 100 qu'il faille le comprendre sous la forme récursive vu que sinon, l'énoncé est sans grand intérêt.

Parce que sinon, concernant le fait de savoir si on peut choisir ou pas l'emplacement des cases coloriées au départ, il me semble qu'au niveau du Français, vu la formulation de la phrase, il n'y a pas la moindre ambiguïté : on te demande combien il faut en colorier au minimum pour qu'au final tout soit colorié ce qui signifie on ne peut plus clairement que la seule chose qui compte, c'est le nombre de case que tu colorie : à toi de voir quelle disposition permet de rendre ce nombre le plus petit possible.

[Mizuki777]

http://image.noelshack.com/fichiers/201 ... 211229.jpg

[Pseuda]

Bonsoir,

Dans ce cas, après quelques essais, il semblerait qu'une condition nécessaire et suffisante pour colorier tout le carré, est que chaque colonne et chaque ligne contienne au moins une case coloriée. Le minimum serait donc de cases coloriées au départ (la diagonale par exemple).

Quant à la démonstration : la récurrence. On suppose qu'on a colorié ainsi tout le carré nxn, et on rajoute une ligne et une colonne pour en faire un carré (n+1)x(n+1). On ne peut pas continuer le coloriage sans rajouter une nouvelle case coloriée. Il y a un endroit évident où placer la (n+1)-ème case coloriée pour colorier tout le carré (de manière nécessaire et suffisante).

[Ben314]

Dans ce cas, après quelques essais, il semblerait qu'une condition nécessaire et suffisante pour colorier tout le carré, est que chaque colonne et chaque ligne contienne au moins une case coloriée.

non, le deuxième exemple de mon post précédent (on colorie une case sur de deux le long de deux cotés adjacents) montre que ce n'est pas nécessaire.

[Pseuda]

Bonjour,

Oui en effet, c'est pourquoi j'ai parlé au conditionnel. Mais ce qui compte, c'est le nombre minimum de cases à colorier, peu importe la configuration des cases (qui n'est pas demandée par l'exercice). La démonstration par récurrence est très simple et évidente, et montre qu'il faut au minimum n cases coloriées au départ (bien placées, par exemple le long de la diagonale), pour pouvoir colorier toutes les cases du carré.

[Ben314]

Ben la récurrence de la fin de ton post, c'est... pas mieux que le début...

On suppose qu'on a colorié ainsi tout le carré nxn, et on rajoute une ligne et une colonne pour en faire un carré (n+1)x(n+1). On ne peut pas continuer le coloriage sans rajouter une nouvelle case coloriée. Il y a un endroit évident où placer la (n+1)-ème case coloriée pour colorier tout le carré (de manière nécessaire et suffisante).

Si tu regarde par exemple la solution sur le 3x3 consistant à colorier les cases (1,1) ; (1,3) et (3,1) tu constate que, sur les 4 sous carrés 2x2 obtenu en enlevant une ligne et un colonne du bord, le "sous coloriage" sur ce carré 2x2 n'est jamais une solution pour le carré 2x2.
Donc cette solution ne peut pas être obtenue par "prolongement" d'une solution d'un 2x2 en ajoutant une ligne et une colonne au bord ce qui rend caduque toute forme de récurrence "directe" sur la taille du carré.

[Pseuda]

Heu, pas d'accord avec toi Ben314. La récurrence que j'ai décrite suppose qu'on a colorié tout le carré au rang , peu importe la configuration qui y a mené (du moment qu'elle comportait au moins cases coloriées convenablement disposées). Pour passer au rang , il faut et il suffit de colorier au moins une case convenablement choisie. Cela fait bien au moins cases coloriées pour colorier tout le carré au rang .

Donc il faut au moins cases coloriées, cases coloriées sont nécessaires. Et elles sont suffisantes (le long de la diagonale). Donc cases coloriées constitue un minimum atteint.

[Ben314]

La récurrence que j'ai décrite suppose qu'on a colorié tout le carré au rang , peu importe la configuration qui y a mené (du moment qu'elle comportait au moins cases coloriées convenablement disposées).

Essaye de lire (et de comprendre) ce que j'ai écrit : partant d'un 2x2 contenant zéro cases coloriées on peut parfaitement (par adjonction d'une ligne et d'une colonne) obtenir un 3x3 correct. Donc de considérer comme tu le fait qu'on va appréhender toutes (*) les situation correctes pour un (n+1)x(n+1) en partant de situation correctes pour un nxn, ben c'est faux.

(*) Et si tu les appréhende pas toute, ben tu as rien démontré du tout vu que ce qu'il faut évaluer, c'est le minimum du nombre de cases coloriées sur l'ensemble de toutes les situation correctes.

[Pseuda]

partant d'un 2x2 contenant zéro cases coloriées on peut parfaitement (par adjonction d'une ligne et d'une colonne) obtenir un 3x3 correct.

Mais c'est le principe d'une récurrence, on suppose que c'est vrai au rang !!!???

[Ben314]

Mais c'est le principe d'une récurrence, on suppose que c'est vrai au rang !!!???

Le "principe" d'une récurrence, comme tu dit, c'est SURTOUT que ça ne s'applique que dans les cas où on a une "formule de récurrence" qui permet de "passer" du rang n au rang n+1.
Toi, ta "formule de récurrence", c'est que l'on obtient les solution au rang n+1 en partant de celle de rang n et en ajoutant une ligne et une colonne. Sauf que cette formule est fausse vu que que le 3x3 dont je parle n'est pas issu d'une des solutions pour le 2x2 par adjonction d'une ligne et d'une colonne.
Bref, c'est pas ta façon de faire une récurrence qui est fausse, c'est ta formule de récurrence.

Et si on veut rentrer plus dans les détail concernant la rédaction, dans ta récurrence, ton hypothèse (de récurrence), c'est que :
- Tout les carrés corrects de taille nxn contiennent au moins n cases coloriées
Ce que tu doit alors démontrer, c'est que :
- Tout les carrés corrects de taille (n+1)x(n+1) contiennent au moins n+1 cases coloriées
Pour ce faire, tu n'a pas le choix : tu doit bien sûr considérer un carré correct quelconque de taille (n+1)x(n+1).
Sauf que là, ce que tu affirme (sans preuve), c'est que ce carré correct (n+1)x(n+1) est forcément constitué d'un carré correct nxn auquel on à ajouté une ligne et une colonne.
Et le problème, c'est bien sûr l'absence de preuve, [et l'exemple du carré 3x3 montre même que c'est faux].

[Pseuda]

Ok, tu as raison Ben314 (je n'ai pas lu ton dernier message). La récurrence porte sur "il faut au moins n cases ....", elle ne dit pas qu'on a colorié effectivement toutes les cases (ce qui serait faux puisqu'on peut les colorier autrement, ou même pas du tout). Donc ça ne marche pas.

(le problème, c'est que je fais d'autres choses en même temps, et que je ferais mieux de ne pas répondre, si je ne peux pas y consacrer un peu de temps minimum).

[Ben314]

Je "fait le malin" concernant le fait que ta preuve ne marche pas, mais d'un autre coté, ben... j'ai toujours pas trouvé de preuve non plus...