Maths Olympiad Prep

Library / /256 of 348

Combinatorics Difficulty 5.0 AIME, harder Find the answer

How many sequences of integers (a1,,a7)(a_{1}, \ldots, a_{7}) are there for which 1ai1-1 \leq a_{i} \leq 1 for every ii, and a1a2+a2a3+a3a4+a4a5+a5a6+a6a7=4a_{1} a_{2}+a_{2} a_{3}+a_{3} a_{4}+a_{4} a_{5}+a_{5} a_{6}+a_{6} a_{7}=4?

A number or a short expression. Spacing and $ signs are ignored.

Solution

For i=1,2,,6i=1,2, \ldots, 6, let bi=aiai+1b_{i}=a_{i} a_{i+1}. From the problem condition each of b1,b2,,b6b_{1}, b_{2}, \ldots, b_{6} can only be 1,0-1,0, or 1 . Since the sum of these six numbers is 4 , either there are five 1 s and a -1 or there are four 1 s and two 0s. In the first case, there are 6 ways to choose ii such that bi=1b_{i}=-1. Once that is fixed, determining the value of a1a_{1} (one of 1 and -1 ) will determine the value of all the remaining aia_{i} 's, so there are 62=126 \cdot 2=12 possible ways in this case. In the second case, since if one of b2,b3,b4,b5b_{2}, b_{3}, b_{4}, b_{5} is zero, then one of the adjacent term to this zero term must also be zero. Therefore the two zeroes must be next to each other or be b1b_{1} and b6b_{6}. If b1=b2=0b_{1}=b_{2}=0, then a2a_{2} must be zero. a1a_{1} 's value doesn't matter, and a3,a4,,a7a_{3}, a_{4}, \ldots, a_{7} must have the same sign. The same goes for b5=b6=0b_{5}=b_{6}=0, giving 322=123 \cdot 2 \cdot 2=12 possibilities in these two cases. If bi=bi+1=0b_{i}=b_{i+1}=0 for i=2,3,4i=2,3,4, then ai+1a_{i+1} must be zero. Moreover, a1,a2,,aia_{1}, a_{2}, \ldots, a_{i} must have the same sign, and so do ai+2,,a7a_{i+2}, \ldots, a_{7}. this gives 223=122 \cdot 2 \cdot 3=12 possibilities in these three cases. If b1=b6=0b_{1}=b_{6}=0, then a1=a7=0a_{1}=a_{7}=0. Also, a2,a3,,a6a_{2}, a_{3}, \ldots, a_{6} must have the same sign so there are 2 possibilities. Combining these cases gives 12+12+12+2=3812+12+12+2=38 possible sequences in total.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.