Ceux qui ont le privilège de savoir ont le devoir d'agir.
Ensemble, mettons un terme à la corruption et à la pauvreté.
Le Théorème de Ramsey
À propos :
Le théorème de Ramsey est l'un des problèmes irrésolus qui permet de prouver la possibilité de la résolution de la théorie de Ramsey par résolution polynomiale. La formule précise qui permet de résoudre la théorie de Ramsey (en mathématiques, et plus particulièrement en combinatoire, la théorie de Ramsey, du nom de Frank Ramsey, tente typiquement de répondre à des questions de la forme : « combien d'éléments d'une certaine structure doivent être considérés pour qu'une propriété particulière se vérifie ? »), est le calcul du pôle expliqué dans l'ensemble théorique de la résolution en losange.
Problème :
Imaginez un cercle. Suivant la ligne du cercle, il y a plusieurs points à distance égal. Si nous relions tous les points par des lignes rouge ou verte, combien de triangle nous obtiendrons au minimum pour N point?
Réponse :
Pour résoudre le problème, nous devons créer une grille dans lequel les valeurs « +1 » (représentant la couleur verte) et « -1 » (représentant la couleur rouge) sont entrées de sorte à reproduire le paterne recherchée.
La logique derrière grille de calcul est la suivante :
1 : Le premier points à dessiné sera toujours à « +1 » à la position [1,1].
2 : Si la dernière valeur ajouté est « +1 », alors la prochaine valeur sera « -1 », et vise-versa.
3 : Si les colonnes et les rangées ont la même valeur, priorisé les colonnes.
Exemple pour 5 points :
1 : Nous appliquons la première règle :
[+1] [] [] [] T=1
T=1 [] [] [] T=0
T=0 [] [] T=0
T=0 [] T=0
T=0
2 : La colonne est pleine, donc nous continuons les rangées :
[+1] [-1] [] [] T=0
T=1 [] [] [] T=0
T=-1 [] [] T=0
T=0 [] T=0
T=0
3 : La deuxième colonne est égal à « -1 » , nous la priorisons :
[+1] [-1] [] [] T=0
T=1 [+1] [] [] T=1
T=0 [] [] T=0
T=0 [] T=0
T=0
4 : Les deuxième rangé est la plus éloigné de « 0 » :
[+1] [-1] [] [] T=0
T=1 [+1] [-1] [] T=0
T=0 [] [] T=0
T=-1 [] T=0
T=0
5 : La troisième colonnes est égal à « -1 », on poursuit avec cette colonne :
[+1] [-1] [+1] [] T=1
T=1 [+1] [-1] [] T=0
T=0 [] [] T=0
T=0 [] T=0
T=0
6 : La première rangée est égal à « 1 », on poursuit avec cette rangée :
[+1] [-1] [+1] [-1] T=0
T=1 [+1] [-1] [] T=0
T=0 [] [] T=0
T=0 [] T=0
T=-1
7 : La dernière colonne est égal à « -1 » :
[+1] [-1] [+1] [-1] T=0
T=1 [+1] [-1] [+1] T=1
T=0 [] [] T=0
T=0 [] T=0
T=0
8 : Toute les valeurs libres sont égal à « 0 », donc nous continuons avec la case la plus en haut à gauche :
[+1] [-1] [+1] [-1] T=0
T=1 [+1] [-1] [+1] T=1
T=0 [-1] [] T=-1
T=-1 [] T=0
T=0
9 : La troisième rangée est égal à « -1 » :
[+1] [-1] [+1] [-1] T=0
T=1 [+1] [-1] [+1] T=1
T=0 [-1] [+1] T=0
T=-1 [] T=0
T=1
10 : Il ne reste plus qu'une case :
[+1] [-1] [+1] [-1] T=0
T=1 [+1] [-1] [+1] T=1
T=0 [-1] [+1] T=0
T=-1 [-1] T=-1
T=0
Nous pouvons exprimer cette logique de manière simplifié dans une Formule de SCI :
#SO()==
OL( ir( 2 , ∞ ) ) ; // L est le nombre de point, moins un.
/* Calcul du Pole :
1 Variables de Limitation OL : 1-1=1
OM(0)
Le maximum de dimension d'itération des Variables Primitives est 2:
OM(0+2)
Il n'y a qu'une seule Variable P (invisible) : 1-1=0
OM(2+0)
Il n'y a qu'une seule Variable R : 1-1=0
OM(2+0)
La valeur total des variable isolé de l'OP est de 0 :
OM(2+0)
*/
OM(3) ; // Variable Secondaire de Mémoire i et j.
// Nous ajoutons k pour simplifier la compréhension du calcul dans l'AF.
OP( 0 ¦ L,L0² ) ;
// L'OP ne respectant pas les Règles de SCI, indique que la formule n'est pas sencé être une formule de SCI.
AF() ;
#AF()==
k = 1 ; // Type de pair de colonne.
PR(L,i)
{ RA( R = 2 ) // R représente les pairs de colonne.
{ k = ¬k
R = 0 ;
}
/* Nous plaçons les valeurs dans la grille, de sorte que toute les colonnes et rangées soit le plus
proche possible de 0 lorsque nous additionnons les itérations.
*/
PR( (L-i+1) , j )
{ RA( parity(j) = 0 )
{ M[ i , (j+i-1) ] = k
} !
{ M[ i , (j+i-1) ] = ¬k
}
}
R ++ ;
}
Chapitre 2 : La Résolution par Théorème.
En comparant les résultats des différents nombres de points, nous pouvons voir des fractales logistiques. Le problème peut donc être simplifié. Il nous faut donc mesurer les répétitions logistique des résultats. Nous pourrons également remarquer que la colonne « i » sera toujours égale à la rangée « i », permettant de calculer une seule colonne pour mesurer les fractales logiques.
Lexique :
+1 = Ligne Verte
-1 = Ligne Rouge
Résultats des mesures :
N=3 +1 -1
+1 0 | +1
N=4 +1 -1 +1
+1 -1 +1 | 0
-1 -1 | ?
N=5 +1 -1 +1 -1
+1 -1 +1 0 | +1
-1 +1
-1 0 | -1
N=6 +1 -1 +1 -1 +1
+1 -1 +1 -1 +1 | 0
-1 +1 -1
-1 +1 -1 | 0
+1 +1 | ?
N=7 +1 -1 +1 -1 +1 -1
+1 -1 +1 -1 +1 0 | +1
-1 +1 -1 +1
-1 +1 -1 0 | -1
+1 -1
+1 0 | +1
...etc....
Formule à appliquer :
En regardant les suites de valeurs obtenues, nous pouvons observer des conditions logiques entre chaque pair de résultat (exemple quand « 1=0 » et « 2=1 », alors 3 et 4 sera toujours égal à 0 et -1). Cette façon de placer les lignes de couleurs sert à générer le minimum de toutes les formes possibles d'une même couleur. Il nous est maintenant possible de jeter à la poubelle les modules créés jusqu'à présent et résoudre le problème.
En observant les résultats, nous pouvons venir à la conclusion suivante :
/* n : Nombre de points.
Tr : Variable stockant le nombre de triangle rouge.
Tv : Variable stockant le nombre de triangle vert.
T : Nombre Total de Forme minimum.
*/
// Nous constatons que pour chaque nombre,
PR( ( n - 1 ) , i )
{ // Si votre nombre est pair,
RA( parity( i ) )
{ Tv += 1 ; // Ajoute à la courbe des Tv +1.
} ! // Sinon (si impair) :
{ Tr += 1 ; // Ajoute à la courbe des Tr +1.
}
}
// Ensuite, multiplions Tv par 2, puis divisons le par 3. Et nous ne conservons que le nombre entier.
Tv = rnd( ( Tv * 2 ) / 3 )
// Faisons la même chose avec Tr.
Tr = rnd( ( Tr * 2 ) / 3 ) ;
// Additionnons Tv et Tr pour connaitre le résultat.
T = Tv + Tr ;
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Résultat Finale
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Nous pouvons donc conclure par des Équations de SCI afin de résoudre le problème :
/* n : Nombre total de points
c : Variable définissant le nombre total de couleur.
A : Variable définissant le nombre d'arrête par forme.
Tr : Variable stockant le nombre de triangle rouge.
Tv : Variable stockant le nombre de triangle vert.
T : Nombre Total de Forme minimum.
*/
Trouver le nombre minimal de triangle vert en utilisant la variable n :
Tv = rnd( rnd( rnd( n / 2 ) / A ) / 2 ) ;
Trouver le nombre minimal de triangle rouge :
Tr = rnd( ( rnd( n / 2 ) - Tv ) / A ) ;
/* Le nombre total minimale de triangle peut maintenant être déductible facilement :
*/
Trouver le nombre minimal de triangle Vert et Rouge :
T = rnd( rnd( n / 2 ) / A )
/* La formule reste la même si nous cherchons d'autre motif.
*/
Trouver le nombre minimal de pentagone vert (Pv) :
Pv = rnd( rnd( rnd( n / 2 ) / A ) / 2 )
Conclusion
Si nous souhaitons étendre le théorème afin de couvrir tout les cas possible, nous pouvons résumer le théorème de Ramsey en 2 formules universelles :
Forme F minimal pour chaque couleur :
F.i = rnd( ( rnd( rnd( n / c ) / A ) + (c-i) ) / c )
Nombre total T de forme F minimal pour les « c » couleurs :
T = rnd( rnd( n / c ) / A )
Pour les graphes non-complet, nous devons utilisez une règle de trois pour ajuster la valeur de « n » :
n = n * « nombre total d'arrête » / (n*(n-1)/2)
De cette façon, « n » représente la valeur des sommets de manière relative aux nombres d'arrêtes manquantes pour faire un graphe complet : la formule fonctionne pour tout les cas.
Donc, pour savoir le nombre de sommet minimum pour « c » couleur et « A » arrête d'une forme, afin de toujours avoir un minimum de « F » forme, l'équation est :
n = A*c*F
