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

Avant-hier
20:47

krabot

C'est pas ce qu'on m'avait dit...
20:47

Yun

Votez Rekt !
20/08
21:21

krabot

Tu crois vraiment ?
18/08
23:04

krabot

Mouais mouais mouais...
23:04

Sabine

REVIENS dARKMARE ! les Passes Brunes sont des retour hihihi !
11:36

krabot

Bwahaha ! Les grands stratèges de l'Empire Brun sont vraiment des ploucs !
11:35

Ahson Miriel

Hallo !!
17/08
23:13

krabot

Kiii kiki kiiiki, j'ai les oreilles qui sifflent...
23:13

Kiii kiki kiiiki

krabot on aura ta peau
Texte généré à 03:42:22

Petites enigmes > Réponse Sciences sujet

Message auquel vous répondez