Skip to main content
replaced http://mathoverflow.net/ with https://mathoverflow.net/
Source Link

I am reposting notzeb's solution to the 3 front case here, and making some comments on it. In particular, I will point out that the solution is not unique; while notzeb used fractal methods, I will give a piecewise smooth solution using the same ideas.

Idea of solution:

I claim that it is enough to find any probability distribution on $\{(p,q,r): p+q+r=1, \ p,q,r \geq 0 \}$ whose projection to each coordinate is the uniform measure on $[0,2/3]$.

Proof that such a measure works:

(For simplicity, I disregard ties.) Observe that it is impossible for either general to win on all fronts. Therefore, if I find a strategy that guarantees that I am expected to win at least 1.5 fronts against any opposing strategy, this means that I have probability at least 1/2 of winning 2 fronts against any opposing strategy. (This logic does not extend to the 5 front case.)

Suppose my enemy sends $p$ troops to the first front. I beat him with probability $\max(1-(3/2)p, 0)$. By linearity of expectation, if my enemy sends troops $(p,q,r)$, my expected number of victories is $$\max(1-(3/2)p, 0)+\max(1-(3/2)q, 0)+\max(1-(3/2)r, 0)$$ $$\geq 3-(3/2)(p+q+r) = 3/2.$$ If my opponent adopts a mixed strategy, linearity shows that I still have expected number of victories at least $3/2$. QED

notzeb's measure:

Take the triangle of possible solutions and inscribe a hexagon in it, with vertices at the permutations of $(0,1/3,2/3)$. All our solutions will be inside that hexagon.

Now, take that hexagon and place 6 smaller hexagons in it as shown below.

6 Hexagons in 1 http://www-math.mit.edu/%7Espeyer/3front.png

Choose one of those 6 hexagons uniformly at random. Place 6 smaller hexagons inside that one, and choose one of these uniformly at random again. Keep going. The hexagons shrink in size each time; the limiting point is your army distribution.

Notice that the space of possible solutions is a Sierpinski-gasket-like figure, of Hausdorff dimension $\log 6/\log 3$. It is cute to observe that the white star of David in the center becomes a Koch snowflake of excluded points in the final solution.

My alternate measure

Inscribe a circle in the triangle. On that circle, place the measure $dA/\sqrt{1-r^2}$, as described in [Harald Hanche-Olsen's answer][3] to a different question.

I am reposting notzeb's solution to the 3 front case here, and making some comments on it. In particular, I will point out that the solution is not unique; while notzeb used fractal methods, I will give a piecewise smooth solution using the same ideas.

Idea of solution:

I claim that it is enough to find any probability distribution on $\{(p,q,r): p+q+r=1, \ p,q,r \geq 0 \}$ whose projection to each coordinate is the uniform measure on $[0,2/3]$.

Proof that such a measure works:

(For simplicity, I disregard ties.) Observe that it is impossible for either general to win on all fronts. Therefore, if I find a strategy that guarantees that I am expected to win at least 1.5 fronts against any opposing strategy, this means that I have probability at least 1/2 of winning 2 fronts against any opposing strategy. (This logic does not extend to the 5 front case.)

Suppose my enemy sends $p$ troops to the first front. I beat him with probability $\max(1-(3/2)p, 0)$. By linearity of expectation, if my enemy sends troops $(p,q,r)$, my expected number of victories is $$\max(1-(3/2)p, 0)+\max(1-(3/2)q, 0)+\max(1-(3/2)r, 0)$$ $$\geq 3-(3/2)(p+q+r) = 3/2.$$ If my opponent adopts a mixed strategy, linearity shows that I still have expected number of victories at least $3/2$. QED

notzeb's measure:

Take the triangle of possible solutions and inscribe a hexagon in it, with vertices at the permutations of $(0,1/3,2/3)$. All our solutions will be inside that hexagon.

Now, take that hexagon and place 6 smaller hexagons in it as shown below.

6 Hexagons in 1 http://www-math.mit.edu/%7Espeyer/3front.png

Choose one of those 6 hexagons uniformly at random. Place 6 smaller hexagons inside that one, and choose one of these uniformly at random again. Keep going. The hexagons shrink in size each time; the limiting point is your army distribution.

Notice that the space of possible solutions is a Sierpinski-gasket-like figure, of Hausdorff dimension $\log 6/\log 3$. It is cute to observe that the white star of David in the center becomes a Koch snowflake of excluded points in the final solution.

My alternate measure

Inscribe a circle in the triangle. On that circle, place the measure $dA/\sqrt{1-r^2}$, as described in [Harald Hanche-Olsen's answer][3] to a different question.

I am reposting notzeb's solution to the 3 front case here, and making some comments on it. In particular, I will point out that the solution is not unique; while notzeb used fractal methods, I will give a piecewise smooth solution using the same ideas.

Idea of solution:

I claim that it is enough to find any probability distribution on $\{(p,q,r): p+q+r=1, \ p,q,r \geq 0 \}$ whose projection to each coordinate is the uniform measure on $[0,2/3]$.

Proof that such a measure works:

(For simplicity, I disregard ties.) Observe that it is impossible for either general to win on all fronts. Therefore, if I find a strategy that guarantees that I am expected to win at least 1.5 fronts against any opposing strategy, this means that I have probability at least 1/2 of winning 2 fronts against any opposing strategy. (This logic does not extend to the 5 front case.)

Suppose my enemy sends $p$ troops to the first front. I beat him with probability $\max(1-(3/2)p, 0)$. By linearity of expectation, if my enemy sends troops $(p,q,r)$, my expected number of victories is $$\max(1-(3/2)p, 0)+\max(1-(3/2)q, 0)+\max(1-(3/2)r, 0)$$ $$\geq 3-(3/2)(p+q+r) = 3/2.$$ If my opponent adopts a mixed strategy, linearity shows that I still have expected number of victories at least $3/2$. QED

notzeb's measure:

Take the triangle of possible solutions and inscribe a hexagon in it, with vertices at the permutations of $(0,1/3,2/3)$. All our solutions will be inside that hexagon.

Now, take that hexagon and place 6 smaller hexagons in it as shown below.

6 Hexagons in 1 http://www-math.mit.edu/%7Espeyer/3front.png

Choose one of those 6 hexagons uniformly at random. Place 6 smaller hexagons inside that one, and choose one of these uniformly at random again. Keep going. The hexagons shrink in size each time; the limiting point is your army distribution.

Notice that the space of possible solutions is a Sierpinski-gasket-like figure, of Hausdorff dimension $\log 6/\log 3$. It is cute to observe that the white star of David in the center becomes a Koch snowflake of excluded points in the final solution.

My alternate measure

Inscribe a circle in the triangle. On that circle, place the measure $dA/\sqrt{1-r^2}$, as described in [Harald Hanche-Olsen's answer][3] to a different question.
added 127 characters in body
Source Link
David E Speyer
  • 156.3k
  • 14
  • 421
  • 763

I am reposting notzeb's solution to the 3 front case here, as I expect the 5 front case to be at least as badand making some comments on it. In particular, noticeI will point out that the winning solution is given by a measure withnot unique; while notzeb used fractal supportmethods, I will give a piecewise smooth solution using the same ideas.

Idea of solution:

I claim that it is enough to find any probability distribution on $\{(p,q,r): p+q+r=1, \ p,q,r \geq 0 \}$ whose projection to each coordinate is the uniform measure on $[0,2/3]$.

Proof that such a measure works:

Solution (rephrased): Take the triangle of possible solutions and inscribe a hexagon in(For simplicity, I disregard ties.) Observe that it is impossible for either general to win on all fronts. Therefore, with verticesif I find a strategy that guarantees that I am expected to win at the permutationsleast 1.5 fronts against any opposing strategy, this means that I have probability at least 1/2 of winning 2 fronts against any opposing strategy. $(0,1/3,2/3)$(This logic does not extend to the 5 front case. All our solutions will be inside)

Suppose my enemy sends $p$ troops to the first front. I beat him with probability $\max(1-(3/2)p, 0)$. By linearity of expectation, if my enemy sends troops $(p,q,r)$, my expected number of victories is $$\max(1-(3/2)p, 0)+\max(1-(3/2)q, 0)+\max(1-(3/2)r, 0)$$ $$\geq 3-(3/2)(p+q+r) = 3/2.$$ If my opponent adopts a mixed strategy, linearity shows that hexagonI still have expected number of victories at least $3/2$. QED

notzeb's measure:

Take the triangle of possible solutions and inscribe a hexagon in it, with vertices at the permutations of $(0,1/3,2/3)$. All our solutions will be inside that hexagon.

Now, take that hexagon and place 6 smaller hexagons in it as shown below.

6 Hexagons in 1 http://www-math.mit.edu/%7Espeyer/3front.png

Choose one of those 6 hexagons uniformly at random. Place 6 smaller hexagons inside that one, and choose one of these uniformly at random again. Keep going. The hexagons shrink in size each time; the limiting point is your army distribution.

Notice that the space of possible solutions is a Sierpinski-gasket-like figure, of Hausdorff dimension $\log 6/\log 3$. It is cute to observe that the white star of David in the center becomes a Koch snowflake of excluded points in the final solution.

Proof that this works: (I disregard ties, as they occur with probability zero.) Observe that it is impossible for either general to win on all fronts. Therefore, if I find a strategy that guarantees that I am expected to win at least 1.5 fronts against any opposing strategy, this means that I have probability at least 1/2 of winning 2 fronts against any opposing strategy. (This logic does not extend to the 5 front case.)

Lemma: For any of the three fronts, the probability distribution of troops that I send there is uniform on the interval $[0,2/3]$. Proof: After I have chosen a hexagon at the coarsest level, I am equally likely to be in $[0,2/9]$, $[2/9,4/9]$ and $[4/9,6/9]$. After I choose the next coarsest hexagon, I am equally likely to be in any one of the three thirds of the interval I chose at the previous step. And so forth. End of lemma.

Suppose my enemy sends $p$ troops to the first front. I beat him with probability $\max(1-(3/2)p, 0)$. By linearity of expectation, if my enemy sends troops $(p,q,r)$, my expected number of victories is $$\max(1-(3/2)p, 0)+\max(1-(3/2)q, 0)+\max(1-(3/2)r, 0) \geq 3-(3/2)(p+q+r) = 3/2.$$ If my opponent adopts a mixed strategy, I still have expected number of victories at least $3/2$. QED

My alternate measure

Inscribe a circle in the triangle. On that circle, place the measure $dA/\sqrt{1-r^2}$, as described in [Harald Hanche-Olsen's answer][3] to a different question.

I am reposting notzeb's solution to the 3 front case here, as I expect the 5 front case to be at least as bad. In particular, notice that the winning solution is given by a measure with fractal support.

Solution (rephrased): Take the triangle of possible solutions and inscribe a hexagon in it, with vertices at the permutations of $(0,1/3,2/3)$. All our solutions will be inside that hexagon.

Now, take that hexagon and place 6 smaller hexagons in it as shown below.

6 Hexagons in 1 http://www-math.mit.edu/%7Espeyer/3front.png

Choose one of those 6 hexagons uniformly at random. Place 6 smaller hexagons inside that one, and choose one of these uniformly at random again. Keep going. The hexagons shrink in size each time; the limiting point is your army distribution.

Notice that the space of possible solutions is a Sierpinski-gasket-like figure, of Hausdorff dimension $\log 6/\log 3$. It is cute to observe that the white star of David in the center becomes a Koch snowflake of excluded points in the final solution.

Proof that this works: (I disregard ties, as they occur with probability zero.) Observe that it is impossible for either general to win on all fronts. Therefore, if I find a strategy that guarantees that I am expected to win at least 1.5 fronts against any opposing strategy, this means that I have probability at least 1/2 of winning 2 fronts against any opposing strategy. (This logic does not extend to the 5 front case.)

Lemma: For any of the three fronts, the probability distribution of troops that I send there is uniform on the interval $[0,2/3]$. Proof: After I have chosen a hexagon at the coarsest level, I am equally likely to be in $[0,2/9]$, $[2/9,4/9]$ and $[4/9,6/9]$. After I choose the next coarsest hexagon, I am equally likely to be in any one of the three thirds of the interval I chose at the previous step. And so forth. End of lemma.

Suppose my enemy sends $p$ troops to the first front. I beat him with probability $\max(1-(3/2)p, 0)$. By linearity of expectation, if my enemy sends troops $(p,q,r)$, my expected number of victories is $$\max(1-(3/2)p, 0)+\max(1-(3/2)q, 0)+\max(1-(3/2)r, 0) \geq 3-(3/2)(p+q+r) = 3/2.$$ If my opponent adopts a mixed strategy, I still have expected number of victories at least $3/2$. QED

I am reposting notzeb's solution to the 3 front case here, and making some comments on it. In particular, I will point out that the solution is not unique; while notzeb used fractal methods, I will give a piecewise smooth solution using the same ideas.

Idea of solution:

I claim that it is enough to find any probability distribution on $\{(p,q,r): p+q+r=1, \ p,q,r \geq 0 \}$ whose projection to each coordinate is the uniform measure on $[0,2/3]$.

Proof that such a measure works:

(For simplicity, I disregard ties.) Observe that it is impossible for either general to win on all fronts. Therefore, if I find a strategy that guarantees that I am expected to win at least 1.5 fronts against any opposing strategy, this means that I have probability at least 1/2 of winning 2 fronts against any opposing strategy. (This logic does not extend to the 5 front case.)

Suppose my enemy sends $p$ troops to the first front. I beat him with probability $\max(1-(3/2)p, 0)$. By linearity of expectation, if my enemy sends troops $(p,q,r)$, my expected number of victories is $$\max(1-(3/2)p, 0)+\max(1-(3/2)q, 0)+\max(1-(3/2)r, 0)$$ $$\geq 3-(3/2)(p+q+r) = 3/2.$$ If my opponent adopts a mixed strategy, linearity shows that I still have expected number of victories at least $3/2$. QED

notzeb's measure:

Take the triangle of possible solutions and inscribe a hexagon in it, with vertices at the permutations of $(0,1/3,2/3)$. All our solutions will be inside that hexagon.

Now, take that hexagon and place 6 smaller hexagons in it as shown below.

6 Hexagons in 1 http://www-math.mit.edu/%7Espeyer/3front.png

Choose one of those 6 hexagons uniformly at random. Place 6 smaller hexagons inside that one, and choose one of these uniformly at random again. Keep going. The hexagons shrink in size each time; the limiting point is your army distribution.

Notice that the space of possible solutions is a Sierpinski-gasket-like figure, of Hausdorff dimension $\log 6/\log 3$. It is cute to observe that the white star of David in the center becomes a Koch snowflake of excluded points in the final solution.

My alternate measure

Inscribe a circle in the triangle. On that circle, place the measure $dA/\sqrt{1-r^2}$, as described in [Harald Hanche-Olsen's answer][3] to a different question.
Source Link
David E Speyer
  • 156.3k
  • 14
  • 421
  • 763

I am reposting notzeb's solution to the 3 front case here, as I expect the 5 front case to be at least as bad. In particular, notice that the winning solution is given by a measure with fractal support.

Solution (rephrased): Take the triangle of possible solutions and inscribe a hexagon in it, with vertices at the permutations of $(0,1/3,2/3)$. All our solutions will be inside that hexagon.

Now, take that hexagon and place 6 smaller hexagons in it as shown below.

6 Hexagons in 1 http://www-math.mit.edu/%7Espeyer/3front.png

Choose one of those 6 hexagons uniformly at random. Place 6 smaller hexagons inside that one, and choose one of these uniformly at random again. Keep going. The hexagons shrink in size each time; the limiting point is your army distribution.

Notice that the space of possible solutions is a Sierpinski-gasket-like figure, of Hausdorff dimension $\log 6/\log 3$. It is cute to observe that the white star of David in the center becomes a Koch snowflake of excluded points in the final solution.

Proof that this works: (I disregard ties, as they occur with probability zero.) Observe that it is impossible for either general to win on all fronts. Therefore, if I find a strategy that guarantees that I am expected to win at least 1.5 fronts against any opposing strategy, this means that I have probability at least 1/2 of winning 2 fronts against any opposing strategy. (This logic does not extend to the 5 front case.)

Lemma: For any of the three fronts, the probability distribution of troops that I send there is uniform on the interval $[0,2/3]$. Proof: After I have chosen a hexagon at the coarsest level, I am equally likely to be in $[0,2/9]$, $[2/9,4/9]$ and $[4/9,6/9]$. After I choose the next coarsest hexagon, I am equally likely to be in any one of the three thirds of the interval I chose at the previous step. And so forth. End of lemma.

Suppose my enemy sends $p$ troops to the first front. I beat him with probability $\max(1-(3/2)p, 0)$. By linearity of expectation, if my enemy sends troops $(p,q,r)$, my expected number of victories is $$\max(1-(3/2)p, 0)+\max(1-(3/2)q, 0)+\max(1-(3/2)r, 0) \geq 3-(3/2)(p+q+r) = 3/2.$$ If my opponent adopts a mixed strategy, I still have expected number of victories at least $3/2$. QED