Finding the maximum number of catchable Pokemon such that no two are enemies with each other

Question

Cynthia loves Pokemon and she wants to catch them all. In Victory Road, there are a total of $80$ Pokemon. Cynthia wants to catch as many of them as possible. However, she cannot catch any two Pokemon that are enemies with each other. After exploring around for a while, she makes the following two observations:
1.Every Pokemon in Victory Road is enemies with exactly two other Pokemon.
2.Due to her inability to catch Pokemon that are enemies with one another, the maximum number of the Pokemon she can catch is equal to $n$.
What is the sum of all possible values of $n$?

This is a question from BdMO 2021(Bangladesh National Mathematical Olympiad), which most of the students couldn't solve (including me).

My attempt:

Let's reconsider the problem with graph theory. We draw an edge between two Pokemons if they are enemies. So, each vertex has degree $2$. If the whole graph is an $80$ cycle (or an $80$-gon), Cynthia can catch $40$ Pokemons at max, which is just one case of the problem.

There are some other cases when we change the edges of the graph, for which I am unable to find the maximum number of catchable Pokemons (I am not good at graph theory). So, how do I approach the problem?

Answer 1

You can also have any number of cycles in the graph. If there is a $3$ cycle and a $77$ cycle she can only catch $1$ of the $3$ and $38$ of the $77$ for a total of $39$. If there are $3$ cycles of $3$ and one cycle of $71$, she can catch $38$. Each time a $3$ cycle is removed from an even cycle the count goes down by $1$ until we get to $25\ 3$ cycles and a $5$ cycle where we can get $27$ so the number can be anything in the range $[27,40]$

To prove there is no graph that allows her to catch more than $40$ Pokemon, note that there are $80$ edges in the graph. At least one of the vertices attached to each edge must be among the uncaught Pokemon. As each vertex can only account for two edges, there must at least $40$ uncaught Pokemon.

To see she can always get $27$ note that when she has caught $26$ they have a maximum of $52$ enemies between them, so there are at least $2$ Pokemon left that she can catch. Those two might be enemies, so she cannot guarantee $28$.

So we sum the numbers $27$ through $40$ getting $469$.

Answer 2

As you observed, the problem is equivalent to the following:

Write $80 = a_1 + \dots + a_k$ with each integer $a_k$ at least $3$. What are the possible values of $n = \sum_{i = 1}^k \lfloor \frac {a_i}2\rfloor$?

The answer is that the possible values of $n$ are $27, 28, \dots, 40$.

Firstly, we have $n \leq \sum_{i = 1}^k \frac{a_i}2 = 40$.

Secondly, we have $n \geq \sum_{i = 1}^k \frac {a_i - 1} 2 = 40 - \frac k 2$. Since each $a_k$ is at least $3$, we have $3k \leq 80$, or $k \leq 26$. This gives $n \geq 27$.

Lastly, we show that any number from $27$ to $40$ can be a possible value of $n$. Thus we construct the following partition: $a_1 = \dots = a_{2t} = 3, a_{2t + 1} = 80 - 6t$, where $t$ can be any integer from $0$ to $12$. The resulting value of $n$ will be $1 \cdot 2t + (40 - 3t) = 40 - t$. This covers all cases from $28$ to $40$, and for $n = 27$ we use $a_1 = \dots = a_{25} = 3, a_{26} = 5$.