Problem 1019
Alice and Bob, sitting on the same side of the table, play "flip-flop". 6 cards, numbered from left to right from 1 to 6, have a blue face and a red face (the visible color of the starting cards is random).Each of the two players, in turn, chooses a "leader card" among those numbered 1 to 4 whose face is blue, then returns the leading card and the two following. Whoever cannot play anymore has lost. The winner scores 20 points minus the total number of moves played during the game, the loser scores that number of moves. Everyone plays for the best. Alice starts.
- 1A. If all the cards are blue at the start, who will win? Alice (answer 1) or Bob (answer 2)?
- 1B. 1B. What is the total number of moves played if both players try to optimize their score?
- 1C. Of the 16 possible orientations of the cards from 1 to 4 at the start, how many allow Alice to win?
- 2A, 2B, 2C. All cards are blue at the start. How many cards will lead an odd number of times?
We can model the problem by a graph. The vertices are the configurations of the 4 (or 10) cards that can be played, and the edges the possible transitions corresponding to a move. We can see that this graph is without cycle because if we consider blue cards as 0 and red cards as 1, the binary number encoded is always greater after the move. This graph is therefore a DAG.
Once the vertices and edges built, we can calculate a total order respecting the partial order of the DAG. This allows to simplify the processing of the vertices (by traversing them in this order or in the reverse order, we know that the vertices corresponding to the incoming or outgoing arcs have already been processed).
Once done, we can tag the vertices according to whether they correspond to a winning or losing node (by arbitrarily choosing a semantics, e.g. Alice starts playing), then by calculating the distance to the final vertex (with red cards only) considering that on a winning vertex, we try to take the shortest possible path, and on a losing vertex, a path as long as possible.
Finally, we can calculate the different paths corresponding to this distance. The written program can generate as a graph (in .dot format) the different paths. The explore_all_path parameter is used to enumerate all the paths (and to display them, to generate the graph, to count the number of times each card is leading), or to enumerate only the "optimal" paths (for parameter N = 10 , it is not recommended to explore all the paths).
For question 2, the statement is ambiguous, because if we assume that everyone is playing for the better (i.e. first tries to win, then to maximize they score), a player who loses may score more points than a player who wins... Indeed, with this strategy, we find a path length of 16, which, according to the statement, brings more points to the loser. Concerning this question, it is necessary either to be satisfied with the "optimal" paths following this definition (there are 146 paths), or to notice that the number of cards being the leader an odd number of times is always the same on millions of paths (if we start the full exploration). Analysis for optimizing the score only requires additional modelisation
The code is available here.
Once the vertices and edges built, we can calculate a total order respecting the partial order of the DAG. This allows to simplify the processing of the vertices (by traversing them in this order or in the reverse order, we know that the vertices corresponding to the incoming or outgoing arcs have already been processed).
Once done, we can tag the vertices according to whether they correspond to a winning or losing node (by arbitrarily choosing a semantics, e.g. Alice starts playing), then by calculating the distance to the final vertex (with red cards only) considering that on a winning vertex, we try to take the shortest possible path, and on a losing vertex, a path as long as possible.
Finally, we can calculate the different paths corresponding to this distance. The written program can generate as a graph (in .dot format) the different paths. The explore_all_path parameter is used to enumerate all the paths (and to display them, to generate the graph, to count the number of times each card is leading), or to enumerate only the "optimal" paths (for parameter N = 10 , it is not recommended to explore all the paths).
For question 2, the statement is ambiguous, because if we assume that everyone is playing for the better (i.e. first tries to win, then to maximize they score), a player who loses may score more points than a player who wins... Indeed, with this strategy, we find a path length of 16, which, according to the statement, brings more points to the loser. Concerning this question, it is necessary either to be satisfied with the "optimal" paths following this definition (there are 146 paths), or to notice that the number of cards being the leader an odd number of times is always the same on millions of paths (if we start the full exploration). Analysis for optimizing the score only requires additional modelisation
The code is available here.
- 1A. 2. Alice will lose.
- 1B. 6. The longest games have 6 moves.
- 1C. 8. There are 8 winning situations and 8 losing situations.
- 2A. 4. Cards leading an odd number of times: 1, 4, 7 and 10.