Problem:
Find the number of functions f from {0,1,2,3,4,5,6} to the integers such that f(0)=0,f(6)=12, and
∣x−y∣≤∣f(x)−f(y)∣≤3∣x−y∣
for all x and y in {0,1,2,3,4,5,6}.
Solution:
Because f(n) and f(n+1) can differ by at most 3 for n=0,1,2,3,4,5, if f decreases k times, then 12=f(6)≤−1⋅k+3(6−k)=18−4k. This implies that f can decrease at most k=1 time.
If f never decreases, then f(n+1)−f(n)∈{1,2,3} for all n. Let a,b, and c denote the number of times this difference is 1, 2, and 3, respectively. Then a+b+c=6 and a+2b+3c=12. Subtracting the first equation from the second yields b+2c=6, so (b,c)=(6,0),(4,1),(2,2), or (0,3). These yield a=0,1,2, or 3 , respectively, so the number of possibilities in this case is
(60,6,0)+(61,4,1)+(62,2,2)+(63,0,3)=1+30+90+20=141
If f decreases from f(0) to f(1) or from f(5) to f(6), then f(2) or f(4), respectively, is determined. The only solutions to a+b+c=4 and a+2b+3c=10 are (a,b,c)=(1,0,3) and (a,b,c)=(0,2,2), so the number of functions is
2[(41,0,3)+(40,2,2)]=20
Finally, suppose that f(n+1)<f(n) for some n=1,2,3,4. Note that the condition ∣(n+1)−(n−1)∣≤∣f(n+1)−f(n−1)∣ implies that f(n+1)−f(n−1)≥2, so it must be that f(n)−f(n+1)=1 and
f(n+2)−f(n+1)=f(n)−f(n−1)=3.
This means that f(n−1) and f(n+2) are uniquely determined by the value of f(n), and, in particular, that f(n+2)−f(n−1)=5. As a result, there are three more values of f to determine, and they must provide a total increase of 7. The only ways to do this are either to have two differences of 3 and one difference of 1 , which can be arranged in 3 ways, or to have one difference of 3 and two differences of 2 , which can be arranged in 3 ways. Thus for each of the 4 possibilities for n, there are 6 ways to arrange the increases, giving a total of 24 ways.
The total number of functions is 141+20+24=185.
The problems on this page are the property of the MAA's American Mathematics Competitions