2
$\begingroup$

this is follow up question of A bit complicated 20 card games.

As the person who determines the order of the cards without changing the numbers on them, you want to make it more difficult for the player by shuffling the deck different than the original order.

To minimize the sum of the cards chosen by the player, while assuming they will choose optimally to maximize their sum, what is the optimal arrangement of the cards?

the numbers are: 3,3,4,5,5,5,6,6,6,6,7,7,8,8,9,10,13,14,15,15

$\endgroup$
1
  • 1
    $\begingroup$ It turns out that there are 24046 optimal arrangements. $\endgroup$
    – RobPratt
    Jan 29 at 14:52

2 Answers 2

6
$\begingroup$

The player always has the four options:

1110-1110-1110-1110-1111

1101-1101-1101-1101-1101

1011-1011-1011-1011-1011

0111-0111-0111-0111-0111

Adding them all together gives

3 x sum of all cards + last card. Now, 4 x optimal picks >= sum of these four picks.

This gives the lower bound:

optimal picks >= 3/4 x sum of all cards + 1/4 x smallest card = 117 = 155 - 38. 38 = (155 - 3) / 4 is the sum of cards dropped.

Next, we show that we can indeed prevent the player from doing better.

With the arrangement

4 5 5 6 - 6 6 8 10 - 13 14 15 15 - 9 8 7 7 - 6 5 3 3

The four reference picks above each achieve 117, dropping 38 points.

Now, let us demonstrate that there are no better picks.

Case 1:

13 14 15 15 are all picked. Then 10 on the left and 9 8 on the right must be dropped and at least one more card on each side: At least 6 on the left and 5 (or two 3's) on the right. Sum: 38.

Case 2:

At least one of 13 14 15 15 was dropped. Compare to the reference pick that drops the same card. In the reference picks dropped cards are maximally spaced. In the pick at hand the dropped cards other than 13 14 15 15 therefore can only move inwards compared to the reference pick. (Note: that is not entirely true as on the right side we could move one out at the cost of having to drop the next one as well. One has to manually check that that is never worth it. Luckily, it's only a handful of cases.) But we have cunningly arranged the cards in such a way that inwards always means equal or upwards. Dropped points therefore can never be less than 38.

It is worth mentioning that while there are multiple arrangements that solve the puzzle they all must

sum to exactly 117 for each of the four reference picks; in particular, the last card must be a 3.

$\endgroup$
6
  • $\begingroup$ well done :) this is very well explained! $\endgroup$
    – Oray
    Jan 29 at 13:10
  • 2
    $\begingroup$ The linear programming relaxation of my ILP formulation also yields lower bound $117$, and the optimal dual variables provide a certificate of optimality that is similar to yours, with dual multipliers $0.25$ on each of these four player options: $$01110111011101110111 \\ 11101110111011101111 \\ 11011101110111011110 \\ 10111011101110111011$$ $\endgroup$
    – RobPratt
    Jan 29 at 15:38
  • $\begingroup$ In fact, the last two cards must both be $3$. $\endgroup$
    – RobPratt
    Jan 29 at 16:42
  • $\begingroup$ @RobPratt I don't see an obvious reason for the second 3. Does your analysis give one? $\endgroup$
    – loopy walt
    Jan 29 at 20:21
  • $\begingroup$ @loopywalt It is the same argument as yours, but using the four options in my earlier comment, where the 19th card appears four times. I also verified by inspection of all 24046 solutions. No other cards are fixed. $\endgroup$
    – RobPratt
    Jan 29 at 20:23
3
$\begingroup$

Via integer linear programming, the minimax sum turns out to be

117,

achieved by the following permutation (among many optimal permutations):

4 5 6 9 6 6 7 10 15 14 15 13 8 8 7 6 5 5 3 3

The best the player can then do is to select the following cards (1 = select, 0 = do not select):

10111011101101110111

Independent of the card values, for 20 cards it turns out that there are 1207 maximally feasible selections for the player (in the sense that changing a 0 to a 1 would violate the rule of avoiding 111100). Each of these selections corresponds to a constraint in the integer linear programming problem.

$\endgroup$
2
  • $\begingroup$ 11101110111011101111 is another solution to this. $\endgroup$
    – Oray
    Jan 29 at 8:20
  • $\begingroup$ @Oray as are 1101 x 5, 1011 x 5 and 0111 x 5. This is no coincidence, see last paragraph of my updated answer. $\endgroup$
    – loopy walt
    Jan 29 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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