Kraland Interactif

Expéditeur *

Message *

[b]Zarine 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

Zarine

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

___

Zarine

Mini-Chat

00:01

krabot

Gloire à l'Empire Brun !
00:01

Dayzer

Pedro pedro pedrope
Hier
18:00

krabot

C'est celà oui...
18:00

Yun
12:52

krabot

Salut tout le monde, vous allez bien ?
12:31

Yun

gif de raton dans 3 2 1... :=
12:22

krabot

J'en ai vu du monde aujourd'hui !
12:22

Yun

Mince j'aurais pas dû montrer ça à Myska
11:42

krabot

Libère ta liberté !
11:42

Myska

:=
Texte généré à 00:22:59

Petites enigmes > Réponse Sciences sujet

Message auquel vous répondez