# Tag Info

20

I'll kick off with some observations. Determining a Nash Equilibrium for such a large solution space is not trivial. So here are some numerical attempts for much simpler problems: For problem a, it shows the following (with a lot of spurious accuracy!): [0 0 9] 0.08969140375863138 [0 2 7] 0.033696054860265535 [0 4 5] 0.029747584762232965 [0 3 6] 0....

18

I believe this is the answer. The strategy is below. Edit: Slightly clearer response with strategy.

15

Up to symmetries of the board, there aren't very many possible moves for the first player: Does this strategy work?

15

I would suggest an alternate (simpler) strategy:

13

The sequence continues because they are

10

The player who can win is by this strategy:

10

Nash equilibrium This task, including the uncertainty about what the opponent would pick, would be a classic fit for game theory, and it must have a solution that's locally optimal i.e. where anyone deviating would make their chances worse (the Nash equlibrium). It's not a question whether such a solution exists, it's well known and proven that it does. Of ...

9

First player wins Example:

9

The result is that

8

Answer to the non-bonus part: Proof: Bonus part: From 12 Hence

8

They decide that and the leader When

7

Here's a little Python program to test it yourself: https://repl.it/repls/ScientificIdenticalPixels And here's C++ code written by user @im_so_meta_even_this_acronym https://ideone.com/SfMHqC

7

First of all, lets present a strategy for $N=4$. $N=4$ $O$ can win in 7 moves (13 total). To start, the first two moves are arbitrary due to rotation and stretching, so let us assume we have the following; 1. $O_1=[0,0]$ 2. $X_1=[-1,-1]$ Now, $O$ will pick a line not on the $O_1,X_1$ line and place another point. $X$, meanwhile, should place a ...

7

7

You should To prove, let us first do the following

6

I think that the solution is Strategy Reasoning Why I chose these numbers

5

I think you can Here's my reasoning: Well, any two points can be connected by a line, right? Then you can see that The challenge is that your opponent can block the connections with a point of their own. But as you remember about Because of the {important} knowledge above, you see that Making the equation Let's do 4. By putting {Note: In this step ...

5

The player with the winning strategy is Strategy

5

The key fact is as follows: Therefore this particular game ends when the numbers on the board are So the conclusion is

5

5

This is an extension of Dr Xorile's observations, which fully answers the question that "there is no optimal strategy as long as knowdledge(and/or guessing) of your opponent distrubution is missing". But if we knew the opponents strategy, then a) Maximisation of wins b) Maximisation of enemy causalties It is interesting to see that even if we knew the ...

4

Let's name the lines. +---+---+ | K | +---+ L + J + | H I | + G +---+---+ | | +---+---+ F + | D E | + C + A +---+ | B | +---+---+ The winner can be found by analyzing the game regardless of the position. Now that we know the winner, who is which color? And Bob's last move would ...

4

Code to find the pattern: https://ideone.com/O5S4Qu (The third number printed out on each line is the winning move if the player to move is in a winning position)

4

Let’s see: I assume that all numbers must be greater than or equal to zero, otherwise the possibilities become too painful. If that was the intention, I’ll look harder. 1 2 3 4 5 6 7 8 9 10 11 Therefore the only starting numbers that win for Alice are Bonus Part: 12

4

For (b), defeating the greatest number of opposition soldiers? I either win or draw. No other combination delivers that result. For (a), winning the most platoon engagements: Seriously, it's a toss-up. It's rock-scissors-paper. For any combination, there is going to be a combination that defeats it. 10x10 is beaten by 9x11, which is beaten by 8X12, and ...

3

My solution: Proof: 1) The optimal strategy is to... 2) If both are playing optimal... 3) Bonus:

3

A lower bound is Represent the game as a bipartite graph $G$ on the set of cards and the set of positions. The game starts with a complete bipartite graph. Every turn, Bob guesses a perfect matching (of the complete bipartite graph). For each guessed edge $ab$, if Alice says it is wrong, then $ab$ is removed; otherwise, all other edges adjacent to $a$ and $... 3 Bob must've won the last round, resulting in fewer black cards in the remaining deck, otherwise he wouldn't call for a reshuffle. Sum of the won money is$\left(\frac{n}{2}\right)^2$, where$n$is the number of rounds played. So we have to solve:$\left(\frac{n_{1}}{2}\right)^2 + \left(\frac{n_{2}}{2}\right)^2 = \left(\frac{n_{3}}{2}\right)^2$, where$n_{1},...