In Hidro planet were living $2008^2$ hydras some time ago. One of them had 1 tentacle, other 2 and so on to the last with $2008^2$ tentacles. Let $t(H)$ be the number of tentacles of hydra $H$. The pairing of $H_1$ and $H_2$ (where $t(H_1) < t(H_2)$) is a new hydra with $t(H_2)-t(H_1)+8$ tentacles, in case of $t(H_1)=t(H_2)$ they die. An expedition found in Hidro the last hydra with 23 tentacles. That could be true ?
Problem
Source: Cuba, Concurso Nacional 2009
Tags: combinatorics proposed, combinatorics
JBL
05.02.2014 20:32
Well, this is an awful lot of words, almost all of which are irrelevant to the solution: all we need to know is that pairing $H_1$ and $H_2$ preserves the parity of the number of tentacles, that $1 + 2 + \ldots + 2008^2$ is even, and that 23 is odd.
mathworld
25.05.2014 18:47
JBL, can you explain with more details please?
JBL
11.08.2014 00:31
Stripped of the nonsense, the problem says that we have an operation on multisets: we choose two elements $x$ and $y$, delete them both, and if $x\neq y$ then you add a new element equal to $|x-y|+8$. We start with some large multiset, and the question asks whether we can apply this operation some number of times to get the multiset $\{23\}$. The answer is "no" because the sum of the elements in the initial multiset is even, the sum of the elements in the desired target is odd, but applying the operation does not change the parity of the sum of the elements.