Can You Sum Some Cards?

You and a friend have a large deck of cards, each numbered $1$, $2$, $3$ or $4$, with plenty of each number. You take turns laying one card at a time on a pile. If at any moment the most recently played group of cards has the same sum as a group of cards played immediately before it, you both slap the pile. For example, each of these sequences is slapped when its last card is played:

• $3, 2, 3, 4, 1$ (the last two cards sum to $5$, as do the two before them);

• $1, 2, 4, 3, 3$ (the last card equals the card before it);

• $2, 3, 1, 2$ (the last two cards sum to $3$, as does the card before them).

How many cards are in the longest possible sequence that is never slapped?

The Fiddler, Zach Wissner-Gross, February 16, 2024(original post)

The official solution appeared in the post of February 23, 2024 and gives $9$ cards, with the single longest sequence $1,4,3,4,2,4,3,4,1$, agreeing with the answer below. The Extra Credit half of that post is paywalled, so the values $15$, $21$ and $31$ are my own.

Solution

Written out in full, a sequence $a_1, a_2, \dots, a_k$ is never slapped when there are no positions $p \le q < r$ with $$a_p + \dots + a_q \;=\; a_{q+1} + \dots + a_r ,$$ that is, no two neighbouring blocks of cards with equal sums. (A slap is checked every time a card is played, so in the finished sequence no such pair of blocks may appear anywhere.)

Block sums are differences of running totals, and that is the idea that tidies everything up. Let $S_0 = 0$ and let $S_j = a_1 + \dots + a_j$ be the total after $j$ cards. The two blocks above have sums $S_q - S_{p-1}$ and $S_r - S_q$, so they are equal exactly when $$S_q - S_{p-1} \;=\; S_r - S_q ,$$ which says that $S_{p-1}$, $S_q$, $S_r$ are three equally spaced numbers. So the puzzle becomes this: choose running totals $0 = S_0 < S_1 < \dots < S_k$, each step between $1$ and $4$, so that no three of them form an arithmetic progression. The cards are just the steps.

Small cases show how tight this is. With only $1$s, the totals $0,1,2$ are in progression, so one card is the most. With cards up to $2$, the steps must alternate (two equal steps make a progression), and $1,2,1$ with totals $0,1,3,4$ works while every fourth card fails, so three is the most. With cards up to $3$, the longest sequences have seven cards, for example $1,3,2,3,1,3,2$ with totals $0,1,4,6,9,10,13,15$.

For cards up to $4$, the sequence $1,4,3,4,2,4,3,4,1$ has totals $$0,\ 1,\ 5,\ 8,\ 12,\ 14,\ 18,\ 21,\ 25,\ 26 .$$ To confirm there is no progression, take each total as a possible middle term $m$ and each smaller total $x$; the third term would be $2m - x$, and in every case that number is not on the list. (For instance, with middle $12$ the smaller totals $0, 1, 5, 8$ would need $24, 23, 19, 16$, none of which appears.) So nine cards can be played. That nine is the most, and that this is the only nine-card sequence, takes an exhaustive search: there is no short hand argument, and the official solution also turns to the computer at this point. The search below tries every sequence, abandoning each as soon as it is slapped, and finds no unslapped sequence of ten cards. $$\boxed{\ 9 \text{ cards: } 1,4,3,4,2,4,3,4,1. \ }$$

The computation

The program plays the game as stated. It builds sequences one card at a time, and after each new card it checks every pair of neighbouring blocks that ends with that card, comparing their sums directly. A sequence that is slapped is not extended. It records the longest sequences found for each highest card from $1$ to $4$.

def slapped(seq):
    right = 0
    for q in range(len(seq) - 1, 0, -1):
        right += seq[q]                # block ending at the end
        left = 0
        for p in range(q - 1, -1, -1):
            left += seq[p]             # block just before it
            if left == right:
                return True
            if left > right:
                break
    return False

def longest(N):
    best = [[]]
    def grow(seq):
        if len(seq) > len(best[0]):
            best[:] = [seq[:]]
        elif len(seq) == len(best[0]):
            best.append(seq[:])
        for a in range(1, N + 1):
            seq.append(a)
            if not slapped(seq):
                grow(seq)
            seq.pop()
    grow([])
    return best

for N in range(1, 5):
    best = longest(N)
    print(N, len(best[0]), len(best), best[0])

It prints the highest card, the longest length, how many sequences reach it, and one of them:

1 1 1 [1]
2 3 2 [1, 2, 1]
3 7 4 [1, 3, 2, 3, 1, 3, 2]
4 9 1 [1, 4, 3, 4, 2, 4, 3, 4, 1]

With cards up to $4$ the longest unslapped sequence has nine cards, and there is exactly one.

Extra Credit

Suppose the cards are numbered $1$ through $N$. How many cards are in the longest sequence that is never slapped when $N = 5$, $6$ and $7$?

Solution

Nothing in the reformulation depended on the number $4$. For any $N$, the question is how many steps of size $1$ to $N$ can be taken from $0$ without three of the totals lying in arithmetic progression. Longer steps leave more room, so the answers grow, but not in a simple pattern. The values for $N = 1, 2, 3$ are $1, 3, 7$, which suggests $2^N - 1$, but $N = 4$ gives $9$, not $15$, so no tidy formula is at work. The answers for $N = 5$, $6$ and $7$ come from the exact search that follows, which finds these witnesses: $$\begin{align*} N = 5:&\quad 1,3,2,4,5,3,4,5,1,3,2,4,5,3,4 \quad (15 \text{ cards}),\\ N = 6:&\quad 3,5,4,6,4,3,5,4,6,5,6,2,6,5,6,1,3,5,6,1,6 \quad (21),\\ N = 7:&\quad 1,7,6,7,5,7,6,4,3,4,6,7,5,7,6,7,\\ &\quad 1,7,6,7,5,7,6,4,3,4,6,7,5,7,6 \quad (31). \end{align*}$$ The search also shows that none of them can be extended or beaten. $$\boxed{\ N = 5:\ 15 \text{ cards};\quad N = 6:\ 21;\quad N = 7:\ 31. \ }$$ The $N = 7$ record is a block of fifteen cards, then a $7$, then the same block again, the shape the official solution noticed for $N = 2$ and $3$.

The computation

For $N = 5$ and $6$ the direct search from The computation above runs in under a second. For $N = 7$ it takes about half a minute, so the program also runs a faster search on the running totals, which keeps the set of totals so far and rejects a new total $s$ whenever some earlier total $t$ has $2t - s$ among them (only totals $t \ge s/2$ can be the middle term, so it looks back just that far). The two searches must agree wherever both are run.

def longest_totals(N):
    S, seen, best = [0], {0}, [0]
    def makes_progression(s):
        for t in reversed(S):
            if 2*t < s:
                return False
            if 2*t - s in seen:
                return True
        return False
    def grow():
        best[0] = max(best[0], len(S) - 1)
        for g in range(1, N + 1):
            s = S[-1] + g
            if makes_progression(s):
                continue
            S.append(s); seen.add(s)
            grow()
            S.pop(); seen.discard(s)
    grow()
    return best

for N in (5, 6):
    print(N, "direct:", len(longest(N)[0]),
          "totals:", longest_totals(N)[0])
print(7, "totals:", longest_totals(7)[0])

It prints

5 direct: 15 totals: 15
6 direct: 21 totals: 21
7 totals: 31