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

Mock AIME 6 2006-2007 Problems/Problem 15

Problem

For any finite sequence of positive integers $A=(a_1,a_2,\cdots,a_n)$, let $f(A)$ be the sequence of the differences between consecutive terms of $A$. i.e. $f(A)=(a_2-a_1,a_3-a_2,\cdots,a_n-a_{n-1})$. Let $F^k(A)$ denote $F$ applied $k$ times to $A$. If all of the sequences $A, f(A), f^2(A),\cdots, f^{n-2}(A)$ are strictly increasing and the only term of $f^{n-1}(A)$ is $1$, we call the sequence $A$ $\textit{superpositive}$. How many sequences $A$ with at least two terms and no terms exceeding $18$ are $\textit{superpositive}$?

Solution

We perform casework backwards, inverting $f(A)$ once at a time. Beginning at the sequence $(1)$, we can create a multitude of sequences: \[(1,2);(2,3);(3,4);\ldots;(17,18)\] If the first term is $9$ or greater, then we cannot continue to invert, so we only consider the lesser cases. From $(8,9)$, we can create $1$ case, namely $(1,9,18)$. From $(7,8)$, we can create $3$ cases. Thus we conjecture that $(k,k+1)$ results in $17-2k$ additional cases. As a result, there are a total of $1+3+5+\cdots+13+15=64$ cases of length $3$. There are clearly also $17$ cases of length $2$.

Next, we consider length $4$. From $(4,5)$, we can create $(1,5,10)$, among others, which results in $(1,2,7,17)$, and we can shift $1$ greater again, so there are $2$ cases.

From $(3,4)$, we can create $(1,4,8)$ and $(2,5,9)$, among others, which each create $(1,2,6,14)$ and $(1,3,8,17)$ respectively when inverted. We can shift again, so there are $5$ and $2$ more cases respectively.

From $(2,3)$, we can create a total of $8+5+2=15$ cases (left as an exercise to the reader). Finally, we tackle $(1,2)$, which by the same token should produce $11+8+5+2=26$ cases of length $4$.

Consider length $5$. From the case $(1,2,4,8)$, we generate $(1,2,4,8,16)$, which can be shifted to produce $3$ cases. There are no other strings that can generate a length $5$ sequence inside the bounds, so we are done.

Thus the answer is $17+64+2+7+15+26+3=\boxed{134}$ such sequences.

Note: Although this casework may seem complicated, the reader should attempt this casework themselves; it is actually much easier than it appears to be.

~ eevee9406

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_6_2006-2007_Problems/Problem_15&oldid=247682"