Kraland Interactif

Expéditeur *

Message *

[b]Elune Morningwood[62�o]Jumper a écrit :[/b]

[quote][b]Mouton a écrit :[/b]
> On se donne un graphe complet à 6 sommets et deux joueurs. Chaque joueur à son tour colorie 
> une arête de sa couleur (rouge ou verte). Un joueur gagne s'il a colorié un triangle. 
> Montrer qu'il y a forcément un vainqueur.

[spoiler]Ne pas avoir un triangle revient a dire que :
Pour tous points A, B et C, si J1 detient AB et AC alors J2 detient BC.

Avec 6 sommets, il existe 5 arretes pour chaque point. Un joueur doit donc avoir au moins 3 arretes.
Donc J1 detient AB, AC et AD.

D'apres notre regle, cela signifie que J2 detient BC, CD et BD. Ce qui forme un triangle pour J2.
Il y a donc forcement un vainqueur.[/spoiler]

Pour le deuxieme:
[spoiler]Il y a tres certainement a voir que quand tu as n=m=2, le joueur qui joue est gagnant.
Et que a chaque action, tu crees 2 blocs a considerer : on a (k-1,l-1) (k-1,n) et (m,l-1). Et qu'on doit pouvoir dire que celui qui prend le (1,1) de chaque bloc est perdant pour x raison.

Mais la, j'arrive pas plus loin sans reflechir plus[/spoiler][/quote]

Message auquel vous répondez

Elune Jumper

Membre

posté 11/10/13 (14:09)

Mouton a écrit :
> On se donne un graphe complet à 6 sommets et deux joueurs. Chaque joueur à son tour colorie
> une arête de sa couleur (rouge ou verte). Un joueur gagne s'il a colorié un triangle.
> Montrer qu'il y a forcément un vainqueur.

Spoiler
Ne pas avoir un triangle revient a dire que :
Pour tous points A, B et C, si J1 detient AB et AC alors J2 detient BC.

Avec 6 sommets, il existe 5 arretes pour chaque point. Un joueur doit donc avoir au moins 3 arretes.
Donc J1 detient AB, AC et AD.

D'apres notre regle, cela signifie que J2 detient BC, CD et BD. Ce qui forme un triangle pour J2.
Il y a donc forcement un vainqueur.

Pour le deuxieme:
Spoiler
Il y a tres certainement a voir que quand tu as n=m=2, le joueur qui joue est gagnant.
Et que a chaque action, tu crees 2 blocs a considerer : on a (k-1,l-1) (k-1,n) et (m,l-1). Et qu'on doit pouvoir dire que celui qui prend le (1,1) de chaque bloc est perdant pour x raison.

Mais la, j'arrive pas plus loin sans reflechir plus

___

Elune, moutonologue

Mini-Chat

02:41

krabot

Le gouvernement de la Confédération Libre me semble bien populaire...
02:11

krabot

Au stade où ils en sont, la Théocratie Seelienne n'est pas près de découvrir une nouvelle technologie...
01:40

krabot

Vivez en harmonie avec la Nature !
01:10

krabot

Nous sommes tous frères !
00:40

krabot

Cela fait longtemps qu'on n'a pas eu une vraie discussion comme ça...
00:09

krabot

Soumettez-vous à la Grande Déesse !
Hier
23:39

krabot

Snif, il n'y a pas de krabotette...
23:09

krabot

Qui va tenter un coup d'état au Paradigme Vert ? C'est vraiment le moment !
23:08

krabot

Cela fait longtemps qu'on n'a pas eu une vraie discussion comme ça...
22:38

krabot

Krabot est de retour... pour vous jouer un mauvais tour !
Texte généré à 03:02:20

Petites enigmes > Réponse Sciences sujet

Message auquel vous répondez