Liczba Erdősa

Problem z zeszłego tygodnia został bardzo pomysłowo rozwiązany przez czytelniczkę, która niestety później usunęła swój komentarz. Zobaczmy, jak węgierscy matematycy Paul Erdős i Georges Szekeres, stali współpracownicy i współautorzy twierdzenia Erdősa-Szekeresa , rozwiązali go w swoim czasie. Wyszli od zasady szufladkowej i pomyśleli o podzieleniu zbioru pierwszych 2n liczb {1, 2, …, 2n} na n podzbiorów tak, aby — biorąc n + 1 liczb z początkowego zbioru — co najmniej dwie z nich znajdowały się w tym samym podzbiorze. Zatem, gdyby te podzbiory były takie, że dla dowolnych dwóch liczb w tym samym podzbiorze, jedna byłaby wielokrotnością drugiej, początkowe stwierdzenie zostałoby udowodnione.

W tym celu n podzbiorów definiuje się jako przecięcia zbioru {1, 2, …, 2n} z następującymi zbiorami: {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³…}, w którym każdy element dzieli następny w swoim podzbiorze, a ponadto każdą liczbę w początkowym zbiorze {1, 2, …, 2n} można zapisać jednoznacznie jako (2m-1) x 2ᴷ, więc należy ona do jednego z tych zbiorów. Nieco złożone wyjaśnienie Bretos Bursó podsumowuje następująco:

„Każda liczba naturalna jest iloczynem części parzystej i części nieparzystej (iloczynem jej czynników pierwszych równych 2 i iloczynem jej czynników pierwszych nieparzystych). Jeśli dwie różne liczby mają tę samą część nieparzystą, to jedna z nich dzieli drugą (ta, która jest podzielna przez 2 razy więcej niż druga, jest wielokrotnością drugiej). Liczby n + 1, które bierzemy, mają n możliwych części nieparzystych (1, 3, 5..., 2n-1), więc istnieją co najmniej dwie liczby z tą samą częścią nieparzystą”.

A skoro już o Erdősie i współpracy między matematykami mowa, nie sposób nie wspomnieć o liczbie Erdősa . Ten płodny węgierski matematyk miał nie mniej niż 509 bezpośrednich współpracowników, których liczba Erdősa (nE) wynosi 1; ci, którzy współpracowali z którymś z tych 509, ale nie bezpośrednio z Erdősem, mają nE równe 2 (czyli ponad sześć tysięcy) i tak dalej.

Jak myślisz, jaka może być Twoja liczba Erdősa, biorąc pod uwagę oszacowanie Fermia? Zadowoliłbym się rozsądnym przybliżeniem. (Wskazówka: jeśli będziesz regularnie czytać tę sekcję, będzie Ci o wiele łatwiej).

Hipoteza Erdősa-Szekeresa

Wspomnianego twierdzenia Erdősa-Szekeresa nie należy mylić z hipotezą o tej samej nazwie.

Twierdzenie głosi, że dla dowolnej pary liczb naturalnych (całkowitych i dodatnich) r i s, każdy ciąg o długości równej lub większej niż (r-1)(s-1) + 1 zawiera monotonicznie rosnący podciąg o długości s lub monotonicznie malejący podciąg o długości r.

Brzmi to skomplikowanie, ale prosty przykład wyjaśni tę koncepcję: dla r = 3 i s = 2, czyli (r-1)(s-1) + 1 = 3, każda permutacja trzech liczb ma albo rosnący podciąg o długości trzy, albo malejący podciąg o długości dwa. Biorąc sześć możliwych permutacji liczb 1, 2 i 3 (i zapisując te ciągi w uproszczonej formie):

• 123 ma w sobie rosnący podciąg o długości trzech: 123
• 132 ma malejący podciąg o długości dwóch: 32
• 213 ma malejący podciąg o długości dwóch: 21
• 231 ma dwa malejące podciągi o długości dwóch: 21 i 31
• 312 ma dwa malejące podciągi o długości dwóch: 31 i 32
• 321 ma trzy malejące podciągi o długości dwóch: 32, 31 i 21

Jak podszedłbyś do udowodnienia tego twierdzenia odwołując się do zasady szufladkowej? (Nie oczekuję ścisłego dowodu, a jedynie planu działania.)

Hipoteza Erdősa-Szekeresa jest uogólnieniem „problemu szczęśliwego zakończenia”, nazwanego tak przez Erdősa, ponieważ doprowadziła do małżeństwa jego przyjaciela i współpracownika Georgesa Szekeresa z australijską matematyczką Esther Klein. Ale to temat na inny artykuł.