Grafos e divisores.1

Do portal NRICH

Remexendo pola arañeira batín con este entretido xogo do web NRICH (enriching mathematics).   Participan dous xogadores alternativamente escollendo da grella de números da esquerda que, como se ve, contén os 100 primeiros naturais. As regras son moi sinxelas:
Regra 1.O primeiro xogador pode escoller calquera número menor que 50 (no exemplo puxen o 45).
Regra 2. O seguinte número debe ser sempre un múltiplo ou un divisor do anterior.
Finalización. Perde aquel que non poida coller ningún número máis.
O xogo pode propoñérse en calquera aula dos primeiros cursos da ESO xa que permite desenvolver o cálculo e a familiarización cos conceptos de múltiplo, divisor, número primo, número composto, coprimos,...
NRICH suxire dar novos enfoques ao xogo, como o de presentalo sen a restricción dada pola primeira regra para logo poñer en evidencia a súa necesidade se non queremos ter un xogo trivial. Tamén podemos investigar se hai algunha estratexia gañadora, ou se hai números que nos convén evitar. Claro que as posibilidades non rematan aquí. De ser moi complicada a abordaxe deste xogo, podería restrinxirse a outras versións que tiveran unha menor cantidade de números: 15, 20, 30, 50,... ou, se cadra, somos quen de aventurar que é o que sucede cando partimos de 101 números, ou 200, ..., 1000,...n,...
Tamén está a cuestión de cal é a maior cadea de números que podemos formar na grella da dereita. Por exemplo, na imaxe anterior tiñamos unha cadea de 11 números susceptible de ser ampliada. Para estudar o problema podemos ver que é o que pasa cos primeiros casos.
O problema parece que pode abordarse botando man dos grafos. Partimos dun conxunto de vértices numerados polos n primeiros números
$$S=\left\{ { v }_{ 1 },{ v }_{ 2 },{ v }_{ 3 },...{ v }_{ n } \right\}$$
Para establecermos as arestas usaremos a seguinte definición
$${ \forall i\neq j\quad v }_{ i }\quad e\quad { v }_{ j\quad  }\quad forman\quad unha\quad aresta\quad \Longleftrightarrow \quad i|j\quad ou\quad _{ \quad  }j|i$$
A un grafo así determinado podémoslle chamar grafo de divisores. No grafo de divisores dado polos cinco primeiros números está claro que a cadea máis longa que podemos formar ten unha lonxitude de 4 vértices: 3, 1, 2, 4.
Pero a pouco que pasemos dos primeiros casos, como era de esperar, o grafo vaise complicando. Para o grafo de divisores dos 13 primeiros números naturais teremos polo menos unha cadea de lonxitude 10 a seguinte: 9, 3, 6, 12, 4, 8, 1, 5, 10, 2 (ou 11, 1, 5, 10, 2, 8, 4, 12, 3, 9) que parece difícil de superar

Se lle chamamos f(n) ao valor da lonxitude da máxima cadea que podemos formar nun destes grafos de n números, acabamos de ver que f(4)=f(5)=4 e que f(13)=10. Podemos intentar obter unha táboa que nos ofreza pistas para intentar aventurar o resto dos valores de f(n). Pero a cuestión non é nada simple.
Parece ser que P. Erdös, R. Freud e N. Hegyvári estableceron que para valores de n o suficientemente grandes (nas fórmulas log indica o logaritmo neperiano):
$$f(n)\le (1-log2)n$$
Se quixeramos unha limitación inferior teriamos esta de A. D. Pollington:
$$\forall c>0\quad \exists N/n\ge N\Longrightarrow f(n)\ge n\cdot { e }^{ -(2+c)\sqrt { logn\cdot log(logn) }  }$$
O artigo de Erdös e cia. non falaba de grafos senón de permutacións a₁, a₂ ,a₃, ..., a_{n ,} dos primeiros enteiros 1,2,3,....,n. Ou máis suxerententemente, trataba das permutacións a₁, a₂,a₃, ..., a_i ,....de todos os números naturais. Concretamente dábanse resultados sobre o mínimo común múltiplo  e o máximo común divisor de dous elementos consecutivos nesas permutacións. Un dos teoremas cualificábano os propios autores de pobre resultado. Di o seguinte:
Dada unha permutación de todos os naturais a₁, a₂,a₃, ..., a_i ,....:
$$\bar { \underset { i }{ lim }  } \frac { \left[ { a }_{ i },{ a }_{ i+1 } \right]  }{ i } \ge \frac { 1 }{ 1-log2 } \simeq 3,26$$
Certamente é difícil imaxinar unha permutación  na que este límite fique dentro do ámbito da finitude.