A387260 Number of strategies in the game "Risk or Safety" to reach n points.

1, 3, 31, 3011, 5755251, 357035589531

Offset: 1

Author

Ruediger Jehn, Aug 24 2025

Keywords

• nonn
• hard
• more
• new

Comments

The game "Risk or Safety" consists of two competing players. A player whose turn it is tosses a coin. If it is heads they earn a point, and they can choose to go for safety, put the point aside in a save box, and give the turn to their opponent. Or they take the risk to continue and toss the coin again. If it is heads again, the number of "open" points increases by one, and they can choose again to continue or stop, converting the "open" points to "saved" points. Whenever it is tails, all the open points are lost, and it is the turn of the other player. Who collects n points first wins.

If a game situation is described by a triple (a, b, c) with a = open points, b = saved points of the player whose turn it is, and c = saved points of the opponent, then the number of possible game situations is n^2(n + 1)/2 = A002411(n). One possibility to calculate the optimal strategy is to examine each triple with a > 0, derive the possible follow-on triples for each possible strategy at this situation, and determine for each stop/continue combination the one with the largest winning probability at this point in the decision tree of all strategies. It is assumed that one optimal strategy exists that both players are playing. For all possible strategies, a system of A002411(n) linear equations needs to be solved. Another approach is to simulate the game iteratively, selecting the solution with the highest winning probability after k turns, and continuing this process until no further improvements are made. Both methods have given the same results, although the matrix approach breaks down for n >= 6, since the inversion of hundreds of billions of 126 X 126 matrices is just not feasible.

The optimal solution for n = 3 is to stop at (1, 0, 0), else always continue. The average game duration is 6 (n = 2), 120/11 (n = 3), 258/17 (n = 4), and 5532/275 (n = 5).

Examples

			a(2) = 3: For n = 2, we have two game situations (1, 0, 0) and (1, 0, 1) where the players need to decide whether to stop or to continue. If the players choose to stop at (1, 0, 0) there are two strategies at (1, 0, 1): stop and continue. However, if the players choose to continue at (1, 0, 0), the position (1, 0, 1) will never be reached, and therefore in total, there exist only 3 strategies, not 4.
		

Crossrefs

Cf. A002411, A349697, A349698, A387261, A387262.