Find, with proof, the number of positive integers whose base-$n$ representation consists of distinct digits with the property that, except for the leftmost digit, every digit differs by $\pm 1$ from some digit further to the left. (Your answer should be an explicit function of $n$ in simplest form.)
Problem
Source:
Tags: AMC, USA(J)MO, USAMO, function, combinatorics proposed, combinatorics
zhaoli
15.06.2005 17:47
See: http://www.unl.edu/amc/a-activities/a7-problems/problemarchive.html [Moderator edit: Also posted at http://www.mathlinks.ro/Forum/viewtopic.php?t=60243 .]
ehehheehee
28.09.2006 00:33
Picture instead of a number base n, a numberline from 0 to n-1.
Place a point to represent the first number of n. After that point, place additional points to represent the other numbers after the first. There will be no gaps in the placement of the points (the points placed at any given time cover consecutive numbers).
Let the first digit of the number be x+1. There are x numbers to the left of x+1 and n-x-1 to the right of it. If the number is has all x numbers to the left of x+1 in it, the number of possibilities are (Let aCb be a choose b):
xCx+(x+1)Cx+(x+2)Cx...(n-1)Cx= by hockeystick identity(n)C(x+1)
counting the possibilities for only x-1 of the numbers to the left of x+1, x-2, x-3...0 numbers we have:
(n)C(x+1)+(n-1)C(x)...(n-x-1)C(0)=(n)C(n-x-1)+(n-1)C(n-x-1)...(n-x-1)C(n-x-1) (since aCb=aC(a-b))=(n+1)C(n-x)
Now we count all possibilities for x
(n+1)C(n-1)+(n+1)C(n-2)...+(n+1)C(2)=x^(n+1)-2n-2 (I need to go)
Phelpedo
26.03.2009 08:38
Let $ f_n$ denote the number in question. We consider two cases:
Case 1: The first digit is $ n - 1$. Now there are only $ n$ possible numbers: $ n - 1$, $ (n - 1)(n - 2)$, ... , $ (n - 1)...(0)$.
Case 2: Let's suppose the first digit is $ m < n - 1$. Now there are two possibilities for the next digit: $ m + 1$ or $ m - 1$. In either case, combine these first two digits into a block. Now we see that this constitutes a bijection to the numbers of $ f_{n - 1}$. Thus this case contributes $ 2f_{n - 1}$ numbers.
Our recursion is $ f_n = n + 2f_{n - 1}$. This should be pretty standard to solve:
We create a sequence $ g_n + k = f_n$. We want this to satisfy $ g_n = \alpha g_{n - 1}$, so $ k = - n$. So we have the recursion $ g_n = 2g_{n - 1}$. That means $ g_n = 2^{n - 1}g_1$. Since $ g_1 = 1$, we have that $ g_n = 2^{n - 1}$ and $ f_n = 2^{n - 1} + n$.
Aryth
01.04.2009 22:35
Phelpedo wrote:
Let $ f_n$ denote the number in question. We consider two cases:
Case 1: The first digit is $ n - 1$. Now there are only $ n$ possible numbers: $ n - 1$, $ (n - 1)(n - 2)$, ... , $ (n - 1)...(0)$.
Case 2: Let's suppose the first digit is $ m < n - 1$. Now there are two possibilities for the next digit: $ m + 1$ or $ m - 1$. In either case, combine these first two digits into a block. Now we see that this constitutes a bijection to the numbers of $ f_{n - 1}$. Thus this case contributes $ 2f_{n - 1}$ numbers.
Our recursion is $ f_n = n + 2f_{n - 1}$. This should be pretty standard to solve:
We create a sequence $ g_n + k = f_n$. We want this to satisfy $ g_n = \alpha g_{n - 1}$, so $ k = - n$. So we have the recursion $ g_n = 2g_{n - 1}$. That means $ g_n = 2^{n - 1}g_1$. Since $ g_1 = 1$, we have that $ g_n = 2^{n - 1}$ and $ f_n = 2^{n - 1} + n$.
sorry to bump the topic again, but isn't this not correct? suppose n = 2, then you have 1 and 10, but you have $ f_2 = 2^1 + 2 = 4$... I think it has to do with what's in your "Now we see that this constitutes a bijection to the numbers of $ f_{n - 1}$. Thus this case contributes $ 2f_{n - 1}$ numbers."
Infinite_Epsilon
11.04.2009 05:27
Yeah, there is a problem with that bijection, although we can actually use that bijection to solve the problem. Pretend that we can start a number with the digit 0. Let $ f_{n}$ be the number of solutions in this case. Then, if we have an base $ n$ number, it is either one digit long, or it is at least 2 digits long. If it is a one digit number, there are $ n$ possibilities, since there are $ n$ digits including 0. If the number has at least two digits, let the digits be $ a$ and $ a+1$. Then, the number can be finished in the same number of ways as the base $ n-1$ number beginning with $ a$. Since we can reach every $ a$ such that $ 0 \leq a < n-1$ in exactly two ways, we have $ 2f_{n-1}$ numbers with at least two digits. Thus, we have $ f_{n} = 2f_{n-1} + n$ with $ f_{1} = 1$, so solving $ f_{n} = 2^{n+1} - 2 - n$, which is trivial to prove by induction. Subtracting out the $ n$ numbers that start with the digit zero, we find that the number of solutions is $ 2^{n+1} - 2 - 2n$
Infinite_Epsilon
11.04.2009 05:40
Alternately, we could prove this without solving an ugly recursion. Again allowing use of the leading digit 0, we note that in base $ n$ there is $ 1$ set of $ n$ consecutive digits, $ 2$ sets of $ n-1$ consecutive digits and so on. If we have $ k$ consecutive digits, building our number from the units digit to the left, since we must choose either the greatest or least digit in our set, we see that there are 2 choices for the units digit, 2 choices for the next left-most digit and so on, until the last digit is forced. Thus, there are $ 2^{k-1}$ possible numbers for any $ k$ consecutive digits. Thus, we have $ 1*2^{n-1} + 2*2^{n-2} + 3*2^{n-3} + ... + n*2^{0}$ total numbers. This collapses to be $ (2^{n} - 1) + (2^{n-1} - 1) + ... + (2^{1} - 1)$. This is equal to $ 2*(2^{n} - 1) - n = 2^{n+1} - 2 - n$. Subtracting the $ n$ numbers that start with the digit zero again, we find that the total number of solutions is $ 2^{n+1} - 2 - 2n$.
dchenmathcounts
12.09.2020 21:55
Bump! Let the leading digit be $m.$ Note there are $m$ numbers less than it and $n-m-1$ numbers greater than it. Then we choose some amount of the $m$ numbers less than $m$ and the $n-m-1$ numbers greater than $m.$ Note that this is essentially the same as making the numbers to the left identical and the numbers to the right identical since their order is fixed, so we want to find \[\sum_{a=0}^m\left(\sum_{b=0}^{n-m-1}\binom{a+b}{a}\right).\]This is equal to \[\sum_{a=0}^m\binom{a+n-m}{a+1}=\sum_{a=0}^m\binom{a+n-m}{n-m-1}\]by the Hockey Stick Identity, and this further simplifies into \[\binom{n+1}{n-m}-1=\binom{n+1}{m+1}-1.\]Now note that \[\sum_{m=1}^{n-1}\left(\binom{n+1}{m+1}-1\right)=\sum_{m=1}^{n-1}\binom{n+1}{m+1}-(n-1)=\left(2^{n+1}-\binom{n+1}{0}-\binom{n+1}{1}-\binom{n+1}{n+1}\right)-(n-1)=2^{n+1}-(2n+2),\]which is our answer.