middle school olympiad combinatorics has me stuck

Solution 1:

A sequence output by a program pointed me to A060963

And the required answer is $29\cdot 4! = 696$

Not many references in that, must be a hard problem then!

Solution 2:

OK here goes... after a bit of thought (not sure it was worth it) I have a manageable set of cases.

The "separations" between the pairs must be four different numbers from $0$ to $6$, having an even sum from $6$ to $12$. It is not too hard to enumerate all possibilities: we find that with one exception they all include $0,1$ or $2,3$ or $4,5$. The exception is $6,4,2,0$.

Case $0,1$: we need a row including components AA and BCB. Assume that AA comes before BCB. In the following, - denotes one unknown letter while o denotes zero or more unknown letters.

• If BCB is at the end then we have ---AABCB or ----DBCB. It is not hard to see that the first is impossible and the second can be completed in $3$ ways.
• If BCB is not at the beginning or end we have oAABCBDo or oAAoDBCBDo. The first can be completed in $3$ ways, the second also in $3$. Total so far, $9$ ways.

Case $2,3$: we need a row including components A--A and B---B. It is not hard to see that one of the As must occur between the Bs, the other before or after: assume it is before.

• The pattern oACBA--Bo can be completed in $2$ ways, but one includes gaps of $0,1$ and has already been counted above.
• The pattern oABCA-Bo can be completed in $2$ ways. Total so far, $12$ ways.

Case $4,5$: we must have A----A and B-----B, with a B occurring at the beginning or end: assume it is at the end. Then we have AB---ACB; it can be completed in $3$ ways, but one includes $0,1$ and has already been counted.

Total so far $14$ ways. But because of the symmetry assumptions I have made, each of these could be done in reverse: total, $28$ ways. It is easy to see that the pattern $6,4,2,0$ can be realised in only one way: total, $29$ ways. And finally, the letters S,I,T,H can replace A,B,C,D in $4!$ ways. Final answer, $29\times4!$.

Addendum. In answer to a comment, the sum of the "separations" must be even because if the locations are $a_1,a_2,b_1,b_2$ etc then we can write down the sum and simplify it modulo $2$ to get $$\eqalign{|a_1-a_2|-1+|b_1-b_2|-1+\cdots &\equiv a_1-a_2-1+b_1-b_2-1+\cdots\cr &\equiv a_1+a_2+b_1+b_2+\cdots\cr &=1+2+\cdots+8\cr &=36\cr &\equiv 0\ .\cr}$$

Solution 3:

First consider the problem with just $S,I,T$. What are those distances between same letters? They can be $0+2+4$, i.e. $SITTIS$, or $1+2+3$, i.e. $SITSTI$.

For four pieces, we want distinct nonnegative partitions adding up to at most $12$:
0+2+4+6: $HSITTISH$
1+2+3+6: $HSITSTIH$
0+3+4+5: $SITHHSTI$
1+2+4+5: $SIHTHSTI$

These four partitions are the only ones possible with sum $12$. The biggest part can't be greater than 6. If the biggest part is 6, then the next biggest must be $\le 4$. The biggest part can't be $4$, since $1+2+3+4<12$.

What remains is counting how many arrangements are possible for each case. Certainly you can permute the letters ($4!$ ways for each). Three of them may be reversed to give a different order, and there may be other representatives not listed for the permutations. What is needed is a careful case analysis that my five-minute sketch does not have.

As David points out in the comments, the sum may be less than $12$. It does have to be even though.
6=0+1+2+3: $HHSITSTI$
8=0+1+2+5: $SITSTHHI$
8=0+1+3+4: unknown

various others, there seem to be many cases.