Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.
Sign up to join this community
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
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.
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.
