Seleziona la lingua

Italian

Down Icon

Seleziona Paese

Spain

Down Icon

Il numero di Erdős

Il numero di Erdős
Erdos
Ritratto di Paul Erdös. CENTRO ERDOS

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.

EL PAÍS

EL PAÍS

Notizie simili

Tutte le notizie
Animated ArrowAnimated ArrowAnimated Arrow