The Game of Barranca

Question

Barranca is played with sixteen cards, numbered 1, 2, ... , 16. Two players alternately choose a card, until each has eight. The winner is the one who has a (sub)set of numbers whose product is 220, or, if neither player has that product, then the winner is the one who can display a product nearest to 220.

Can the first player always win?

What if instead of 220, the target is some other number N? In particular, do values of N exist such that if the target of the game is N, there is a winning strategy for the second player?

Answer 1

I'll address whether

values of N exist such that if the target of the game is N, there is a winning strategy for the second player[.]

The answer is

no.

First, a lemma:

If both players play optimally, the "1" card can be chosen last. ("Can" meaning that there may be multiple equally-optimally-played games, at least one of which has the "1" chosen last.)

This seems straightforward enough. In particular, note that

if there's some optimally-game with "1" earlier than last, you can switch its position with that player's last-chosen card's without making that player's strategy inferior. And you can switch "1" from second-to-last to last without making the first player's strategy inferior.

Now,

suppose the second player had a winning strategy for some N. Then the first player could adopt that strategy by choosing "1" first and effectively becoming the second player.

Answer 2

I have analyzed the game tree with this Python 2.7 code:

wcache = dict()
def winner(target,p1,p2):
    if not (p1,p2) in wcache:
        if len(p1) + len(p2) == 15: #all non-1 cards have been picked
            d1 = distance(p1,target); d2 = distance(p2,target)
            if d1 > d2: return -1
            if d1 < d2: return 1
            return 0
        if len(p1) > len(p2): #i.e. it's P2's turn
            wcache[(p1,p2)] = min(winner(target, p1.union([]), p2.union([i])) for i in (set(range(2,17)) - p1 - p2)) #lowest = best for P2
        else:
            wcache[(p1,p2)] = max(winner(target, p1.union([i]), p2.union([])) for i in (set(range(2,17)) - p1 - p2)) #highest = best for P1
    return wcache[(p1,p2)]

dcache = dict()
def distance(cards,target):
    if not cards in dcache:
        prods = set([1]) #set of partial products
        dist = target-1
        for i in cards: #iteratively attempt to add each card to our partial products
            nex = set()
            for j in prods: #only keep the partial products that aren't too large
                if j <= target + dist: nex.add(j)
                if i*j <= target + dist:
                    nex.add(i*j)
                    if dist > abs(i*j - target): dist = abs(i*j - target)
        dcache[cards] = dist
    return dcache[cards]

and found that the game is

a win for the first player. (Running 'winner(220,frozenset(),frozenset())' returns 1.)

in just under a minute. Unfortunately, in its current state, the code cannot provide information about optimal play.

Answer 3

Solution:

Player 1 wins by force

Case 1: Player 1 tries to take a set of numbers that multiply to 220, They can either pick up a card numbered 11, 5, 4, 2 or 10. However every card he picks can be countered by taking away the card that could complete the set which could put player 1's chances in jeopardy. Player 1 can take 11 however player 2 can continue by picking any of 2,4 because player 2 knows whatever player 1 picks up to complete 220 can be dealt by taking away the factor that completes the number. Thus player 1 chances are extremely unclear.

Case 2: A number less than 220 or higher than 220 is aimed. The only numbers possible are 216 and 224. Because none of 217,218,219,221,222,223 have all factors belonging to the set of 1 to 16. To aim for 224, Player 1 starts with taking up card 2.

Case 2A: player 2 picks x, where x =/= 4,16 Player 2 can simply pick a 4 with intention to get 11 to make a set of 220 by force. To prevent that player 2 has to take any of 11,5,10. Player 1 can win by picking a 16 or 9 as 16×2×7 and 16×14 or 2×9×12 and 4×6×9 are both possible and player 2 cannot make their own set of 216 in any possible way considering best play from player 1.

Subcase 2A, number picked by player 2 is 16. Then once again player 1 can pick 4 for the reason above mentioned. Player 2 has to pick one of 11,10,5 to prevent that and now player 1 has to pick 14 so as to prevent player 2 making 16,14 set. Now player 2 has to pick an 8 to prevent player 1 making 8×2×14. Player 1 can win by taking 9 thus threatening to make two sets at once which player 2 cannot deal with.

Case 2B: Player 2 picks up number 4 player 1 can proceed by picking 9. In this case, player 2 can hold off player 1 by picking 14 (or 16 but in that case, it would favour player 1 because after player 1 picks up a 14 serving double purpose of not letting opponent complete its set and meanwhile completing its own as 14×2×8 or 2×9×12) threatening to take 16. Player 1 forcefully has to take 16. Now player 2 takes 8 to make 8×4×7 for which player 1 has to pick 7 again. However at this point all possibilities of 216,224 has exhausted and therefore the closest number player 1 can aim is 210 for which he can make it by getting a 15. However player 2 cannot take 15 away because of the threat of 2×9×12 still remains. Hence it is impossible for player 2 manage a draw here.

Also player 2 cannot win by picking remaining cards as all the possibility of achieving 216 or 224 has been exhausted.

For any another number $N$: (Warning spoiler)

I claim that it is not winning for player 1 for every possible number $N$. Since, the conditions are symmetrical, we can assume if player 1 can force a win with x number of cards where $x = 2^n$, player 1 can force a win where 16 cards too. Without loss of generality, we assume the number of cards are 4 viz. 1,2,3,4
Player 1 wins trivially with $N<6$ or $N>8$. For $N=6$. Player 1 picks a 3, forces player 2 to pick 2, and player 1 wins by picking a 4.
For $N=7$, if player picks a 4, player 2 can pick a 2, and whatever player 1 picks, he cannot win by any means, as the difference between numbers and N obtained by both player will be same i.e 7-2 = 12-7. So this one singular case can be extrapolated and used to prove that it is not possible for player 1 to win everytime for any $N$.

Answer 4

220 is 2^2 * 5 * 11, it can be obtained as (2,10,11) and (4,5,11)
216 is 2^3 * 3^3, it can be obtained as (2,9,12), (3,6,12), (3,8,9), (4,6,9), (2,3,4,9)
224 is 2^5 * 7, it can be obtained as (14,16), (2,7,16), (2,8,14), (4,7,8)

Then, next closest is 225 (3,5,15), followed by 210 - (2,3,5,7), (2,7,15), (5,6,7), (3,7,10).

Sometimes solution refers to "we" = first player, and "he" = second player. Sorry for not sticking to any particular way.

WARNING, SPOILERS BELOW!

As we can see, 220 is trivial to block. 216 and 224 are slightly harder to block with more combinations. Out of these numbers, 2 and 4 pop out - they are both present in both the 220 and 216/224 combos. So, it seems the winning strategy should pick one of those two. Let's first try with 2. Second player then picks

Anything but 4: we pick 4. Second player cannot assemble 220, and picks second number:
0) He doesn't have any of 5,10,11 - we pick 11, then 5 or 10 in the next turn assembling 220, we win.
So, he has one of these three numbers plus:
1A) Anything but 9, 14 or 16 - first player picks 9, then (4,6,9), (2,3,4,9) or (2,9,12) is inevitable. Blocking any of second player attempts at his own 216/224 is trivial and costless.
1B) On picking 14 or 16, first player grabs the other number, then the second player is required to block one of the (2,8,14) or (2,7,16). First player then picks 9. 216 is forced.
1C) On picking 9, we grab 14. Either (2,8,14) or (14,16) cannot be blocked.

So, now for the interesting case where the second player picked 4. We ignore the 220 possibility and NOT pick anything that would lead towards it (if we pick 11 he gets 10, that's it)

What are the options left? Well, both can still get (14,16), (3,6,12) and (3,8,9). The first player can hope for (2,9,12), (2,7,16) and (2,8,14). The second can hope for (4,6,9) and (4,7,8). (2,3,4,9) is gone.

Here, the immediate threat of the second player is getting 8 and 9, opening triplets (3,8,9), (4,6,9) and (4,7,8). If we pick something outside of these three sets (eg 14), he gets 9, so we need 6, then he gets 8, so we need 7, then he gets 3 and draws. So, we need to get one of these numbers. Which? 3) He gets 9, then we get 6, he gets 7, we get 8, he gets 14, we get 16. Drawish. 6) He gets 8, we pick 7, he gets 9, we pick 3, he gets 16, we pick 14, he gets 12. Maybe winning but I haven't checked if this is the optimal play. 8) Second player gets 9, we get 6, he gets 14, we get 16, he picks 7. Drawish. 9A) Second player gets 7, we get 8, he gets 14, we get 16 and he loses, he cannot defend against 3,8,9 and 2,9,12 while losing all his chances. 9B) Second player gets 8, we get 7, he gets 16, we get 14, he gets 12. This seems promising.

Now, number 210 is the threat. We get 15 and complete it. He lacks 7 and cannot get it. He can't get to 225 either, and there are no number closer or equal distance to 220.

Finally, analyzing what would happen if we start with the other candidate - number 4. Obviously, if he picks anything but 2 we refer to 2,4 case above. So, the options left are similar to the case above, only with players inverted. If we pick anything but 14 or 16, he gets 14 or 16, depending what we got. We cannot block both (14,16) and (2,8,14)/(2,7,16). 16 fails to picking 8 and 9 (we need to block with 14 and 12, but 3,8,9 remains). 14 is plausible, he cannot make a triplet, we block him. (he 9, we 12), (he 16, we 7), (he 8, we 3)... we end up with 7 again and can make 210 as 3,7,10, winning the game again.

So, the game will end with first player winning with score 210 if both play optimally. There are two possible first moves, after which most other moves are forced.