Il numero di Erdős

Il problema della settimana scorsa è stato affrontato in modo molto ingegnoso da una lettrice che, purtroppo, ha poi cancellato il suo commento. Vediamo come i matematici ungheresi Paul Erdős e Georges Szekeres, collaboratori abituali e coautori del teorema di Erdős-Szekeres , lo hanno affrontato a loro tempo. Partirono dal principio del "casellaio" e pensarono di dividere l'insieme dei primi 2n numeri {1, 2, …, 2n} in n sottoinsiemi tali che – prendendo n + 1 numeri dall'insieme iniziale – almeno due di essi appartenessero allo stesso sottoinsieme. Pertanto, se questi sottoinsiemi fossero tali che, per due numeri qualsiasi nello stesso sottoinsieme, uno fosse multiplo dell'altro, l'affermazione iniziale sarebbe dimostrata.

A questo scopo, gli n sottoinsiemi sono definiti come le intersezioni dell'insieme {1, 2, …, 2n} con i seguenti insiemi: {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³…}, in cui ogni elemento divide il successivo nel suo sottoinsieme, e inoltre ogni numero nell'insieme iniziale {1, 2, …, 2n} può essere scritto univocamente come (2m-1) x 2ᴷ, quindi appartiene a uno di questi insiemi. Una spiegazione un po' complessa che Bretos Bursó riassume come segue:

Ogni numero naturale è il prodotto di una parte pari e di una parte dispari (il prodotto dei suoi fattori primi pari a 2 per quello dei suoi fattori primi dispari). Se due numeri distinti hanno la stessa parte dispari, allora uno di essi divide l'altro (quello divisibile per 2 volte in più dell'altro è un multiplo dell'altro). Gli n + 1 numeri che prendiamo hanno n possibili parti dispari (1, 3, 5..., 2n-1), quindi ce ne sono almeno due con la stessa parte dispari.

E a proposito di Erdös e collaborazioni tra matematici, non si può non menzionare il numero di Erdös . Il prolifico matematico ungherese ebbe non meno di 509 collaboratori diretti, il cui numero di Erdös (nE) è 1; coloro che collaborarono con uno qualsiasi di questi 509, ma non direttamente con Erdös, hanno un nE di 2 (ovvero più di seimila), e così via.

Quale pensi che, usando una stima fermiana, potrebbe essere il tuo numero di Erdős? Mi accontenterò di un'approssimazione ragionevole. (Suggerimento: se leggi questa sezione regolarmente, sarà molto più facile.)

La congettura di Erdős-Szekeres

Il suddetto teorema di Erdős-Szekeres non deve essere confuso con la congettura omonima.

Il teorema afferma che per qualsiasi coppia di numeri naturali (interi e positivi) r e s, qualsiasi sequenza di lunghezza uguale o maggiore di (r-1)(s-1) + 1 contiene una sottosequenza monotonicamente crescente di lunghezza s o una sottosequenza monotonicamente decrescente di lunghezza r.

Sembra complicato, ma un semplice esempio chiarirà il concetto: per r = 3 e s = 2, quindi (r-1)(s-1) + 1 = 3, qualsiasi permutazione di tre numeri ha una sottosequenza crescente di lunghezza tre o una sottosequenza decrescente di lunghezza due. Prendendo le sei possibili permutazioni dei numeri 1, 2 e 3 (e scrivendo le sequenze in forma semplificata):

• 123 ha una sottosequenza crescente di lunghezza tre in sé: 123
• 132 ha una sottosequenza decrescente di lunghezza due: 32
• 213 ha una sottosequenza decrescente di lunghezza due: 21
• 231 ha due sottosequenze decrescenti di lunghezza due: 21 e 31
• 312 ha due sottosequenze decrescenti di lunghezza due: 31 e 32
• 321 ha tre sottosequenze decrescenti di lunghezza due: 32, 31 e 21

Come affronteresti la dimostrazione di questo teorema partendo dal principio del "casellaio"? (Non chiedo una dimostrazione rigorosa, solo un piano d'attacco.)

Quanto alla congettura di Erdős-Szekeres, si tratta di una generalizzazione del "problema del lieto fine", così chiamato da Erdős perché portò al matrimonio del suo amico e collaboratore Georges Szekeres con la matematica australiana Esther Klein. Ma questo è un altro articolo.