O enigma do mercader

Os enigmas de Canterbury (1907) é o título dun libro de Henry Dudeney (1857-1930), un gran creador de xogos e retos matemáticos. O macguffin do relato consiste en que un grupo de preregrinos camiño de Canterbury coinciden nunha pousada e comezan a propoñerse enigmas. Cada un leva o nome de quen o presenta, aínda que normalmente a característica ou oficio do propoñente non garda relación co contido do problema. 

Posiblemente un dos máis versionados e coñecidos sexa o enigma do pousadeiro. 

O enigma do pousadeiro. O pousadeiro falou así: "Velaquí unha cuba de boa cervexa de Londres, e nas miñas mans sosteño dúas mediddas: unha de cinco pintas e a outra de tres pintas. Prégovos que me mostredes como é poible que poida poñer unha pinta en cada unha das medidas". Por suposto, non pode empregarse ningún outro recipiente ou elemento e non está permitido marcar as medidas.

Hai outra proposta na que me quería parar pois,a pesar de que Dudeney se estende demasiado na explicación, a pregunta é moi bonita.

O enigma do mercader. Eramos trinta en total cabalgando esta mañá. Certamente podemos ir un xunta o outro, no que é dado en chamar liña única, o u de dous en dous, ou de tres en tres, ou de cinco en cino, ou de seis en seis, ou de dez en dez, ou de quince en quince ou os trinta en columna. De ningunha outra forma podemos andar de modo que non existan números desiguais nas liñas. Agora,  un número de peregrirnos podían cabalgar así de 64 formas difrerentes. Prégovos que  me digades cantos peregrinos deberon consecuentetemente integrar a compañía. O mercader claramente pediu a menor cantidade de persoas que poideran cabalgar de sesenta e catro maneiras.

A cuestión non é outra que achar o menor número que teña 64 divisores. Para iso botamos man do resultado que nos di que se a descomposición factorial dun número é $$m=q_{1}^{\alpha _{1}-1}\cdot q_{2}^{\alpha _{2}-1} ... \quad q_{k}^{\alpha _{k}-1} $$ o seu número de divisores será $$\alpha _{1}  \cdot      \alpha _{2}    ... \:  \cdot   \alpha _{k} $$

Como no noso caso o número de divisores é 64,  $\alpha _{i} \in \left \{ 2,4,8,16,32,64 \right \} $ de aí que os expoñentes da descomposición factorial do número buscado deben estar entre os valores $ \alpha _{i} -1\in \left \{ 1,3,7,15,31,63 \right \}  $

Unha posible resposta é $m=2^{63}=99\,223\,372\,036\,854\,780\,000  $. Este número ten 64 divisores, pero teñamos presente que estamos buscando o menor número verificando esta propiedade. Este sería un caso extremo, o correspondente ao expoñente 63. Se partimos do outro caso extremo, se todos os expoñentes fosen 1, o resultado estaría formado polo produto dos seis primeiros primos $m=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13=30\ 030$. Ben, este xa é algo menor. Podémolo mellorar?

A resposta é afirmativa. O último factor é 13. É preferible colocar no seu lugar $2^{3}$. Nese caso a solución sería  $m=2^{3}\cdot 3\cdot 5\cdot 7\cdot 11=9\ 240$, que evidentemente é menor pois, aínda que multiplicamos o anterior valor por $2^{2}$, dividímolo por 13. 

Podemos seguir por este camiño. Unha alternativa sería pensar nunha potencia maior para o factor 2. O seguinte valor das potencias é 7. Isto significaría ter que multiplicar por $2^{4}=16$ e a cambio só conseguiriamos eliminar o factor 11. O resultado sería $m=2^{7}\cdot 3\cdot 5\cdot 7=13\ 440$, evidentemente un valor peor que o obtido anteriormente. De aí que debamos considerar incrementar a potencia de 3. Como [3³ =9 ] $3^{2}=9$ é, agora si, menor que 11, obtemos unha vantaxe ao multiplicar por 9. Neste caso o número obtido sería $m=2^{3}\cdot 3^{3}\cdot 5\cdot 7=7\ 560$. Non parece que poidamos mellorar este resultado pois para iso deberiamos incrementar a potencia do factor 5 a $5^{3}=125$, isto é, multiplicar m por 25 e a cambio só eliminariamos o factor 7. Finalmente denotaremos a solución como $A(64)= 7\ 560$ tal e como o fixo M. E. Grost no American Mathemathical Monthly nun artigo do ano 1968.

Acabamos de ver que obter o menor número con n divisores, A(n), non parece unha pescuda que se poida facer directamente. Con todo hai un caso simple. Se p é primo tense que $A(p)=2^{p-1}$.

A sucesión do menor número con n divisores (OEIS A005179) ten este desconcertante comezo (están marcados en letra grosa os valores dos lugares primos):

 1, 2, 4, 6, 16, 12, 64, 24, 36, 48, 1024, 60, 4096, 192, 144, 120, 65536, 180, 262144, 240, 576, 3072, 4194304, 360, 1296, 12288, 900, 960, 268435456, 720, 1073741824, 840, 9216, 196608, 5184, 1260, 68719476736, 786432, 36864, 1680, 1099511627776, 2880,...

Consideremos agora un número que sexa produto de dous primos, como o $6=3\cdot 2$. Non é dificil de ver que $A(6)=12=2^{2}\cdot 3$. Para $4=2\cdot2$, pois non dixemos que os primos tiñan que ser distintos, temos $A(4)=6=2\cdot 3$ e analogamente para $9=3\cdot3$ temos $A(9)=2^{2}\cdot 3^{2}=36$. No artigo referido Grost demostra que para todo número que sexa produto de dous primos $n=p\cdot q$ con $p\geq q$, o menor enteiro con n divisores será $A(n)=2^{p-1}3^{q-1}$. Nesta altura todos estariamos tentados a xeneralizar o resultado:

Xeneralización. Se $n=q_{1}\cdot q_{2}...q_{k}$ con $q_{1}\geq q_{2}\geq ...\geq q_{k}$ factores primos, entón $A(n)=p_{1}^{q_{2}}\cdot p_{1}^{q_{1}}...p_{k}^{q_{k}}$ onde $p_{i}$ é o i-ésimo número primo.

Desafortunadamente esta xeneralización non é certa, nin tan siquera para os números que son factores de tres primos. Por exemplo non se verifica para n=8 pois $A(8)=24=2^{3}\cdot 3\neq 2\cdot 3\cdot 5=30$. Tampouco se verifica para 16, 24, 32, 48,... Podemos lembrar que xa vimos que o 64 tampouco está entre os valores caracterizados pola xeneralización xa que $A(64)= 7\ 560\neq 2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13$. Grost chamoulle a estes números extraordinarios e, consecuentemente denominaría ordinarios a aqueles enteiros para os que si é certa a xeneralización. Resulta que hai unha infinidade de números extraordinarios pero en certo sentido os números ordinarios son máis abundantes entre os naturais. Resulta que os números ordinarios son densos nos naturais. Chamándolle $\alpha (n)$ á cantidade de números ordinarios menores ou iguais que n, o que se está afirmando é que $$\lim_{n\to\infty}\frac{\alpha (n)}{n}=1$$