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
|
|
![]() |
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
|
|
![]() |
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)
Contribution du : 31/08/2014 19:42
|
|
![]() |
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
|
|
![]() |
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
|
|
![]() |
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
|
|
![]() |
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
|
|
![]() |