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
00:51

krabot

Libère ta liberté !
00:49

Mile

@darkmare, j'aurai qu'un mot a dire : hihihi
25/03
21:24

krabot

Le gouvernement de la Confédération Libre me semble bien populaire...
21:17

Yun

Big Billy
20:53

krabot

Je ne pensais pas que l'elmérisme aviaire avait fait autant de dégâts...
20:53

Alphante

T’en penses quoi krabot ? Tu penses que la majuscule c’est un hommage à toi ?
20:53

Alphante

Bravo. Je suis fier de toi,
20:35

darkmare

En même temps vous vous êtes tapés toute mon adolescence!!! Même moi je n'aurais pas tenu tellement j'étais désagréable!!!
20:33

krabot

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

darkmare

Et moi alors??? Plus de 20 ans de rajquit et de comptes définitivement supprimés ou hachedeusés... Et un de mes rares personnages à tenir les trois mois... Pour l'instant... ça mérite un cadeau aussi, non???
Texte généré à 00:03:58

Petites enigmes > Réponse Sciences sujet

Message auquel vous répondez