, 2023

We claim that the princesses can guarantee saving $k$ princes and no more. To see that they can save $k$ princes, have each princess kiss the first $k$ frogs - clearly each of the first $k$ frogs will be saved.

Now we will show by induction on $k$ that the princesses cannot guarantee saving more than $k$ princes. The base case $k = 0$ is trivial. Suppose that for some $k$ there exists a strategy for the princesses to save at least $k + 1$ princes. Consider the first point during this strategy when a princess makes a kiss that is guaranteed to be correct - if no such point exists then there is some matching for which the princesses cannot assure saving any princes, so we may assume such a point exists. Denote the princess and frog involved in this kiss by $p_0$ and $f_0$ respectively.

Construct a bipartite graph $G$ on two sets of $n$ vertices, one set $P$ corresponding to the princesses and the other set $F$ corresponding to the frogs. For any $p \in P$ and $f \in F$ add edge $pf$ if $p$ has not kissed $f$ before $p_0$ kisses $f_0$. Then, since up to this point no kiss has been guaranteed to be correct, there exists a perfect matching on this graph. However if we remove edge $p_0f_0$ to form a graph $H$ then there can no longer be a perfect matching as we assumed $p_0$ must be correct in kissing $f_0$. Thus, by Hall's marriage theorem there exists a subset $F'$ of $F$ such that if $P'_H$ is the set of vertices connected to a vertex in $F'$ by an edge in $H$ then $|P'_H| < |F'|$. However if $P'_G$ is the set of vertices connected to a vertex in $F'$ by an edge in $G$ then $|P'_G| \geq |F'|$, again by Hall's marriage theorem. Since $|P'_H| \geq |P'_G| - 1$, this implies that $|P'_G| = |F'|$. From now we denote $P' \equiv P'_G$.

Now we allow the princesses to save all the frogs in $F'$ for free - this can only help the princesses. If $|F'| = m$ this means that $m$ princesses (precisely those in $P'$) and $m$ frogs (those in $F'$) can be discounted and assumed saved. Consider any princess $p \in P \setminus P'$. As $p$ is not in $P'$, no edge from $p$ to $F'$ was in $G$, i.e. $p$ has already kissed all frogs in $F'$. Thus we have $n-m$ princesses and $n-m$ frogs remaining, and each princess has already spent $m$ kisses on frogs in $F'$ that now provide no useful information. Thus the rest of the princesses' strategy from this position is equivalent to a strategy to save at least $k+1-m$ princes given $n-m$ frogs and $k-m$ guesses. However by induction, no such strategy exists. This contradiction shows that the princesses can save at most $k$ princes.