O número de Erdős

O problema da semana passada foi abordado de forma muito engenhosa por uma leitora que, infelizmente, posteriormente apagou seu comentário. Vejamos como os matemáticos húngaros Paul Erdős e Georges Szekeres, colaboradores regulares e coautores do teorema de Erdős-Szekeres , o abordaram em sua época. Eles partiram do princípio da casa dos pombos e pensaram em dividir o conjunto dos primeiros 2n números {1, 2, …, 2n} em n subconjuntos tais que — tomando n + 1 números do conjunto inicial — pelo menos dois deles estivessem no mesmo subconjunto. Assim, se esses subconjuntos fossem tais que, para quaisquer dois números no mesmo subconjunto, um fosse múltiplo do outro, a afirmação inicial estaria provada.

Para este propósito, os n subconjuntos são definidos como as interseções do conjunto {1, 2, …, 2n} com os seguintes conjuntos: {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³…}, em que cada elemento divide o próximo em seu subconjunto, e, além disso, cada número no conjunto inicial {1, 2, …, 2n} pode ser escrito unicamente como (2m-1) x 2ᴷ, então ele pertence a um desses conjuntos. Uma explicação um tanto complexa que Bretos Bursó resume da seguinte forma:

Todo número natural é o produto de uma parte par e uma parte ímpar (o produto de seus fatores primos igual a 2 e o de seus fatores primos ímpares). Se dois números distintos têm a mesma parte ímpar, então um deles divide o outro (aquele que é divisível por 2 a mais que o outro é múltiplo do outro). Os n + 1 números que tomamos têm n partes ímpares possíveis (1, 3, 5..., 2n-1), então há pelo menos dois com a mesma parte ímpar.

E por falar em Erdös e em colaborações entre matemáticos, não se pode deixar de mencionar o número de Erdös . O prolífico matemático húngaro teve nada menos que 509 colaboradores diretos, cujo número de Erdös (nE) é 1; aqueles que colaboraram com qualquer um desses 509, mas não diretamente com Erdös, têm um nE de 2 (mais de seis mil), e assim por diante.

Qual você acha que, usando uma estimativa Fermiana, seria o seu número de Erdős? Eu me contento com uma aproximação razoável. (Dica: se você ler esta seção regularmente, será muito mais fácil.)

A conjectura de Erdős-Szekeres

O teorema de Erdős-Szekeres acima mencionado não deve ser confundido com a conjectura de mesmo nome.

O teorema afirma que para qualquer par de números naturais (inteiros e positivos) r e s, qualquer sequência de comprimento igual ou maior que (r-1)(s-1) + 1 contém uma subsequência monotonicamente crescente de comprimento s ou uma subsequência monotonicamente decrescente de comprimento r.

Parece complicado, mas um exemplo simples esclarecerá o conceito: para r = 3 e s = 2, então (r-1)(s-1) + 1 = 3, qualquer permutação de três números tem uma subsequência crescente de comprimento três ou uma subsequência decrescente de comprimento dois. Tomando as seis permutações possíveis dos números 1, 2 e 3 (e escrevendo as sequências de forma simplificada):

• 123 tem uma subsequência crescente de comprimento três em si mesma: 123
• 132 tem uma subsequência decrescente de comprimento dois: 32
• 213 tem uma subsequência decrescente de comprimento dois: 21
• 231 tem duas subsequências decrescentes de comprimento dois: 21 e 31
• 312 tem duas subsequências decrescentes de comprimento dois: 31 e 32
• 321 tem três subsequências decrescentes de comprimento dois: 32, 31 e 21

Como você abordaria a prova desse teorema a partir do princípio da casa dos pombos? (Não estou pedindo uma prova rigorosa, apenas um plano de ataque.)

Quanto à conjectura de Erdős-Szekeres, trata-se de uma generalização do "problema do final feliz", assim chamado por Erdős porque levou ao casamento de seu amigo e colaborador Georges Szekeres com a matemática australiana Esther Klein. Mas isso é assunto para outro artigo.