2
$\begingroup$

CONTEXT

Currently I am reading a series of book by Martin Gardner, the one I am working on is "The colossal book of Mathematics". Knowing that this man is hail as the greatest Math-Magician of the 20th Century, I am still surprised by his rather magical tricks.

The following problem is inspired by a Martin Gardner's problem I have read last February.

PROBLEM

Two new-weds are traveling to a group of island that has $2019$ islands in total. Some of the islands are connected by boats, some are not. Any island is linked to at least one other island. The couple plays a game. The husband picks an island they will start and the couple will travel there by airplane. From then on, they will take turns to choose the next island they can travel to using boats and which they have not visited before. Who cannot move anymore loses the game.

Prove that: No matter how the wife moves, as well as how the islands are connected, the husband always has a winning strategy.

EDITS

This problem is just inspired by math tricks, but it is a serious problem. The answer to this may contain graph theory.

$\endgroup$
  • $\begingroup$ There are a total of $2019$ nodes. All conncected components can not have even number of nodes, so atleast 1 must have an odd number of nodes. As a result if the husband chooses that island which is a part of a connected component with odd number of nodes, the wife will lose $\endgroup$ – h-squared Mar 10 at 16:54
  • $\begingroup$ @h-squared Not necessarily. For example, if the husband chooses node 2 of three connected as $1 - 2 - 3$, the husband loses. $\endgroup$ – Robert Israel Mar 10 at 17:26
  • $\begingroup$ @RobertIsrael The husband must take node 1 then, the Qs asks for a winning strategy, the strategy is to go for an odd conncected component $\endgroup$ – h-squared Mar 10 at 17:45
  • $\begingroup$ @h-squared Yes, in this case. But for a more complicated connected graph of odd cardinality, what does the husband do? $\endgroup$ – Robert Israel Mar 10 at 18:41
2
$\begingroup$

@h-sqared and @Robert Israel, you might concern.

So this is my solution to this problem. Please check it out and any comment is appreciated.

Define a set as good if the islands in that set can be divided into pairs, and two island in each pair is connected.

Let $T_M$ be a good set that consists of the most islands. Because we have 2019 islands, which is, obviously, an odd number, so there is at least one island $x$ that does not belong to $T_M$.

Assume that $x$ is linked to another $y \notin T_M$, then we add both $x$ and $y$ to $T_M$, which is a contradition because $T_M$ has already has maximum number of islands.

So $x$ must be only conneted to islands in $T_M$. Now we number the number the islands in $T_M$ in pairs $(a_m,b_m)$ Let the husband start at $x$

Let $x$ conneted with $a_1$. Now the path will be: $x \rightarrow a_1 \rightarrow b_1 \rightarrow a_2 \rightarrow b_2 \rightarrow ... a_k\rightarrow b_k$

If at this point the wife decides to "jump out" of $T_M$, literally move to an island $z$ outside $T_M$ then we swap the pairs from its initial matching to $(x,a_1),(b_1,a_2),...(b_k,z)$. Thus, we now have $T_M$ plus 2 islands that are $x$ and $z$, which is a contradiction.

So the wife cannot jump out of $T_M$. And because the pairs in $T_M$ are matched, no matter how the wife moves, the husband always has another island to go to.

Thus, he wins. Q.E.D

| cite | improve this answer | |
$\endgroup$
-1
$\begingroup$

Since

$2019\equiv 1$ (mod $2$)

There are a total of $2019$ nodes and atleast $1$ connected component must have odd nodes. Hence the husband must pick that island which is in an odd connected component.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is not sufficient to win. It is possible for the husband to lose on an odd connected graph. $\endgroup$ – Robert Israel Mar 10 at 18:45
  • $\begingroup$ @h-squared I think you have considered this too simple. If it has odd nodes then what if it has multiple branches and one branch has even nodes? Thank you! $\endgroup$ – Nikola Tolzsek Mar 11 at 3:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.