Cartographie des connexions à votre prochain shindig. unclibraries_commons 

Disons que vous planifiez votre prochaine fête et agonisante sur la liste des invités. À qui devriez-vous envoyer des invitations? Quelle combinaison d'amis et d'étrangers est le bon mélange?

Il s'avère que les mathématiciens travaillent sur une version de ce problème depuis près d'un siècle. Selon ce que vous voulez, la réponse peut être compliquée.

Notre livre, "Le monde fascinant de la théorie des graphes, "Explore des puzzles comme ceux-ci et montre comment ils peuvent être résolus à travers des graphiques. Une question comme celle-ci peut sembler petite, mais c'est une belle démonstration de la façon dont les graphiques peuvent être utilisés pour résoudre des problèmes mathématiques dans des domaines aussi divers que les sciences, la communication et la société.

Un puzzle est né

Bien qu'il soit connu que Harvard est l'une des meilleures universités académiques du pays, vous pourriez être surpris d'apprendre qu'il y a eu une époque où Harvard avait l'une des meilleures équipes de football du pays. Mais dans 1931, dirigé par Le quart-arrière américain Barry Wood, tel était le cas.

Cette saison, Harvard a joué à l'armée. À la mi-temps, de façon inattendue, l'Armée a dirigé Harvard 13-0. Manifestement bouleversé, le président de Harvard a déclaré au commandant des cadets de l'armée que même si l'armée pouvait être meilleure que Harvard dans le football, Harvard était supérieur dans une compétition plus savante.

Bien que Harvard soit revenu pour vaincre l'armée 14-13, le commandant a accepté le défi de rivaliser avec Harvard dans quelque chose de plus savant. Il a été convenu que les deux seraient en concurrence - en mathématiques. Cela a conduit l'armée et Harvard à sélectionner des équipes de mathématiques; l'épreuve de force s'est produite à West Point dans 1933. À la surprise de Harvard, l'armée a gagné.

La compétition Harvard - Army a finalement conduit à une compétition annuelle de mathématiques pour les étudiants de premier cycle en 1938, appelée Putnam examen, nommé d'après William Lowell Putnam, un parent du président de Harvard. Cet examen a été conçu pour stimuler une saine rivalité en mathématiques aux États-Unis et au Canada. Au fil des ans et continuant à ce jour, cet examen a contenu de nombreux problèmes intéressants et souvent difficiles - y compris celui que nous décrivons ci-dessus.

Lignes rouges et bleues

L'examen 1953 contenait le problème suivant (reformulé un peu): Il y a six points dans l'avion. Chaque point est relié à un point sur deux par une ligne bleue ou rouge. Montrer qu'il y a trois de ces points entre lesquels ne sont dessinées que des lignes de la même couleur.

En mathématiques, s'il y a une collection de points avec des lignes tracées entre des paires de points, cette structure est appelée un graphique. L'étude de ces graphes est appelée théorie des graphes. En théorie des graphes, cependant, les points sont appelés sommets et les lignes sont appelées arêtes.

Les graphiques peuvent être utilisés pour représenter une grande variété de situations. Par exemple, dans ce problème de Putnam, un point peut représenter une personne, une ligne rouge peut signifier que les gens sont amis et une ligne bleue signifie qu'ils sont des étrangers.

Montrer qu'il y a trois points reliés par des lignes de la même couleur. Gary Chartrand

Par exemple, appelons les points A, B, C, D, E, F et sélectionnons l'un d'entre eux, disons A. Parmi les cinq lignes tracées de A à cinq autres points, il doit y avoir trois lignes de la même couleur.

Dites les lignes de A à B, C, D sont toutes rouges. Si une ligne entre deux des points B, C et D est rouge, il y a trois points séparés par des lignes rouges. Si aucune ligne entre B, C et D n'est rouge, ils sont tous bleus.

Et s'il n'y avait que cinq points? Il ne peut y avoir trois points où toutes les lignes entre elles sont colorées de la même manière. Par exemple, les lignes A-B, B-C, C-D, D-E, E-A peuvent être rouges, les autres étant bleues.

D'après ce que nous avons vu, alors, le plus petit nombre de personnes qui peuvent être invitées à une fête (où chaque deux personnes sont soit des amis soit des étrangers) de telle sorte qu'il y a trois amis communs ou trois étrangers mutuels est six.

Et si nous souhaitions que quatre personnes soient des amis communs ou des étrangers? Quel est le plus petit nombre de personnes que nous devons inviter à une fête pour en être certain? Cette question a été répondue. C'est 18.

Et si nous souhaitions que cinq personnes soient des amis communs ou des étrangers? Dans cette situation, le plus petit nombre de personnes à inviter à une fête pour être garanti de cela est - inconnu. Personne ne sait. Bien que ce problème soit facile à décrire et semble peut-être simple, il est notoirement difficile.

Chiffres de Ramsey

Ce dont nous avons discuté est un type de nombre dans la théorie des graphes appelé un nombre de Ramsey. Ces chiffres sont nommés pour le philosophe, économiste et mathématicien britannique Frank Plumpton Ramsey.

Ramsey mourut à l'âge de 26 mais obtint dès son plus jeune âge un très curieux théorème en mathématiques, ce qui a donné lieu à notre question ici. Disons que nous avons un autre plan plein de points reliés par des lignes rouges et bleues. Nous choisissons deux entiers positifs, nommés r et s. Nous voulons avoir exactement r points où toutes les lignes entre eux sont des points rouges ou s où toutes les lignes entre eux sont bleues. Quel est le plus petit nombre de points que nous pouvons faire avec? C'est ce qu'on appelle un numéro de Ramsey.

Par exemple, disons que nous voulons que notre avion ait au moins trois points reliés par toutes les lignes rouges et trois points reliés par toutes les lignes bleues. Le nombre de Ramsey - le plus petit nombre de points dont nous avons besoin pour y arriver - est de six.

Lorsque les mathématiciens regardent un problème, ils se posent souvent la question suivante: cela suggère-t-il une autre question? C'est ce qui est arrivé avec les numéros de Ramsey - et les problèmes de fête.

Par exemple, en voici une: Cinq filles planifient une fête. Ils ont décidé d'inviter des garçons à la fête, qu'ils connaissent ou non les garçons. Combien de garçons ont-ils besoin d'inviter pour être sûr qu'il y aura toujours trois garçons parmi eux, de sorte que trois des cinq filles sont soit amis avec les trois garçons, soit ne connaissent pas les trois garçons? Il n'est probablement pas facile de faire une bonne estimation de la réponse. C'est 41!

Très peu de nombres de Ramsey sont connus. Cependant, cela n'empêche pas les mathématiciens d'essayer de résoudre de tels problèmes. Souvent, ne pas résoudre un problème peut conduire à un problème encore plus intéressant. Telle est la vie d'un mathématicien.

À propos des auteurs

Gary Chartrand, professeur émérite de mathématiques, Western Michigan University; Arthur Benjamin, professeur de mathématiques, Harvey Mudd College, et Ping Zhang, professeur de mathématiques, Western Michigan University

Cet article a été publié initialement le The Conversation. Lis le article original.

Livres connexes:

at Marché InnerSelf et Amazon