Pseudo défi

par **buzard** » 20 Juin 2007, 09:43

Bonjour,

Je ne comprend pas bien le problème là? qu'est-ce qu'il faut colorier exactement?
La forme initiale? ou alors est-ce qu'on peut déborder, sur le quadrillage autour?

en tous cas sur un quadrillage 4x4 il est impossible de ne colorier qu'un coin

XOOO
OOOO
OOOO
OOOO

par **Imod** » 20 Juin 2007, 10:26

buzard a écrit:Je ne comprend pas bien le problème là? qu'est-ce qu'il faut colorier exactement? La forme initiale? ou alors est-ce qu'on peut déborder, sur le quadrillage autour? en tous cas sur un quadrillage 4x4 il est impossible de ne colorier qu'un coin

Bonjour buzard .

La question est de changer la couleur de toutes les cases du morceau de quadrillage que l'on a choisi ( les cases que l'on a pas choisies ne changent pas de couleur et n'ont de toute façon pas d'intérêt ) . Pour le problème du coin je n'ai pas dit que l'on pouvait à coup sûr changer la couleur de toutes les cases sauf le coin ou seulement du coin . Je précise . Supposons que pour tout morceau de quadrillage à n cases toutes blanches on peut noicir toutes les cases par des retournements de ses cases . Supposons en plus qu'il existe un morceau de quadrillage à n+1 cases blanches que l'on ne puisse pas noircir complètement . En enlevant une case C quelconque aux n+1 cases , on obtient un morceau à n cases blanches que l'on peut par hypothèse noircir complètement par une série de retournements S . Si on effectue les retournement S à l'ensemble des n+1 cases , on noircira toutes les cases sauf C ( si C était noire , on aurait noici les n+1 cases : contradiction ) .

J'espère avoir été clair .

Imod

par **kazeriahm** » 20 Juin 2007, 11:25

bon et si on initialise a n=2,

je reprend ton raisonnement Imod, on a n>=2, et j'utilise une récurrence forte.

On a donc noirci n cases et il nous reste C blanche. On enlève une case D des n cases noires. Il nous reste donc n-1 cases noires et C blanche. On blanchit les n-1 cases (ce qu'on peut faire car récurrence forte et "involution" du coloriage). Avec C, on a n cases blanches, que l'on noircit. En rajoutant D, on a bien noirci les n+1 cases.

Me serai-je trompé?

par **Imod** » 20 Juin 2007, 11:34

Bonjour Kazeriahm .

"En rajoutant D ..." , problème D est-elle alors noire ou blanche ?

Imod

par **kazeriahm** » 20 Juin 2007, 11:43

euh Imod j'ai effacé mon message oui parcequ'on ne peut pas toucher aux n cases sans modifier D... désolé :dodo:

par **Imod** » 21 Juin 2007, 17:18

Toujours pour un ensemble de n+1 cases dans le cas où n est pair , on considère une case C de l'ensemble ayant un nombre pair de voisines ( C existe-t-elle ? ) . Que se passe-t-il si pour chaque case E de l'ensemble choisi qui n'est pas voisine de C , on inverse toutes les cases de l'ensemble sauf la case E et que pour finir , on retourne C ( ie: changer la couleur de C et de ces voisines ) ?

Imod

par **Imod** » 21 Juin 2007, 17:33

Rain' a écrit:Mais C existe-t-elle ?

Le plus dur est fait ! Ne pas oublier que n est pair ( ou n+1 impair ) .

Penser à l'histoire des poignées de mains : dans une assemblée , il y a nécessairement un nombre pair de personnes ayant serré la main à un nombre impair de personnes .

Imod

par **Imod** » 26 Juin 2007, 22:56

C'est tout à fait équivalent aux poignées de mains dont je parlais ci-dessus ( vu pour la première fois dans un recueuil d'exercices pour l'oral du Capes ) .

Il y a un nombre impair de cases . Si chacune a un nombre impair de voisines alors la somme des voisines de toutes les cases est impaire . C'est impossible car si A est voisine de B alors B est voisine de A : la somme doit être paire .

Imod

par **Imod** » 27 Juin 2007, 00:19

Pas de quoi , ça parait très con après coup mais on entre là dans la théorie des graphes ( qui va se développer je vous l'assure ) .

Imod

par **Imod** » 02 Juil 2007, 16:54

Un exercice qui n'est pas sans rappeler le pseudo-défi ( qui marche d'ailleurs pour tous les graphes ) : Problème du mois

Imod

Pseudo défi

Qui est en ligne