Let $\text{N}$ denote the number of strictly increasing sequences of positive integers $a_1,a_2,\cdots, a_{19}$ satisfying the following two rules $:$

$a_1=1$ and $a_{19}=361,$
for any $i \neq j,$ if $b_{ij}$ is the $(i \cdot j)^{\text{th}}$ number not in the sequence $,$ then $(a_i-b_{ij})(a_j-b_{ij})<0.$

Find the largest positive integer $k$ such that $2^k$ divides $\text{N}.$

Solution 1

First, it is clear that $b_i$ is always increasing as $i$ increases. Notice that the condition $(a_i-b_{ij})(a_j-b_{ij})<0$ is equivalent to the condition $b_{ij}\in(a_i,a_j)$ , where $i<j$ . The first time we have $i=n$ for some positive integer $n$ is at $b_{n(n+1)}$ , which implies that $b_{n(n+1)}\in(a_n,a_j)$ , implying that $a_n<b_{n(n+1)}$ . Notice that this index of $b$ is minimized since at all lesser indices $n$ cannot be the smaller of the two factors $i,j$ (since $i\ne j$ ). Similarly, we note that the greatest value for which we have $j=n$ is at $b_{n(n-1)}$ since all greater indices would have $n$ being the smaller of the two factors. Thus $b_{n(n-1)}\in(a_i,a_n)$ and $a_n>b_{n(n-1)}$ .

Combining these facts, we see that $b_{n(n-1)}<a_n<b_{n(n+1)}$ and we note that $b_{n(n-1)}=n(n-1)+n-1$ by construction (since there are $n(n-1)$ other indices of $b$ of lesser value, and there are $n-1$ indices of $a$ from the inequality above). Similarly, $b_{n(n+1)}=n(n+1)+n$ . Therefore, after expanding, $n^2-1<a_n<n^2+2n$ which implies that $n^2\le a_n\le n^2+2n-1<(n+1)^2$ Clearly, there are no two $n$ such that the above intervals overlap (consider the squares at the extremes of this inequality) and so the location of each $a_n$ within each inequality is independent. Therefore, we consider the length of the interval; there are $n^2+2n-1-n^2+1=2n$ integers that $a_n$ could be in the interval. Then, if we consider $n=2,3,\ldots,18$ and permit them to vary, the total number of sequences is $\begin{aligned} N & = (2 \cdot 2) (2 \cdot 3) \dots (2 \cdot 18) \\ = 2^{17} \cdot 18! \end{aligned}$ We can calculate that $18!$ contains $9+4+2+1=16$ powers of $2$ , so the answer is $16+17=\boxed{033}$ .

~ eevee9406

2019 CIME I (Problems • Answer Key • Resources)
Preceded by Problem 8	Followed by Problem 10
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All CIME Problems and Solutions

Page

Toolbox

Search

2019 CIME I Problems/Problem 9

Solution 1

See also