Bir sonraki shindig'inizdeki bağlantıları haritalama. unclibraries_commons 

Bir sonraki partinizi planladığınızı ve misafir listesinde acı çektiğinizi varsayalım. Kime davetiye göndermelisin? Arkadaş ve yabancıların hangi kombinasyonu doğru karışımdır?

Matematikçilerin bu sorunun bir versiyonu üzerinde neredeyse bir yüzyıldır çalıştıkları ortaya çıktı. Ne istediğine bağlı olarak, cevap karmaşık olabilir.

Bizim kitabımız, “Grafik Teorisinin Büyüleyici Dünyası“Bu gibi bulmacaları araştırıyor ve grafiklerle nasıl çözülebileceğini gösteriyor. Bunun gibi bir soru küçük görünebilir, ancak grafik, bilimler, iletişim ve toplum gibi farklı alanlarda matematiksel sorunları çözmek için grafiklerin nasıl kullanılabileceğinin güzel bir göstergesi.

Bir bulmaca doğar

Harvard'ın ülkedeki en iyi akademik üniversitelerden biri olduğu biliniyor olsa da, Harvard'ın ülkenin en iyi futbol takımlarından birine sahip olduğu bir zaman olduğunu öğrenince şaşırabilirsiniz. Ancak 1931’in öncülüğünde Amerikan oyun kurucusu Barry Wood, böyle oldu.

O sezon Harvard Ordu oynadı. İlk yarı, beklenmedik bir şekilde, Ordu Harvard 13 – 0'i yönetti. Açıkça üzülen Harvard başkanı, Ordu’nun komutanının komutanına, Ordunun futbolda Harvard’dan daha iyi olmasına rağmen, Harvard’ın daha bilimsel bir rekabet içinde üstün olduğunu söyledi.

Harvard, Ordu 14-13’i yenmek için geri gelmesine rağmen, komutan, Harvard’a karşı daha akademik bir konuda rekabet etme mücadelesini kabul etti. İkisinin rekabet edeceği konusunda hemfikirdi - matematikte. Bu, Ordu ve Harvard'ın matematik ekiplerini seçmesine yol açtı; gösteri, 1933’teki West Point’te gerçekleşti. Harvard'ın sürprizine göre, Ordu kazandı.

Harvard-Army yarışması sonunda 1938’te mezun olan öğrenciler için yıllık bir matematik yarışmasına yol açtı. Putnam sınavıHarvard'ın başkanının akrabası William Lowell Putnam için. Bu sınav, Amerika Birleşik Devletleri ve Kanada'da matematikte sağlıklı bir rekabeti teşvik etmek için tasarlanmıştır. Yıllar geçtikçe ve bu güne kadar devam eden bu sınav, yukarıda açıkladığımız sınav da dahil olmak üzere birçok ilginç ve çoğu zaman zorlayıcı problemler içeriyordu.

Kırmızı ve mavi çizgiler

1953 sınavı şu problemi içeriyordu (biraz yeniden değerlendirildi): Düzlemde altı nokta var. Her nokta diğer noktalara mavi veya kırmızı olan bir çizgiyle bağlanır. Aralarında sadece aynı renkteki çizgilerin çizildiği üç nokta olduğunu gösterin.

Matematikte, bazı nokta çiftleri arasında çizilen çizgilerle bir nokta koleksiyonu varsa, bu yapıya grafik denir. Bu grafiklerin çalışmasına grafik teorisi denir. Bununla birlikte, grafik teorisinde noktalar köşeler, çizgiler ise kenarlar olarak adlandırılır.

Grafikler, çok çeşitli durumları temsil etmek için kullanılabilir. Örneğin, bu Putnam probleminde, bir nokta bir kişiyi temsil edebilir, kırmızı çizgi insanların arkadaş olduğu ve mavi çizgi de yabancı oldukları anlamına gelebilir.

Aynı renkteki çizgilerle birbirine bağlanmış üç nokta olduğunu gösterin. Gary Chartrand

Örneğin, A, B, C, D, E, F noktalarını arayalım ve bunlardan birini seçelim, A diyelim. A'dan diğer beş noktaya çizilen beş çizgiden aynı renkte üç çizgi bulunmalıdır.

A'dan B'ye, C'den D'ye kadar tüm çizgilerin kırmızı olduğunu söyleyin. İki B, C, D arasındaki çizgi kırmızıysa, aralarında sadece kırmızı çizgiler bulunan üç nokta vardır. İki B, C, D arasında hiçbir çizgi kırmızı değilse, hepsi mavidir.

Ya sadece beş puan varsa? Aralarındaki tüm çizgilerin aynı renkte olduğu üç nokta olmayabilir. Örneğin, A --- B, B --- C, C --- D, D --- E, E - A çizgileri kırmızı, diğerleri mavi olabilir.

Gördüklerimize göre, bir partiye davet edilebilecek en az sayıda insan (her iki insanın da arkadaş veya yabancı olduğu), böylece üç ortak arkadaş veya üç ortak yabancı var.

Ya dört insanın karşılıklı arkadaş ya da karşılıklı yabancı olmasını istersek? Bundan emin olmak için bir partiye davet etmemiz gereken en az insan sayısı nedir? Bu soru cevaplandı. 18.

Ya beş kişinin karşılıklı arkadaş ya da karşılıklı yabancı olmasını istersek? Bu durumda, bunu garanti altına almak için bir partiye davet edecek en az sayıda insan olduğu bilinmemektedir. Kimse bilmiyor. Bu sorunun tarif edilmesi kolay ve belki de oldukça basit gibi görünse de, bilinen bir şekilde zordur.

Ramsey numaraları

Tartışmakta olduğumuz şey, grafik teorisinde Ramsey sayısı denilen bir sayı türüdür. Bu sayılar İngiliz filozof, iktisatçı ve matematikçi olarak adlandırılmıştır. Frank Plumpton Ramsey.

Ramsey, 26 yaşında öldü, ancak çok erken yaşlarında matematikte çok merak uyandırıcı bir teorem elde etti, bu da bizim sorumuza yol açtı. Diyelim ki kırmızı ve mavi çizgilerle birbirine bağlanmış noktalarla dolu başka bir uçağımız var. R ve s adında iki pozitif tamsayı seçiyoruz. Tam olarak aralarındaki tüm çizgilerin kırmızı olduğu noktalara veya aralarındaki tüm çizgilerin mavi olduğu noktalara sahip olmak istiyoruz. Bunu yapabileceğimiz en küçük puan nedir? Buna Ramsey numarası denir.

Örneğin, uçağımızın tüm kırmızı çizgilerle bağlı en az üç noktaya ve tüm mavi çizgilerle bağlı üç noktaya sahip olmasını istediğimizi söylüyoruz. Ramsey sayısı - bunun gerçekleşmesi için gereken en az sayı - altı.

Matematikçiler bir soruna baktıklarında, genellikle kendilerine soruyorlar: Bu başka bir soru öneriyor mu? Ramsey sayılarıyla ve parti problemleriyle bu oldu.

Örneğin, işte bir tane: Beş kız parti planlıyor. Bazı erkekleri partiye davet etmeye karar verdiler, erkekleri tanıyıp tanımadılar. Beş kızdan üçünün ya üç erkekle arkadaş olacağı ya da üç erkekle tanışmayacakları şekilde aralarında üç erkek olacağından emin olmak için kaç erkek çocuğu davet etmeleri gerekiyor? Muhtemelen cevabı iyi bir tahmin yapmak kolay değildir. 41!

Çok az sayıda Ramsey sayısı bilinmektedir. Ancak bu, matematikçilerin bu tür sorunları çözmeye çalışmasını engellemez. Genellikle, bir sorunu çözememek daha da ilginç bir soruna yol açabilir. Bir matematikçinin hayatı budur.

Yazarlar Hakkında

Gary Chartrand, Profesör Matematik Emeritus, Western Michigan University; Arthur Benjamin, Matematik Profesörü, Harvey Mudd Collegeve Ping Zhang, Matematik Profesörü, Western Michigan University

Bu yazı orijinalinde Konuşma. Okumak Orijinal makale.

İlgili Kitaplar:

at InnerSelf Pazarı ve Amazon