この数学パズルは次のパーティーの計画に役立ちます

: By ゲイリー・チャートランド、ハーベイ・マッド大学、およびピン・チャン、西ミシガン大学

ご覧いただきありがとうございます InnerSelf.com、どこに〜がある 20,000+ 「新しい態度と新しい可能性」を促進する人生を変える記事。すべての記事は次のように翻訳されます 30以上の言語. ニュースレター登録 週刊発行の InnerSelf Magazine と Marie T Russell's Daily Inference に掲載されています。 InnerSelfマガジン 1985年から出版されています。

次のシンディグで接続をマッピングします。 unclibraries_commons

次のパーティを計画してゲストリストに苦しんでいるとします。誰に招待状を送るべきですか？友人と見知らぬ人の組み合わせが正しい組み合わせですか？

数学者たちはこの問題のバージョンに XNUMX 世紀近くにわたって取り組んできたことが判明しました。何を望むかによっては、答えが複雑になる場合があります。

私たちの本、「グラフ理論の魅力的な世界」」では、このようなパズルを調査し、グラフを使用してパズルを解く方法を示します。このような質問は小さいように思えるかもしれませんが、これは科学、コミュニケーション、社会などのさまざまな分野で数学的問題を解決するためにグラフをどのように使用できるかを示す美しいデモンストレーションです。

パズルが生まれる

ハーバード大学が国内トップクラスの学術大学の一つであることはよく知られていますが、ハーバード大学に全米最高のフットボールチームがあった時代があったと知ると驚かれるかもしれません。しかし1931年に、全米代表のクォーターバック、バリー・ウッド、そういうことだった。

そのシーズン、ハーバード大学は陸軍と対戦した。ハーフタイムでは、予想外にアーミーがハーバード大学を13対0でリードした。明らかに動揺したハーバード大学の学長は、陸軍の士官候補生の司令官に対し、フットボールでは陸軍の方がハーバードよりも優れているかもしれないが、より学術的な競争ではハーバードの方が優れていると語った。

ハーバード大学が戻ってきて陸軍を14対13で破ったが、司令官はより学術的なことでハーバード大学に対抗するという挑戦を受け入れた。二人は数学で競うことに同意した。これにより、陸軍とハーバード大学が数学チームを選択することになりました。対決は1933年にウェストポイントで起きた。ハーバード大学が驚いたことに、陸軍が勝利した。

ハーバード大学と陸軍のコンテストは、最終的に 1938 年に学部生を対象とした年次数学コンテストにつながりました。パトナム試験、ハーバード大学学長の親戚であるウィリアム・ローウェル・パットナムにちなんで名付けられました。この試験は、米国とカナダにおける数学における健全な競争を刺激することを目的として設計されました。長年にわたり、そして今日に至るまで、この試験には、上で説明した問題を含め、多くの興味深く、しばしば困難な問題が含まれています。

赤と青のライン

1953 年の試験には次の問題がありました (少し書き直されました): 平面には XNUMX つの点があります。すべての点は、青または赤の線で他のすべての点に接続されています。これらの点が XNUMX つあり、それらの間には同じ色の線だけが描かれていることを示します。

数学では、いくつかの点のペアの間に線が引かれた点の集合がある場合、その構造はグラフと呼ばれます。これらのグラフの研究はグラフ理論と呼ばれます。ただし、グラフ理論では、点は頂点と呼ばれ、線はエッジと呼ばれます。

グラフはさまざまな状況を表すために使用できます。たとえば、このパトナム問題では、点は人物を表し、赤い線はその人物が友人であることを意味し、青い線はその人物が見知らぬ人であることを意味します。

$数学のテスト$
XNUMX つの点が同じ色の線で結ばれていることを示します。ゲイリー・チャートランド

たとえば、点 A、B、C、D、E、F を呼び出し、そのうちの XNUMX つ、たとえば A を選択します。A から他の XNUMX つの点に引かれた XNUMX 本の線のうち、同じ色の線が XNUMX 本ある必要があります。

A から B、C、D までの線がすべて赤だとします。 B、C、D のいずれか XNUMX つの間の線が赤色の場合、その間に赤い線だけがある点が XNUMX つあります。 B、C、D のいずれか XNUMX つの間の線が赤でない場合、それらはすべて青になります。

ポイントが XNUMX つしかなかったらどうなるでしょうか? XNUMX つの点の間のすべての線が同じ色になることはありません。たとえば、線 A ～ B、B ～ C、C ～ D、D ～ E、E ～ A は赤、その他は青になる場合があります。

私たちが見たところによると、共通の友人が XNUMX 人、または共通の見知らぬ人が XNUMX 人いるようなパーティー (XNUMX 人ごとに友人か見知らぬ人) に招待できる最小人数は XNUMX 人です。

18 人が共通の友人、または共通の見知らぬ人になりたい場合はどうすればよいでしょうか? これを確実にするには、パーティーに招待する必要がある最小人数は何人ですか? この質問には回答がありました。 XNUMXです。

XNUMX 人が共通の友人、または共通の見知らぬ人になりたい場合はどうすればよいでしょうか? この状況では、これを保証するためにパーティーに招待できる最小人数は不明です。誰も知らない。この問題は説明するのが簡単で、かなり単純に聞こえるかもしれませんが、非常に難しいことで知られています。

ラムジー数

私たちがこれまで議論してきたのは、ラムゼー数と呼ばれるグラフ理論における数値の一種です。これらの数字はイギリスの哲学者、経済学者、数学者の名前にちなんで名付けられました。フランク・プランプトン・ラムジー.

ラムジーは 26 歳で亡くなりましたが、非常に幼い頃に数学における非常に興味深い定理を取得し、それがここでの私たちの疑問を引き起こしました。赤と青の線で結ばれた点でいっぱいの別の平面があるとします。 r と s という名前の XNUMX つの正の整数を選択します。ちょうど r 個の点の間のすべての線が赤になるか、s 個の点の間のすべての線が青になるようにしたいと考えています。これを行うことができる最小のポイント数はいくつですか? それはラムゼー数と呼ばれます。

たとえば、平面にすべての赤い線で接続された少なくとも XNUMX つの点と、すべての青い線で接続された XNUMX つの点があるとします。ラムジー数 (これを実現するために必要な最小ポイント数) は XNUMX です。

数学者は問題を検討するとき、「これは別の質問を示唆しているだろうか?」と自問することがよくあります。これがラムジーの数字と党の問題で起こったことだ。

たとえば、41 人の女の子がパーティーを計画しています。彼らは、少年たちを知っているかどうかに関係なく、何人かの少年をパーティーに招待することにしました。その中に常に XNUMX 人の男の子がいて、XNUMX 人の女の子のうち XNUMX 人が XNUMX 人の男の子全員と友達であるか、または XNUMX 人の男の子全員と知り合いではないことを確認するには、何人の男の子を招待する必要がありますか? おそらく、答えを正確に推測するのは簡単ではありません。 XNUMXですよ！

知られているラムジー数はほとんどありません。しかし、だからといって数学者がそのような問題を解決しようとするのを止めるわけではありません。多くの場合、XNUMX つの問題を解決できないと、さらに興味深い問題が発生する可能性があります。これが数学者の人生です。