Two teams, $ A$ and $ B$, fight for a territory limited by a circumference. $ A$ has $ n$ blue flags and $ B$ has $ n$ white flags ($ n\geq 2$, fixed). They play alternatively and $ A$ begins the game. Each team, in its turn, places one of his flags in a point of the circumference that has not been used in a previous play. Each flag, once placed, cannot be moved. Once all $ 2n$ flags have been placed, territory is divided between the two teams. A point of the territory belongs to $ A$ if the closest flag to it is blue, and it belongs to $ B$ if the closest flag to it is white. If the closest blue flag to a point is at the same distance than the closest white flag to that point, the point is neutral (not from $ A$ nor from $ B$). A team wins the game is their points cover a greater area that that covered by the points of the other team. There is a draw if both cover equal areas. Prove that, for every $ n$, team $ B$ has a winning strategy.
Problem
Source:
Tags: geometry, algorithm, induction, combinatorics proposed, combinatorics
13.09.2007 21:28
Let $ A_{1}, ... , A_{2n}$ the $ 2n$ points around the circunference. Color the A-points with $ A$ and the B-points with $ B$. Let O the center of circunference and $ B_{1}, ... , B_{2}n$ the midpoints of the arcs $ A_{1}A_{2}, ... , A_{2n}A_{1}$, respectively. See that if a point $ X$ is in the sector $ A_{i}OB_{i+i}$, this point will belong to the territory with same color of $ A_{i}$ (and if this point is in the sector $ B_{i}OA_{i+1}$, this point will belong to the territory with same color of $ A_{i+1}$). The problem can be solved using induction. To n = 2, is easy. Suppose that for $ n\leq k$, team B has a winning strategy. To prove that for $ n = k+1$ the proposition is valid, follow the same strategy to win of $ n = k$. When the team A put your last flag, we have three cases: 1)Team A put the last flag between two A-flags: Trivial case. A-territory remais the same, and the same for B-territory. So, B-team should only put your (k+1)-flag in any place. 2) Team A put the last flag between two B-flags ($ A_{i}$ and $ A_{i+1}$, wlog): Let $ S_{a}$ the area of the total territory of $ A$ after the k-flag of $ B$ be used, and $ S_{b}$ the area of B-territory. Let $ [XOY]$ the area of a sector $ XOY$. Let M the point with the (k+1)-A-flag, and N the point with the (k+1)-B-flag. We'll have that the area of A, after your (k+1)-flag used, will be $ S_{a}+\frac{[A_{i}OM]}{2}+\frac{[MOA_{i+1}]}{2}$. Suppose that, wlog, ${ [A_{i}OM}]\geq [MOA_{i+1}]$. Now, to win, B-team should put your flag in a point N, sufficiently closed to M and between A_i and M, because your new area will be $ S_{b}-(\frac{[A_{i}OM]+[MOA_{i+1}]}{2})+([A_{i}OM]-[NOM])$ $ = S_{b}+\frac{([A_{i}OM]-[MOA_{i+1}])}{2}-[NOM]$. $ [NOM]$ can be too little than we want, and the new area of A-territory will be $ S_{a}-\frac{([A_{i}OM]-[MOA_{i+1}])}{2}+[NOM]$. 3) Team A put your last flag between one A-flag and one B-flag ($ A_{i}$ and $ A_{i+1}$, respectively, wlog): We'll use the same notations of case 2. The new area of A will be $ S_{a}+\frac{[A_{i}OM]}{2}$ (it can be easily checked, look a picture). To win, B-team should only put you (k+1)-flag in any place between $ A_{i}$ and $ M$, because the new areas of A and B will be $ S_{a}$ and $ S_{b}$, respectevely!
14.09.2007 11:39
i think your solution isn't working. after the last moves $ S_{a}$ will be more then $ S_{a}+[A_{i+1}OM]\cdot1/2$ $ S_{b}$ will be less then $ S_{b}$ and also $ S_{a}+[A_{i+1}OM]\cdot1/2$ can be more then $ S_{b}$
15.09.2007 21:39
Let $ X_{1}$ be the first point where $ A$ puts his flag. Starting from this point divide the circle with an angle of $ 360/n$ and fix these points $ X_{2},X_{3},...,X_{n}$. It is obvious that having an $ A$ flag near a $ B$ the territory between them is the same for both. The only territories that count are obtained from $ 2$ nearby identical flags. The winning strategy for $ B$ is to put his flags in the fixed points $ X_{i}$ until there are no more free of them; if $ A$ puts a flag in a fixed point $ B$ continues putting his flag in the next free fixed point. The simplest configuration we can have is that $ B$ occupies all the fixed points and $ A$ tries to neutralize the $ B$ territories by putting an $ A$ flag between $ 2$ nearby $ B$ flags; until now the game is a draw but there are $ n$ angles(areas) and $ A$ disposes of $ n-1$ flags (the first one is fixed) so after the "neutralization" $ A$ has only one flag and $ 2$ angles are free(the first one and the last), putting an $ A$ flag near another one identical to it, $ B$ can put his last flag in one of the $ 2$ free angles, closer to the $ X_{1}$ s.t. the new territory of $ B$ is bigger then $ A$`s $ \Rightarrow$ $ B$ wins. Starting again with this configuration, if $ A$ tries to obtain a territory between $ 2$ nearby $ B$ flags, a $ B$ territory with the maximum angle will be not neutralized and again at the end $ B$ wins. Now, if $ A$ changes this configuration by putting a flag in the place of a $ B$ fixed point, obtaining so an $ A$ territory, $ B$ will have one more free flag at the end and he can neutralize this $ A$ territory with it.This is valid also in the situation that $ 2$ nearby $ A$ flags are on fixed points; every time when $ A$ tries to obtain a territory, either gives $ B$ one more free flag ,so a chance to neutralize it, or makes free a $ B$ territory with the maximum angle,so bigger then the $ A$ territory. So, $ B$ has a wining strategy . If smth is not clear or we have some slips, we wait for questions or remarks .
19.09.2007 06:04
$ MihAliza$, please, explain me, your strategy is put B´s flags in the free fix points "in order" am i right? so, for n=7, if A put A's flags in the fix points $ X_{1}, X_{7}, X_{6}$ and B(in your strategy) put B's flags in $ X_{2},X_{3}$ and $ X_{4}$, then if A put a flag in X5, he is temporally the winner; but when B play, he can put a B flag between and A and B flags or between two As flags, so in the A turn, he is winning yet or the game is in draw, then A can neutralize 2 consecutive Bs and he is winning again, this procces can be repeated. how do you solve this case?
19.09.2007 15:18
The algorithm is the same. When all the fixed points are occupied, B begins to neutralize A's territories.There are the steps, after $ X1$,$ X7$,$ X6$,$ X5$ are occupied by A and $ X2$,$ X3$,$ X4$ by B.It's B's turn: $ B$ $ \Rightarrow $ between $ X1$ and $ X7$ $ A$ $ \Rightarrow $ between $ X2$ and $ X3$ $ B$ $ \Rightarrow $ between $ X7$ and $ X6$ $ A$ $ \Rightarrow $ between $ X3$ and $ X4$ $ B$ $ \Rightarrow $ between $ X6$ and $ X5$ And, just how you said, the game until now is a draw.But there is 1 remaining flag for A, and 1 for B, and there are no more teritories to neutralize.But we have 2 free ter. with maximum area: those between $ X1$ and $ X2$, and between $ X4$ and $ X5$, so wherever puts A to save a territory for him (the smartest is to put in one of these, near B's flag), B can put nearer to A's flag in the other. And he wins. (It's important, that at the end, before the last move of A and B, there are always at least 2 free territories with maximum area, each of an angle, because they put until that moment 2*(n-1) flags, and there are n fix points, and n places between them, the fix points are surely occupied. So there are at least 2 free places,and even if the game until now is a draw,which is the worst case for B, he can save a larger territory then A, with his last step)
19.09.2007 21:57
Sorry, i can't see where is the mistake in my solution! Are you speaking about the case 3) ? If yes, you saw how i told to put the last B-flag? I can be wrong, but i still thinking that my solution work..
20.09.2007 10:41
Your solution is wrong. Let $ n=3$: A puts the first flag,B puts symmetrical from the center his flag,A puts near the B-flag and B puts closer to A so that $ S_{b}>S_{a}$; until now we constructed a winning strategy for $ n=2$. Now if A puts his last flag between the B-flags(in the middle), B has no solution to win. So, the induction does not work in this case.