omb
Menu principal
Sujets d'articles
Extrait de l'Album
Forum Informations | BxMO 2017 | SBPM  

Sujet :
Nom/Email :
Icône du message :
Sélectionner
Message : URL  Email  Images  Inside images Flash WIKI link  Source code  Quote

Bold Italic Underline Linethrough    EXEMPLE


 [plus...]
Options :Activer les émoticones
Activer les codes Xoops
Activation du line break (Suggérré non activé si le HTML est activé)
Code anti-spam : 
     
Re : Nombres de Ramsey (clés pour olympiade n°10)

par A l'aide !!! sur 1/9/2014 10:24:40

Merci, c'est parfaitement clair maintenant et je confirme que les majorations sont pratiques : j'obtiens N <= 36 pour l'exercice 1 (d'où N_max = 36) et N <= 63 pour l'exercice 3 (d'où N_max = 62).
Re : Nombres de Ramsey (clés pour olympiade n°10)

par Pablo Bustillo Vazquez sur 31/8/2014 23:31:00

Justement, j'ai montré que N = 2*(nombre de triangles non-monochromes). Il ne peut donc, pas être impair...
Re : Nombres de Ramsey (clés pour olympiade n°10)

par A sur 31/8/2014 21:36:08

Il n'y aurait pas un problème avec N/2 ?

On n'a toujours un nombre entier (si N est impair) !
Re : Nombres de Ramsey (clés pour olympiade n°10)

par Pablo Bustillo Vazquez sur 31/8/2014 20:02:40

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.
Re : Nombres de Ramsey (clés pour olympiade n°10)

par Pablo Bustillo Vazquez sur 31/8/2014 19:42:03

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.
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 :