omb
Menu principal
Sujets d'articles
Extrait de l'Album
Nombres de Ramsey (clés pour olympiade n°10) [Forum - Questions diverses] Informations | BxMO 2017 | SBPM  


 Bas   Précédent   Suivant Réponse Ecrire un nouveau message

« 1 (2)


A l'aide !!!
Re : Nombres de Ramsey (clés pour olympiade n°10)
A l'aide !!!
Donc, pour l'exercice 1, grâce à la théorie exposée dans l'article, on peut supposer qu'il y a un triangle (rouge ou vert) et avec les trois autres points pas encore utilisés, on peut montrer de même qu'on obtient un triangle unicolore (rouge ou vert) et on peut donc conclure que le résultat est établi ???

Contribution du : 31/08/2014 18:52
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:58
Groupe :
Utilisateurs enregistrés
OMI Groupe A
Post(s): 50
Bon, supposons qu'il existe un graphe complet à 6 sommets bicolore sans 2 triangles monochromes.
Il existe un triangle (disons ABC rouge) comme prouvé.
Supposons CD rouge,
-> AD et BD bleu
Supposons DE bleu,
-> AE et BE rouge
--> ABE rouge
Donc DE rouge,
-> CD bleu
...
CD bleu et (par symétrie) tous les segments entre A,B ou C et D,E ou F aussi.
Et merde ....

Contribution du : 31/08/2014 19:36
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 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


A
Re : Nombres de Ramsey (clés pour olympiade n°10)
A
Il n'y aurait pas un problème avec N/2 ?

On n'a toujours un nombre entier (si N est impair) !

Contribution du : 31/08/2014 21:36
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
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


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

Contribution du : 01/09/2014 10:24
Transférer la contribution vers d'autres applications Transférer



 Haut   Précédent   Suivant
« 1 (2)

Réponse Ecrire un nouveau message



[Recherche avancée]


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 :