9
$\begingroup$

Consider a deck of 52 cards in four mathy suits --two red: "adds" ($+$) and "subs" ($-$); and two black: "muls" ($\times$) and "divs" ($\div$)-- and thirteen numerical values --"A" (1), 2, 3, 4, 5, 6, 7, 8, 9, 10, "J" (11), "Q" (12), "K" (13).

A solitaire game on this deck arranges the cards into four stacks of thirteen cards each, according to two familiar rules:

  • Cards in a stack must alternate color
  • (Reading from the bottom of the stack) The cards must decrease in numerical value, although "K" is allowed to be placed on top of "A". Values within a stack must be consecutive.

For example, this is (part of) a valid stack of cards:

$[bottom] \;\; [5-] \;\; [4\times] \;\; [3+] \;\; [2\div] \;\; [A+] \;\; [K\times] \;\; [Q-] \;\; [J\times] \;\; [10+] \;\; [9\div] \;\; \cdots \;\; [top]$

Run-of-the-mill stuff, no? Well, consider that we assign a score to every stack of cards:

  • With an initial value of zero, (and again reading from the bottom) we apply the arithmetic operation represented by each card in turn. (That is, you can think of each card as Reverse Polish Notation instructions.)
  • Division rounds toward zero (so that every computation step yields an integer)

Edit. I changed the example to make more explicit use of rounding in the middle of a stack store computation, and to remove possibly-deceptive patterns in the suits.

The example partial stack would have a score of $-124$:

$(0) [5-] \rightarrow -5$ $(-5) [4\times] \rightarrow -20$ $(-20)[3+] \rightarrow -17$ $(-17)[2\div]\rightarrow -8.5 \rightarrow -8$ $(-8)[A+] \rightarrow -7$ $(-7) [K\times] \rightarrow -91$ $(-91) [Q-] \rightarrow -103$ $(-103) [J\times] \rightarrow -1133$ $(-1133) [10+] \rightarrow -1123$ $(-1123) [9\div] \rightarrow -124.777\dots \rightarrow -124$

Finally, we compute the game score:

  • The game score is the absolute value of the sum of the stack scores (NOT the sum of the absolute values).

Question: What's the largest possible game score?

A fairly naive computer search gave me a value of $915,382$. I'll accept an answer that proves this (or whatever better number) is optimal. (Proof can come in the form of a comprehensive computer search algorithm, though I'd prefer something "logical".)

UPDATE. I conducted a new and (I believe) comprehensive computer search, and have confirmed the $915,382$ maximum. (Perhaps-unsurprisingly, maximal arrangements --for the most part-- put "$+$" and "$\times$" cards into two stacks, and "$-$" and "$\div$" into the remaining stacks. There can be some fiddling with black bottom cards, since they all provide the same result when their "operation" is performed on zero.) @FelixCQ's observation that stack-starting values come in pairs of opposite color was the key to constructing a manageable search strategy, so I'm inclined to accept his answer. However, I'll leave the question open for a while longer in case anyone wants to put forth an analysis that doesn't involve checking 5.67 billion individual cases.

  • 0
    It looks like this problem asks for a full-tableau Canfield layout.2013-02-27

2 Answers 2

2

Let us assume that all 52 card must be used (in the context of Solitaire, one could imagine being stuck at some point, and then count the current score as the total score, but let us only consider cases with all cards being used).

Since cards must be consecutive, and since stacks are 13 cards long, the same value can only appear once per stack. Since there are only four stack, each value must appear exactly once per stack.

We therefore have four stacks (which we may call $+$, $-$, $\times$ and $\div$, based on the color of the Ace in the stack, for example).

As it has been pointed out, the stacks need not start with the same value; however, the first values of each stack are not all that independent:

  • Say the $+$ stack starts with value $k$, then it ends with value $(k \mod 13) + 1$ with same color.
  • This means that one of both card with value $k$ and opposite color is missing a predecessor, so it must start another stack. And of course the same can be said of the two other stacks.

So stacks' starting values go by two, with opposite colors.

The corrected number of cases to check is now $13^2 \cdot 2^{25} \approx 5,67\cdot10^{9}.$

This should still be manageable by a computer program, although it might take some time. :)

  • 0
    @DayLateDon: Indeed, I agree with your computation of the numerics. I have also edited out poorly expressed arguments.2011-10-14
1

I think with rounding towards 0 you can get $93,405,311,997$, rather larger than yours, with $[2-] \; [1\div] \; [13-] \; [12\div] \; \cdots \;[4-] \; [3\div] \; [2+] \; [1\times] \;[13+] \; [12\times] \; \cdots \; [4+] \; [3\times]$

I found this pattern by thinking that you want to try to neutralise the effects of the negatives and divisions before getting onto the serious business of building up your result. You also want subtraction before division to make the negative number halfway as small as possible, and addition before multiplication to get the final result as big as possible. Your constraint on the cards being in numerical order means that there are 13 patterns of this kind to check, and this seems to be the largest. I may have missed something including what you mean by stack scores.

  • 0
    Your strategy of maximizing with $+$ and $\times$ while minimizing with $-$ and $\div$ was part of what fed my own search, with the "adds" and "muls" filling two stacks and the "subs" and "divs" filling the remaining two stacks. This makes a lot of sense to me, but I haven't ruled-out the possibility that a clever tweak could boost the score by even a point.2011-10-13