| 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) |