Bump ...

Wow amazing problem! Could I have the source please?

@ below: First off, forgive my ignorance but I am a newbie to math contests. I tried googling the exact title and slight variations of it but to no avail. What does TT (in the title) stand for?

Iyerie wrote: Wow amazing problem! Could I have the source please?

Look at the title from the source.

Iyerie wrote: Wow amazing problem! Could I have the source please?

@ below: First off, forgive my ignorance but I am a newbie to math contests. I tried googling the exact title and slight variations of it but to no avail. What does TT (in the title) stand for? Tournament of Towns 2009 Junior A-7 https://www.artofproblemsolving.com/community/c3239_tournament_of_towns

I don't understabd your solution Sorry if I am being silly.... Iyerie wrote: We can represent the $2009$ islands with a polygon with $2009$ vertices. What do you mean by polygon ? I assume you just wanted to say vertices.... Iyerie wrote: Wow amazing problem! Could I have the source please? Let there exist $n$ sets of connected vertices. Since there exist an odd number of total vertices, there must exist an odd number of connected sets with an an odd number of vertices. What do you mean by $n$ sets of connected vertices ? You mean interconnected vertices as in a connected subgraph ? Iyerie wrote: Wow amazing problem! Could I have the source please? The way she does this is by choosing a vertex that is part of set of vertices that contains an odd number of vertices. Case 1:WLOG assume that Ben always decides to choose a vertex that is part of the set that Anna chose If you meant Anna chooses from a connected-subgraph, then Ben will have to chose from this subgraph (due to connected condition). So I guess you mean something else by connected... Would you please elaborate ?

utkarshgupta wrote: Iyerie wrote: We can represent the $2009$ islands with a polygon with $2009$ vertices. What do you mean by polygon ? I assume you just wanted to say vertices.... Yes, creating a polygon with those vertices is rather unnecessary. I did so in my initial thought process and that's just the way I wrote it out. The proof is complete without that too. utkarshgupta wrote: Iyerie wrote: Wow amazing problem! Could I have the source please? Let there exist $n$ sets of connected vertices. Since there exist an odd number of total vertices, there must exist an odd number of connected sets with an an odd number of vertices. What do you mean by $n$ sets of connected vertices ? You mean interconnected vertices as in a connected subgraph ? By $n$ sets of connected vertices I basically meant that there would be those many distinct sets. I intended to use $n$ later on again but then I realized I didn't need to so this is another thing that could be eliminated without changing the proof Yes, I do mean as in a connected subgraph. Going back to the analogy of polygons, this would happen if I formed a triangle with any $3$ of the vertices from that $2009$ sided polygon (then those $3$ vertices would be denoted as "connected") utkarshgupta wrote: Iyerie wrote: Wow amazing problem! Could I have the source please? The way she does this is by choosing a vertex that is part of set of vertices that contains an odd number of vertices. Case 1:WLOG assume that Ben always decides to choose a vertex that is part of the set that Anna chose If you meant Anna from a connected-subgraph, then Ben will have to chose from this subgraph (due to connected condition). So I guess you mean something else by connected... Would you please elaborate ? I think my definition of $"connected"$ still holds? I did mean that if Anna chooses from a particular subgraph then Ben too will choose from that same subgraph. However, I don't think that this entire approach is correct. Now that I am looking at it after some time, I don't see a plausible way to combine the cases to form $Case 3$

Not sure how this problem ended up in this forum, where it is way too hard. I got asked by someone to try it, so here's a solution.

Amir Hossein wrote: Anna and Ben decided to visit Archipelago with $2009$ islands. Some pairs of islands are connected by boats which run both ways. Anna and Ben are playing during the trip: Anna chooses the first island on which they arrive by plane. Then Ben chooses the next island which they could visit. Thereafter, the two take turns choosing an island which they have not yet visited. When they arrive at an island which is connected only to islands they had already visited, whoever's turn to choose next would be the loser. Prove that Anna could always win, regardless of the way Ben played and regardless of the way the islands were connected. (12 points for Juniors and 10 points for Seniors) Pick a maximal matching $\mathcal{M}$ of $G$, the graph of islands, with $m$ edges. Note that $\mathcal{M}$ has $2m<2009$ vertices, so some vertex $A$ is not in $\mathcal{M}$. Ana starts at $A$. Since each edge of $G$ shares a vertex with $\mathcal{M}$, Ben's move will lead to a vertex of $\mathcal{M}$. Ana then proceeds to the island to which the previous one is matched. She repeats this from here on, thus enabling her to be able to make a move as long as Ben can. Unless, if Ben moves to an unmatched vertex, in which case we have an augmenting path in the graph, contradiction! Hence she must have the last move. Remark: The whole idea can be reverse-engineered even if one doesn't know about maximal matchings. Particularly, one tries the heuristic of "keeping Ana alive in the game". The simplest way is to have a pairing of islands which eventually leads to asking for a structure with each edge of $G$ having a vertex in.

: We let $\mathcal M$ be a maximal matching in the graph. We let $\mathcal I$ denote the remaining vertices not in the matching. Since $2009$ is odd and $|\mathcal M|$ is even, there must be at least one vertex in $\mathcal I$. By the maximality of $\mathcal M$, the set $\mathcal I$ is an independent set. [asy][asy] size(7cm); dotfactor *= 2; real h = 7; pair O = (-4, 2*h/3); filldraw(box((-0.5,-0.5),(4.5,h+0.5)), invisible, blue); filldraw(circle(O, h/3), invisible, deepgreen); pen gry = grey + dotted; pair A = O+h/6*dir(90); pair B = O+h/6*dir(210); pair C = O+h/6*dir(330); draw(A--(0,h), gry); draw(B--(1,h), gry); draw(C--(2,h), gry); draw(B--(3,h), gry); draw(A--(4,h), gry); draw((0,h)--(1,h), gry); draw((0,h)--(3,0), gry); draw((2,0)--(4,h), gry); draw((2,0)--(1,0), gry); draw((0,0)--(3,h), gry); draw((3,h)--(4,0), gry); dot(A, deepgreen); dot(B, deepgreen); dot(C, deepgreen); for (int i=0; i<=4; ++i) { draw((i,0)--(i,h), blue); dot((i,0), blue); dot((i,h), blue); } label("$\mathcal M$", (2,-0.5), dir(-90), blue); label("$\mathcal I$", O+h/3*dir(-90), dir(-90), deepgreen); [/asy][/asy] Anna now uses the following strategy: she starts at a vertex $v_0$ in $\mathcal I$. Thereafter, on her turn, whenever Ben moves to some vertex in $\mathcal M$ she follows the edge of the matching we found. Claim: If Anna follows this strategy, then Ben can never move into $\mathcal I$. Proof. Assume for contradiction Ben moved into $\mathcal I$. Then there is some path \[ v_0 - v_1 - v_2 - \dots - v_{2k+1} \]which the token followed where $v_0, v_{2k-1} \in \mathcal I$, but $v_1v_2$, $v_3v_4$, \dots, $v_{2k-1} v_{2k}$ were edges in $\mathcal M$. However, we could then increase the size of the matching by taking $v_0v_1$, $v_2v_3$, $v_4v_5$, \dots, $v_{2k}v_{2k+1}$ instead of the edges $v_1v_2$, $v_3v_4$, \dots, $v_{2k-1} v_{2k}$. This is the desired contradiction. $\blacksquare$ Thus, we gave a procedure ensuring Anna always has a move. Since Anna cannot lose, and the game must terminate, it follows that Anna has a winning strategy. Remark: Of course, the proof works equally well with $2009$ replaced by any odd number. In fact, so-called ``circular optimization'' lets us deduce this meta-fact (that only the parity of $2009$ matters) a priori, by choosing $G$ to have several connected components. A way you can come up with this proof is to first note the easy case if $G$ has a matching using all but one vertex, then Anna clearly wins by following this strategy (here $|\mathcal I| = 1$ and many complications do not arise). The proof then generalizes to $|\mathcal I| > 1$. In fact, we find that Anna also wins on any graph which does not contain a perfect matching, by the same token.

Consider a matching of maximal size in $G$. Suppose it is given by $\{x_i,y_i\}$ for $1\le i\le m$. Let $u_1,u_2,\ldots,u_r$ be the remaining vertices. Note that $r$ must be odd. Note that there are no edges between the $u_i$, else we could make a larger matching. The strategy is for Anna to place the token on $u_1$. Now Ben must place the token in the matching, and whenever Ben places a token in the matching, Anna is to place the token on the corresponding vertex. We'll make sure that this move is never denied to her by ensuring that she never enters a pair $\{x_i,y_i\}$ unless Ben enters it first. Indeed, we claim that the path formed by the tokens under this strategy from Anna (and any plays from Ben) can never hit $u_i$ for $2\le i\le r$. This clearly finishes as Anna always has a move guaranteed. Suppose that it did. Then that creates a path of length $2k+1$ containing exactly $k$ matching edges. We can now just swap these $k$ out for the other $k+1$ in this path, and thereby create a larger matching. This is the desired contradiction, so we're done.

Tournament of Towns 2009 Senior A6 wrote: Anna and Ben decided to visit Archipelago with $2009$ islands. Some pairs of islands are connected by boats which run both ways. Anna and Ben are playing during the trip: Anna chooses the first island on which they arrive by plane. Then Ben chooses the next island which they could visit. Thereafter, the two take turns choosing an island which they have not yet visited. When they arrive at an island which is connected only to islands they had already visited, whoever's turn to choose next would be the loser. Prove that Anna could always win, regardless of the way Ben played and regardless of the way the islands were connected. (12 points for Juniors and 10 points for Seniors)

We prove this inductively. WLOG suppose that $G$ is connected or choose a smaller connected component. Claim: If there exists a vertex $V$ with more than $3$ components coming out of it, we can induct downwards. Proof. Let the components attached be terminal if going to that component from $V$ guarentees a win for the opponent. If all components are terminal, Anna wins by choosing $V$. Else, suppose there is an odd non-terminal. There must be some other odd component, and Anna can inductively choose that component as going to $V$ is losing. If there is an even non-terminal, this implies that this component has itself a vertex $V$. Inducting on this vertex finishes. $\blacksquare$ Anna can now attempts to pair vertices in $G$, utilizing the above when necessary to finish to get a winning vertex.

Take a maximal matching, because $G$ has an odd number of vertices there exists a vertice $v$ not in the matching, Anna can start at $v$. I claim all of bens moves must be from one pair in the matching to another. Clearly for his first move that is the case. Now suppose it was the case for his first $n$ moves and Anna always moved to the other vertice in the matching. If ben moves to a vertice not in one of the matchings we can take, the path that has been formed and get a larger matching by splitting the vertices in the path up. Thus ben always moves to a vertice in the matching so Anna can always move and thus she wins.