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 "Mock AIME 6 2006-2007 Problems/Problem 15"

m
(solution)
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
−
{{Solution}}
+
We perform casework backwards, inverting <math>f(A)</math> once at a time. Beginning at the sequence <math>(1)</math>, we can create a multitude of sequences:
 +
<cmath>(1,2);(2,3);(3,4);\ldots;(17,18)</cmath>
 +
If the first term is <math>9</math> or greater, then we cannot continue to invert, so we only consider the lesser cases. From <math>(8,9)</math>, we can create <math>1</math> case, namely <math>(1,9,18)</math>. From <math>(7,8)</math>, we can create <math>3</math> cases. Thus we conjecture that <math>(k,k+1)</math> results in <math>17-2k</math> additional cases. As a result, there are a total of <math>1+3+5+\cdots+13+15=64</math> cases of length <math>3</math>. There are clearly also <math>17</math> cases of length <math>2</math>.
 +
 
 +
Next, we consider length <math>4</math>. From <math>(4,5)</math>, we can create <math>(1,5,10)</math>, among others, which results in <math>(1,2,7,17)</math>, and we can shift <math>1</math> greater again, so there are <math>2</math> cases.
 +
 
 +
From <math>(3,4)</math>, we can create <math>(1,4,8)</math> and <math>(2,5,9)</math>, among others, which each create <math>(1,2,6,14)</math> and <math>(1,3,8,17)</math> respectively when inverted. We can shift again, so there are <math>5</math> and <math>2</math> more cases respectively.
 +
 
 +
From <math>(2,3)</math>, we can create a total of <math>8+5+2=15</math> cases (left as an exercise to the reader). Finally, we tackle <math>(1,2)</math>, which by the same token should produce <math>11+8+5+2=26</math> cases of length <math>4</math>.
 +
 
 +
Consider length <math>5</math>. From the case <math>(1,2,4,8)</math>, we generate <math>(1,2,4,8,16)</math>, which can be shifted to produce <math>3</math> cases. There are no other strings that can generate a length <math>5</math> sequence inside the bounds, so we are done.
 +
 
 +
Thus the answer is <math>17+64+2+7+15+26+3=\boxed{134}</math> such sequences.
 +
 
 +
<i>Note:</i> Although this casework may seem complicated, it is easier for the reader to attempt this casework themselves; it is actually much easier than it appears to be.
 +
 
 +
~ [https://artofproblemsolving.com/wiki/index.php/User:Eevee9406 eevee9406]

Revision as of 20:57, 29 April 2025

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, it is easier for the reader to 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=247681"