Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2019 CIME I Problems/Problem 9"
(solution)
 
Line 5: Line 5:
  
 
=Solution 1=
 
=Solution 1=
−
{{solution}}
+
First, it is clear that <math>b_i</math> is always increasing as <math>i</math> increases. Notice that the condition <math>(a_i-b_{ij})(a_j-b_{ij})<0</math> is equivalent to the condition <math>b_{ij}\in(a_i,a_j)</math>, where <math>i<j</math>. The first time we have <math>i=n</math> for some positive integer <math>n</math> is at <math>b_{n(n+1)}</math>, which implies that <math>b_{n(n+1)}\in(a_n,a_j)</math>, implying that <math>a_n<b_{n(n+1)}</math>. Notice that this index of <math>b</math> is minimized since at all lesser indices <math>n</math> cannot be the smaller of the two factors <math>i,j</math> (since <math>i\ne j</math>). Similarly, we note that the greatest value for which we have <math>j=n</math> is at <math>b_{n(n-1)}</math> since all greater indices would have <math>n</math> being the smaller of the two factors. Thus <math>b_{n(n-1)}\in(a_i,a_n)</math> and <math>a_n>b_{n(n-1)}</math>.
 +
 
 +
Combining these facts, we see that
 +
<cmath>b_{n(n-1)}<a_n<b_{n(n+1)}</cmath>
 +
and we note that <math>b_{n(n-1)}=n(n-1)+n-1</math> by construction (since there are <math>n(n-1)</math> other indices of <math>b</math> of lesser value, and there are <math>n-1</math> indices of <math>a</math> from the inequality above). Similarly, <math>b_{n(n+1)}=n(n+1)+n</math>. Therefore, after expanding,
 +
<cmath>n^2-1<a_n<n^2+2n</cmath>
 +
which implies that
 +
<cmath>n^2\le a_n\le n^2+2n-1<(n+1)^2</cmath>
 +
Clearly, there are no two <math>n</math> such that the above intervals overlap (consider the squares at the extremes of this inequality) and so the location of each <math>a_n</math> within each inequality is independent. Therefore, we consider the length of the interval; there are <math>n^2+2n-1-n^2+1=2n</math> integers that <math>a_n</math> could be in the interval. Then, if we consider <math>n=2,3,\ldots,18</math> and permit them to vary, the total number of sequences is
 +
\begin{align*}
 +
N&=(2\cdot2)(2\cdot3)\cdots(2\cdot18)\
 +
&=2^{17}\cdot18!\
 +
\end{align*}
 +
We can calculate that <math>18!</math> contains <math>9+4+2+1=16</math> powers of <math>2</math>, so the answer is <math>16+17=\boxed{033}</math>.
 +
 
 +
~ [https://artofproblemsolving.com/wiki/index.php/User:Eevee9406 eevee9406]
 +
 
  
 
==See also==
 
==See also==

Latest revision as of 18:31, 16 April 2025

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 N=(2⋅2)(2⋅3)⋯(2⋅18)=217⋅18! We can calculate that $18!$ contains $9+4+2+1=16$ powers of $2$, so the answer is $16+17=\boxed{033}$.

~ eevee9406


See also

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2019_CIME_I_Problems/Problem_9&oldid=246821"