|
22n-1 odd numbers are chosen from
{22n + 1, 22n + 2, 22n + 3, ... ,
23n}. Show that we can find two of them such that neither has its
square divisible by any of the other chosen numbers.
--- x ---
Acho que estou longe de resolver o problema, mas tive umas
idéias interessantes e gostaria de discuti-las aqui na lista...
A idéia que tive é de um algoritmo que seleciona ímpares
dentro desse intervalo, esse algoritmo tem umas propriedades
interessantes:
- Tomamos um ímpar do intervalo, como 22n + 1 e
fatoramos em primos, sejam p[1], ..., p[d] tais primos de forma que
22n + 1
= p[1]s[1]...p[d]s[d].
- Construa uma árvore d-ária, ou seja uma árvore que
possui até d nós filhos, sendo que no i'ésimo nó filho, incluímos o inteiro
p[1]s[1]....p[i]s[i]+1...p[d]s[d]. A construção
é válida desde que o número formado esteja dentro dos limites.
- Se a árvore possuir mais de um elemento ela
possui a propriedade de que para cada elemento dela existe um elemento nela
mesma que divide o seu quadrado.
dem: é fácil ver que os filhos tem seus
quadrados divididos pelo seu pai e ancestrais, no caso da raiz, como a diferença
dela e de um de seus filhos é apenas 1, em 1 dos fatores primos, ao elevarmos ao
quadrado o filho da raiz divide o quadrado da raiz (nenhum dos s[i] é
zero...).
- Se construirmos todas as árvores com mais de um elemento
possíveis dentro desse intervalo e fizermos a união de seus elementos temos um
conjunto S, onde para todo x pert. S existe um y != x, y pert. S tq y
divide x².
- Talvez ainda seja possível inserir elementos que não
formam uma árvore mas que sejam múltiplos de um elemento de S, mas acredito que
esses casos sejam raros, pois precisaríamos ter um número cuja fatoração em
primos só possui primos grandes o suficiente para que ao aumentar em 1 o
expoente do menor primo dessa fatoração o novo número ultrapasse o limite de
23n.
- Outra propriedade interessante é que se quisermos menos
elementos, podemos simplesmente eliminar elementos ramos dessas árvores sem
quebrar a propriedade desejada.
- Acredito que ao complementar o conjunto S da forma acima
ele se torna maximal, no sentido que não existe um outro conjunto de ímpares no
intervalo que mantenha a propriedade.
- Infelizmente não tive idéias para contar ou estimar um
limitante superior para o número de elementos de S e o número de elementos que
podem ser inseridos em S como complemento.
[ ]'s
|