1
$\begingroup$

In how many ways can $4$ integers $a_1<a_2<a_3<a_4$ be chosen from the integers $1,2,3,...,26$ such that $5 \le a_i - a_{i-1} \le 7$ for all $i = 2,3,4$?

I'm not sure what I'm missing in my line of thinking:

Since $5 \le a_i - a_{i-1} \le 7$, the difference between two consecutive integers chosen must be $5,6$ or $7$ (since everything's an integer). If I let $a_1 = 1$, then by incrementing the next integers by $7$ I see that the maximum I get is $22$. Therefore, the difference $a_i - a_{i-1}$ could be anything among $5,6,7$ for all $i$. Thus I have $3^3$ possibilities.

Similarly, letting $a_1$ be $2,3,4$ and $5$ all yields $3^3$ possibilities.

When I let $a_1 = 6$, however, if I keep incrementing by the biggest difference, $7$, the max. I get is $27$, which is $1$ more than the allowed maximum. That means I'm not allowed to use all three $7$'s for the difference but a maximum of two $7$'s. That gives me $3^3-1$ possibilities.

When I let $a_1 = 7$, the 'maximum' I get is $28$, $2$ more than $26$. Therefore, I can only use a maximum of one $7$. Since there is one case where I can use all three $7$'s and six cases in which I use two 7's, I have $3^3 - (1+6)$ possibilities.

For $a_1 = 8$ the 'maximum' $a_4$ is 29. So to fit in with $26$, I must not use any $7$'s at all. That gives me $2^3$ possibilities.

For $a_1 = 9$ I can get $a_4 = 30$ 'max'. To offset the difference of $4$, I cannot use 7's at all and one of the 6's. That gives me $4$ choices.

For $a_1 = 10$ I have $31$ 'max'. Now I can use only all 5's, or a maximum of one $6$ only. That's $4$ possibilities as well.

Finally, for $a_1=11$, I can only have the differences be $5$ all the time. So 1 possibility.

So the sum gave me $198$. But the answer is $216$. Where did I go wrong?

$\endgroup$
0
$\begingroup$

It is true that $a_1 = 1,2,3,4,5$ each give you $3^3$ possibilities.

Next, looking at $a_1 = 6$, we see that the possibility of $7,7,7$ is excluded, but every other possibility is included, so this gives $26$ possibilities.

Looking at $a_1 = 7$, only those totaling to $20$ or more are not allowed, which means that $757$, for example, is permissible, but you have excluded it. Hence we exclude $776,767,677$ and $777$ to get $23$ possibilities, not $27 -(1+6)$, rather $27-(1+3)$.

For $a_1 = 8$ only those totalling to $19$ or more must be excluded. That is, the above possibilities, plus $757$, $775$,$577$,$667,676,766$. This gives $17$ in total.

For $a_1 = 9$ the above, plus all permutations of $765$, and $666$, are excluded, giving $17-7 = 10$.

For $a_1 = 10$ the above plus all permutations of $755$ and $665$ are excluded, giving $4$ possibilities.

For $a_1 = 11$ only $555$ remains.

The total? $135 + 26 + 23+17+10+4+1 = 216$.

$\endgroup$
1
$\begingroup$

Let the consecutive increments be $x, y, z$. There are $27$ choices of $x, y, z \in \{5,6,7\}$.

Given a fixed choice of $x, y, z$, the number of ways to select the $a_i$'s is $f(x,y,z) = 26 - (a_4 - a_1) = 26 - (x + y + z)$.

Since $f(x,y,z)$ is linear, it is clear that its average value is $26 - 3 \times 6 = 8$.

Thus the answer is $27 \times 8 = 216$.

$\endgroup$
0
$\begingroup$

There is a mistake for $a_1 = 7$. The number of possibilities of having two $7$ isn’t $6$ but : $\binom{3}{2} = 3$.

Moreover, for $a_1 =8$, you are saying that there can’t be $7$, yet what about : $a_1 = 8, a_2 = 8+7 = 15, a_3 = 20, a_4 = 25$ ? (Same argument for $a_1 = 9$)

$\endgroup$
0
$\begingroup$

You've just skipped some possibilities. For example, you say that when $a_1=8,$ you can't use any $7'$s at all, but that's not so. You can use $5,6,7$ or $5,5,7.$ It's probably easier if you consider that you can make a maximum of $18$ with the $3$ increments.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.