Het Erdős-getal

Het probleem van vorige week werd zeer ingenieus aangepakt door een lezer die haar reactie helaas later verwijderde. Laten we eens kijken hoe de Hongaarse wiskundigen Paul Erdős en Georges Szekeres, vaste medewerkers en co-auteurs van de Erdős-Szekeres-stelling , het in hun tijd aanpakten. Ze gingen uit van het hokjesprincipe en bedachten om de verzameling van de eerste 2n getallen {1, 2, …, 2n} te verdelen in n deelverzamelingen, zodanig dat – door n + 1 getallen uit de beginverzameling te nemen – er ten minste twee in dezelfde deelverzameling zaten. Dus, als deze deelverzamelingen zodanig waren dat voor twee willekeurige getallen in dezelfde deelverzameling er één een veelvoud van de ander was, zou de beginstelling bewezen zijn.

Voor dit doel worden de n deelverzamelingen gedefinieerd als de snijpunten van de verzameling {1, 2, …, 2n} met de volgende verzamelingen: {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³…}, waarbij elk element het volgende in zijn deelverzameling deelt, en bovendien elk getal in de initiële verzameling {1, 2, …, 2n} eenduidig ​​kan worden geschreven als (2m-1) x 2ᴷ, zodat het tot een van deze verzamelingen behoort. Een ietwat complexe uitleg die Bretos Bursó als volgt samenvat:

Elk natuurlijk getal is het product van een even en een oneven deel (het product van zijn priemfactoren gelijk aan 2 en dat van zijn oneven priemfactoren). Als twee verschillende getallen hetzelfde oneven deel hebben, dan deelt het ene het andere (het ene is vaker deelbaar door 2 dan het andere een veelvoud is van het andere). De n + 1 getallen die we nemen hebben n mogelijke oneven delen (1, 3, 5..., 2n-1), dus er zijn er minstens twee met hetzelfde oneven deel.

En nu we het toch over Erdös en samenwerkingen tussen wiskundigen hebben, mag het Erdösgetal niet onvermeld blijven. De productieve Hongaarse wiskundige had maar liefst 509 directe medewerkers, van wie het Erdösgetal (nE) 1 is; degenen die met een van deze 509 samenwerkten, maar niet direct met Erdös, hebben een nE van 2 (dat is meer dan zesduizend), enzovoort.

Wat denk je, met behulp van een fermiaanschatting, dat jouw Erdősgetal zou kunnen zijn? Ik neem genoegen met een redelijke benadering. (Tip: als je dit gedeelte regelmatig leest, zal het veel makkelijker zijn.)

Het vermoeden van Erdős-Szekeres

De bovengenoemde stelling van Erdős-Szekeres moet niet worden verward met de gelijknamige veronderstelling.

De stelling stelt dat voor elk paar natuurlijke getallen (gehele getallen en positieve getallen) r en s, elke rij met een lengte gelijk aan of groter dan (r-1)(s-1) + 1 een monotoon toenemende deelreeks met een lengte s of een monotoon afnemende deelreeks met een lengte r bevat.

Het klinkt ingewikkeld, maar een eenvoudig voorbeeld verduidelijkt het concept: voor r = 3 en s = 2, dus (r-1)(s-1) + 1 = 3, heeft elke permutatie van drie getallen óf een stijgende deelreeks van lengte drie óf een dalende deelreeks van lengte twee. Neem de zes mogelijke permutaties van de getallen 1, 2 en 3 (en schrijf de reeksen in vereenvoudigde vorm):

• 123 heeft op zichzelf een stijgende subreeks van lengte drie: 123
• 132 heeft een afnemende subreeks van lengte twee: 32
• 213 heeft een afnemende deelreeks van lengte twee: 21
• 231 heeft twee afnemende deelreeksen van lengte twee: 21 en 31
• 312 heeft twee afnemende deelreeksen van lengte twee: 31 en 32
• 321 heeft drie afnemende deelreeksen van lengte twee: 32, 31 en 21

Hoe zou u deze stelling vanuit het hokjesprincipe bewijzen? (Ik vraag niet om een ​​sluitend bewijs, maar om een ​​aanpak.)

Wat de Erdős-Szekeres-hypothese betreft, het is een generalisatie van het "happy end-probleem", zo genoemd door Erdős omdat het leidde tot het huwelijk van zijn vriend en medewerker Georges Szekeres met de Australische wiskundige Esther Klein. Maar dat is een ander artikel.