An island nation has $n$ islands. In the beginning every two islands are connected by a bridge. Papa Smurf starts out on island $A$ and wants to visit all other islands however Gargamel is trying to stop him. Whenever papa Smurf comes to an island, Gargamel destroys $k$ bridges coming out of that island. (if the remaining bridges are less than $k$ then he destroys all remaining bridges)
Depending on $n$ and $k$ how many islands can papa Smurf visit at most (without repeating any) regardless of Gargamel’s actions?
My attempt at a solution is as follows:
In the beginning the island nation is the graph $K_n$ and the starting island $A$ can be any vertex. Since the degree of all vertices is $n-1$ it follows that if $k\ge n-1$ then after papa Smurf visits his first island Gargamel will destroy all outgoing bridges meaning he won’t be able to go anywhere. Now if $k < n-1$, papa Smurf can always construct a Hamilton path since the island nation is a complete graph. Then we consider the best case scenario in which Gargamel breaks only the bridges papa Smurf doesn’t need (there will always be 1 bridge left at least and WOLOG we can consider that bridge to be the one we need). Under these conditions papa Smurf can visit all $n$ islands. So finally we can say: If $k\ge n-1$ then papa Smurf can visit only $2$ islands including $A$. If $k<n-1$ then papa Smurf can visit all $n$ islands.
I’m not sure my argument for $k<n-1$ is correct. I’d like help with that part.
Best Answer
If $k < n-1$, then Papa Smurf can always reach at least $n-k$ islands, and Gargamel can always prevent Papa Smurf from reaching $n-k+1$ islands.
For Papa Smurf's strategy, he can simply choose at each step to go to an island he hasn't been to yet, if possible.
Suppose Papa has so far visited $m-1$ different islands $I_1, I_2, \ldots, I_{m-1}$ in order without repeats, and now arrives at an unvisited island $I_m$. Of the $n-1$ bridges originally connected to island $I_m$, Gargamel could only have destroyed the bridges connected to previously visited islands, so there are still bridges from $I_m$ to each of the $n-m$ unvisited islands. Now Gargamel may destroy $k$ bridges connected to $I_m$, but if $k<n-m$, there is still at least one bridge to some unvisited island, so Papa may continue. So this simple strategy works at least until $m=n-k$; that is, Papa will be able to visit at least $n-k$ different islands.
For Gargamel's strategy, after Papa Smurf's first move from $I_1$ to $I_2$, Gargamel will choose a set $S$ of any $k$ islands which does not include $I_1$ or $I_2$. At every chance, Gargamel will destroy all $k$ of the bridges from Papa's current island to each island in $S$. Or if Papa had already visited his current island and it's not $I_1$, then those bridges are already destroyed and Gargamel can choose any other bridges from the island.
With this strategy, Papa can never reach any of the $k$ islands in $S$, so he cannot reach more than $n-k$ islands.