What is the minimum $a_{100}$?

Question

$100$ integers $a_1, a_2, \cdots, a_{100}$ satisfy the following conditions

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

• if $i < j$ then, $a_j \div a_i \neq 2$.

What is the minimum $a_{100}$ ?

The answer is less than or equal to 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

My conjecture is 149.

Answer 1

Let us work from the top down instead. Suppose we are given an upper bound $A\geq a_i$. Then for any odd number $x\leq A$ we may define $s$ to be the maximal exponent such that $$ 2^sx\leq A $$ If $s$ is odd we can at most include the numbers $2^1x,2^3x,...,2^sx$ among our choices for $a_i$. That makes $(s+1)/2$ numbers. If $s$ is even we can include $2^0x,2^2x,...,2^sx$ which makes $(s+2)/2$ numbers.

The exponents $s$ can be found for any given odd $x\leq A$ using the formula $$ s=\lfloor\log_2(A/x)\rfloor $$ so the most numbers we will be able to fit in given the bound $A$ must be $$ \max_i(A)=\sum_{x\leq A}^{x\text{ odd}}f(\lfloor\log_2(A/x)\rfloor) $$ where $f(s)=(s+1)/2$ if $s$ is odd and $f(s)=(s+2)/2$ if $s$ is even.

---

Computing this sum for $A=148$ and $A=149$ one obtains $$ \max_i(148)=99\quad\text{and}\quad\max_i(149)=100 $$ so indeed $a_{100}=149$ is optimal.

Answer 2

You can use the pigeon hole principle. Assume by contradiction that $1\leq a_{1}<\cdots<a_{100}\leq 148$. Cover the set $\{1,2,\ldots,148\}$ by the holes

{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}.

(i.e. take elements in $\{1,\ldots, 148\}$ that differ by a factor $2$, then add the elements that you did not pick yet).

You will see that there are exactly $99$ holes. As there are $100$ elements $a_{i}$, there must exist $a_{i}< a_{j}$ that lie in the same hole. This implies that $a_{j}=2a_{i}$, contrary to the assumption. So the minimum $a_{100}$ is indeed $149$.