¿Cuál es el mínimo $a_{100}$ ?

Question

$100$ números enteros $a_1, a_2, \cdots, a_{100}$ cumplen las siguientes condiciones

• $0 < a_1 < a_2 < \cdots < a_{100}$ .

• si $i < j$ entonces, $a_j \div a_i \neq 2$ .

¿Cuál es el mínimo $a_{100}$ ?

La respuesta es menor o igual que 149:

1, 3, 4, 5, 7, 9, 11, 12, 13, 15, 16, 17, 19, 20, 21, 23, 25, 27, 28, 29, 31, 33, 35, 36, 37, 39, 41, 43, 44, 45, 47, 48, 49, 51, 52, 53, 55, 57, 59, 60, 61, 63, 64, 65, 67, 68, 69, 71, 73, 75, 76, 77, 79, 80, 81, 83, 84, 85, 87, 89, 91, 92, 93, 95, 97, 99, 100, 101, 103, 105, 107, 108, 109, 111, 112, 113, 115, 116, 117, 119, 121, 123, 124, 125, 127, 129, 131, 132, 133, 135, 137, 139, 140, 141, 143, 144, 145, 147, 148, 149

Mi conjetura es 149.

Answer 1

Puedes utilizar el principio del encasillamiento. Supongamos por contradicción que $1\leq a_{1}<\cdots<a_{100}\leq 148$ . Cubrir el conjunto $\{1,2,\ldots,148\}$ por los agujeros

{1,2}, {3,6}, {4,8}, {5,10}, {7,14}, {9,18}, {11,22}, ...,
{65,130}, {67,134}, {68,136}, {69,138}, {71,142}, {73,146},
{75}, {76}, {77}, {79},..., {145}, {147}, {148}.

(es decir, tomar elementos en $\{1,\ldots, 148\}$ que difieren en un factor $2$ y, a continuación, añade los elementos que aún no hayas elegido).

Verá que hay exactamente $99$ agujeros. Como hay $100$ elementos $a_{i}$ debe existir $a_{i}< a_{j}$ que yacen en el mismo agujero. Esto implica que $a_{j}=2a_{i}$ contrariamente a lo supuesto. Por tanto, el mínimo $a_{100}$ es realmente $149$ .

Answer 2

Trabajemos de arriba abajo. Supongamos que nos dan un límite superior $A\geq a_i$ . Entonces para cualquier número impar $x\leq A$ podemos definir $s$ es el máximo exponente tal que $$ 2^sx\leq A $$ Si $s$ es impar podemos incluir como mucho los números $2^1x,2^3x,...,2^sx$ entre nuestras opciones para $a_i$ . Eso hace que $(s+1)/2$ números. Si $s$ es incluso podemos incluir $2^0x,2^2x,...,2^sx$ que hace que $(s+2)/2$ números.

Los exponentes $s$ para cualquier impar $x\leq A$ mediante la fórmula $$ s=\lfloor\log_2(A/x)\rfloor $$ por lo que la mayor cantidad de números que seremos capaces de encajar dado el límite $A$ debe ser $$ \max_i(A)=\sum_{x\leq A}^{x\text{ odd}}f(\lfloor\log_2(A/x)\rfloor) $$ donde $f(s)=(s+1)/2$ si $s$ es impar y $f(s)=(s+2)/2$ si $s$ es par.

---

Calculando esta suma para $A=148$ y $A=149$ se obtiene $$ \max_i(148)=99\quad\text{and}\quad\max_i(149)=100 $$ Así es $a_{100}=149$ es óptima.