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

Hier
17:50

krabot

Ils sont plein de pognon, dans la Palladium Corporation...
17:49

Milhshake

Vive la Cursurie !
Avant-hier
16:21

krabot

Soumettez-vous à la Grande Déesse !
16:21

Red Jujul

Activé mon personnage ça fait une journée que j'attends
14/05
23:13

krabot

Révolution !
23:12

elwinks

VIVE LA CURSURIE
23:12

elwinks

vive la cursurie
10/05
19:24

krabot

Ssech, j'ai les oreilles qui sifflent...
19:24

Ssech

krabot
19:24

krabot

Libère ta liberté !
Texte généré à 06:06:19

Petites enigmes > Réponse Sciences sujet

Message auquel vous répondez