Erdős sayısı

Geçen haftanın problemi , ne yazık ki daha sonra yorumunu silen bir okuyucu tarafından çok ustaca ele alındı. Erdős-Szekeres teoreminin düzenli işbirlikçileri ve ortak yazarları olan Macar matematikçiler Paul Erdős ve Georges Szekeres'in zamanında bu problemi nasıl ele aldıklarına bir bakalım. Güvercin yuvası ilkesinden yola çıkarak ilk 2n sayının {1, 2, …, 2n} kümesini, başlangıç ​​kümesinden n + 1 sayı alarak, en az ikisinin aynı alt kümede olacağı şekilde n alt kümeye bölmeyi düşündüler. Dolayısıyla, bu alt kümeler, aynı alt kümedeki herhangi iki sayıdan biri diğerinin katı olacak şekilde olsaydı, ilk ifade kanıtlanmış olurdu.

Bu amaçla, n altküme, {1, 2, …, 2n} kümesinin şu kümelerle kesişimleri olarak tanımlanır: {1, 2, 2², 2³…}, {3, 3 x 2, 3 x 2², 3 x 2³…}, {5, 5 x 2, 5 x 2², 5 x 2³,…}, …, {n-1, (n-1) x 2, (n-1) x 2², n-1) x 2³…}, burada her eleman altkümedeki bir sonrakini böler ve ayrıca başlangıç ​​kümesindeki {1, 2, …, 2n} her sayı (2m-1) x 2ᴷ şeklinde benzersiz bir şekilde yazılabilir, dolayısıyla bu kümelerden birine aittir. Bretos Bursó'nun özetlediği biraz karmaşık bir açıklama şu şekildedir:

"Her doğal sayı, bir çift kısım ile bir tek kısmın çarpımıdır (2'ye eşit asal çarpanlarının çarpımı ile tek asal çarpanlarının çarpımı). İki farklı sayının tek kısmı aynıysa, biri diğerini böler (diğerinden 2 kat fazla bölünebilen sayı, diğerinin katıdır). Aldığımız n + 1 sayının n olası tek kısmı vardır (1, 3, 5..., 2n-1), yani aynı tek kısma sahip en az iki sayı vardır."

Erdös'ten ve matematikçiler arasındaki işbirliklerinden bahsetmişken, Erdös sayısından bahsetmemek olmaz. Bu üretken Macar matematikçinin en az 509 doğrudan işbirlikçisi vardı ve Erdös sayıları (nE) 1'di; bu 509 kişiden herhangi biriyle iş birliği yapanların, ancak Erdös ile doğrudan iş birliği yapmayanların nE'si 2'ydi (yani altı binden fazla) ve bu böyle devam ediyordu.

Fermiyen bir tahmin kullanarak Erdős sayınızın ne olabileceğini düşünüyorsunuz? Makul bir tahminle yetineceğim. (İpucu: Bu bölümü düzenli olarak okursanız, çok daha kolay olacaktır.)

Erdős-Szekeres varsayımı

Yukarıda sözü edilen Erdős-Szekeres teoremi aynı adlı varsayımla karıştırılmamalıdır.

Teorem, herhangi bir doğal sayı çifti (tam sayılar ve pozitif) r ve s için, (r-1)(s-1) + 1'e eşit veya daha büyük herhangi bir dizinin, uzunluğu s olan monotonik olarak artan bir alt dizi veya uzunluğu r olan monotonik olarak azalan bir alt dizi içerdiğini belirtir.

Kulağa karmaşık gelse de, basit bir örnek konuyu açıklığa kavuşturacaktır: r = 3 ve s = 2 için, yani (r-1)(s-1) + 1 = 3, üç sayının herhangi bir permütasyonunun ya üç uzunluğunda artan bir alt dizisi ya da iki uzunluğunda azalan bir alt dizisi vardır. 1, 2 ve 3 sayılarının altı olası permütasyonunu alalım (ve dizileri basitleştirilmiş biçimde yazalım):

• 123'ün kendi içinde üç uzunluğunda artan bir alt dizisi vardır: 123
• 132'nin uzunluğu iki olan azalan bir alt dizisi vardır: 32
• 213'ün uzunluğu iki olan azalan bir alt dizisi vardır: 21
• 231'in uzunluğu iki olan iki azalan alt dizisi vardır: 21 ve 31
• 312'nin uzunluğu iki olan iki azalan alt dizisi vardır: 31 ve 32
• 321'in uzunluğu iki olan üç azalan alt dizisi vardır: 32, 31 ve 21

Bu teoremi güvercin deliği ilkesinden yola çıkarak nasıl ispatlarsınız? (Kesin bir ispat istemiyorum, sadece bir saldırı planı istiyorum.)

Erdős-Szekeres varsayımı ise, Erdős'ün arkadaşı ve iş arkadaşı Georges Szekeres'in Avustralyalı matematikçi Esther Klein ile evlenmesine yol açtığı için bu adı verdiği "mutlu son problemi"nin genelleştirilmiş halidir. Ama bu başka bir yazının konusu.