omb
Menu principal
Sujets d'articles
Extrait de l'Album
Forum - Tous les Posts Informations | BxMO 2017 | SBPM  
   Tous les Posts (Pablo Bustillo Vazquez)

 Bas   Précédent   Suivant



Re : Nombres de Ramsey (clés pour olympiade n°10)
Groupe A
Inscrit:
03/10/2013 13:52
Groupe :
Utilisateurs enregistrés
OMI Groupe A
Post(s): 16
Justement, j'ai montré que N = 2*(nombre de triangles non-monochromes). Il ne peut donc, pas être impair...

Contribution du : 31/08/2014 23:31
Transférer la contribution vers d'autres applications Transférer


Re : Nombres de Ramsey (clés pour olympiade n°10)
Groupe A
Inscrit:
03/10/2013 13:52
Groupe :
Utilisateurs enregistrés
OMI Groupe A
Post(s): 16
Si le début de ton raisonnement fonctionne - Corentin - (je me suis pas fais chier à vérifier), alors - si j'ai bien compris - on peut conclure de la sorte:
Si DE, EF ou FD sont bleus (par exemple DE), alors nous avons un deuxième triangle monochrome en reliant l'arête bleue avec A, B ou C (dans cet exemple, le triangle ADE est alors entièrement bleu). Et si aucun ne sont bleus, ils sont tous rouges => triangle DEF monochrome. Donc il existe nécessairement un deuxième triangle monochrome.

...Par contre, ça risque d'être difficile de généraliser pour l'exercices 3.

Contribution du : 31/08/2014 20:02
Transférer la contribution vers d'autres applications Transférer


Re : Nombres de Ramsey (clés pour olympiade n°10)
Groupe A
Inscrit:
03/10/2013 13:52
Groupe :
Utilisateurs enregistrés
OMI Groupe A
Post(s): 16
Une technique pour résoudre les exercices 1 et 3:

Supposons un graphe complet à n sommets colorié en deux couleurs.

Première idée cool: On peut s'intéresser au nombre N de triplet de sommets (x, y, z) tels que les arêtes (x,y) et (x,z) sont de couleurs différentes. On remarque que dans chaque triangle non-monochrome, il y a exactement 2 triplets de la sorte et que dans aucun triangle monochrome, il n'y a de tels triplets. Donc (nombre de triangle monochrome) = (nombre de triangles) - (nombre de triangles non-monochrome) = .

Donc on veut trouver une valeur maximale à N qui nous donne une valeur minimale satisfaisante au nombre de triangles monochromes.

Deuxième idée cool: Pour trouver cette majoration, on s'intéresse au nombre de tels triplets (x, y, z) avec x fixés. Ce nombre de triplets est trivialement (nombre d'arêtes bleues issues de x)*(nombre d'arêtes rouges issues de x) . Le nombre total de triplets est donc inférieur ou égal à . Cette majoration devrait suffire pour ces deux exercices.

Contribution du : 31/08/2014 19:42
Transférer la contribution vers d'autres applications Transférer


Re : Nombres de Ramsey (clés pour olympiade n°10)
Groupe A
Inscrit:
03/10/2013 13:52
Groupe :
Utilisateurs enregistrés
OMI Groupe A
Post(s): 16
Si tu me donnes l'énoncé de l'exo, je veux bien t'aider.

Contribution du : 30/08/2014 02:00
Transférer la contribution vers d'autres applications Transférer



 Haut




Membres
Prénom :

Nom :

Mot de passe : 

Conserver la connexion

Récupérer mot de passe
Recherche
Le site officiel de l'Olympiade Mathématique Belge
Contact webmasters :