In Tigre there are $2024$ islands, some of them connected by a two-way bridge. It is known that it is possible to go from any island to any other island using only the bridges (possibly several of them). In $k$ of the islands there is a flag ($0 \le k \le 2024$). Ana wants to destroy some of the bridges in such a way that after doing so, the following two conditions are met: $\bullet$ If an island has a flag, it is connected to an odd number of islands. $\bullet$ If an island does not have a flag, it is connected to an even number of islands. Determine all values of $k$ for which Ana can always achieve her objective, no matter what the initial bridge configuration is and which islands have a flag.
Problem
Source: Rioplatense Math Olympiad Level 3, P2 2024
Tags: graph theory, combinatorics, combinatorial optimization, rioplatense
mijail
05.12.2024 21:39
Solved with @Enigma714
Let $G$ be a connected graph with $2024$ vertices, there are $k$ red-colured vertices. Ana wants to delete edges such that at the end we have a graph $G'$ with odd vertices being exactly the $k$ red vertices.
First, let's see $k$ is even. Indeed, by handshaking lemma, the sum of the degrees of $G'$ is even, and we have exactly $k$ odd vertices. Now, let's see is true for any $0\leq k\leq 2024$ even. As Ana can delete edges, it's enough to asume that $G$ is a tree. We will prove the following lemma: Lemma: For any tree $G$ with $n\geq 1$ vertices and $0\leq k\leq n$ even, for any red-colouring of $k$ vertices, Ana can delete to get what she wants.
Obvious for $n=1$. For the sake of induction, assume true for $n-1$.
Let $v$ be a leaf and $u$ the vertex connected to $v$. So, if Ana deletes $uv$, the graph is still a tree.
$\bullet$ If $v$ is not red, then Ana can delete $uv$ and in new graph $G-v$ apply induction.
$\bullet$ If $v$ is red and $u$ is red, then Ana doesn't delete $uv$, and in $G-v$ unpaint $u$ and apply induction.
$\bullet$ If $v$ is red and $u$ is not red, then Ana doesn't delete $uv$, and in $G-v$ paint $u$ and apply induction.
In $G-v$ we have a tree with $n-1$ vertices and $k$ red vertices in case 1 and 3, or $k-2$ red vertices in case 2, so can apply induction, and by parity we will get what we want.
Therefore the possible $k$ are all even in that interval.
bin_sherlo
05.12.2024 21:56
We claim that if $k$ is an even number, then Ana can achieve this. Take the graph interpretation. Let the cities containing flag be special. If Ana does not destroy an edge, then let her fix it (we will use "fixing" for this). If there are odd special cities, then after the operation Ana made, odd number of cities have odd edges and odd number of cities have even edges which is impossible since total degree must be even. Now let's show that if there are $n$ cities and $2m\leq n$ special cities, then Ana can destroy some edges so that the conditions will be held. Let's induct on $n$. It's true for $2m=n$. Suppose that it's true for $n\geq 2m$. First, Ana considers a spanning tree and destroys the edges not in that spanning tree. If a leaf is not special, then Ana destroys that leaf's connection, too. After these operations, Ana has a spanning tree where each leaf is special. If a two leaves meet at a point, then Ana fixes those two leaves' edges and throws the leaves (for connection of leaves, an even number of change has occured so throwing those leaves does not effect rest of the graph). By this operations, we can assume that any two leaves have no common vertex. Pick a leaf $v$. Let $u$ be the only neighbour of $v$. If $u$ is nonspecial, then we fix the edge between $u$ and $v$ and throw $v$, make $u$ special. Rest of the graph have an even number of specials hence by our induction assumption, Ana can achieve her goal. If both $u,v$ are specials, then fix the edge between $u$ and $v$ and throw $v$, make $u$ nonspecial. Again by our induction assumption Ana achieves her goal as desired.$\blacksquare$