Blog

by Davide Lombardo

EGMO 2015, Problem 5. Let $m, n$ be positive integers with $m > 1$. Anastasia partitions the integers $1, 2, \dots , 2m$ into $m$ pairs. Boris then chooses one integer from each pair and finds the sum of these chosen integers.
Prove that Anastasia can select the pairs so that Boris cannot make his sum equal to $n.$

Well, Boris' sum lies between $1+2+\cdots+m = \frac{m(m+1)}{2}$ and $(m+1)+(m+2)+\cdots+(m+m) = m^2 + \frac{m(m+1)}{2}$; so any value of $n$ outside of this interval is fine, and we need to find a partition that prevents Boris from achieving a given $n$ only for $n$ in this interval. The first idea that comes to mind is to try and force Boris to do something we want, independently of what he may choose (as in the best conjurer's tricks). For example, the obvious partition $(1,m+1), (2,m+2), \ldots, (m,m+m)$ has the property that – no matter what Boris chooses – we know what his choice is modulo $m$: it's going to be $1,2,\ldots,m$. So with this partition poor Boris can only obtain sums that are congruent to
$$1 + \cdots + m \equiv \frac{m(m+1)}{2} \pmod{m}.$$
That's pretty good already: let's say that $m$ is odd, for the moment, so that $\frac{m(m+1)}{2}$ is zero modulo $m$. Then we're saying that if $n$ is not a multiple of $m$, we can just give him this partition and he'll be done for :). So this leaves us with only a few numbers to worry about, namely the multiples of $m$ in the interval $[\frac{m+1}{2} m,\frac{3m+1}{2}m]$. Wait though, I'm being way too generous with my friend Boris here: why should I let him choose all the big numbers and achieve a super-large sum? If he wants to take $2m$ he'll have to give up on $2m-1$, and likewise with $2m-2,2m-3$ etc... in other words, what happens if I offer him the other obvious partition, namely $\{1,2\}, \{3,4\}, ..., \{2m-1,2m\}$? His sum is going to be in the interval $[1+3+\cdots+(2m-1),2+4+\cdots+2m] = [m^2,m^2+m]$. Much better! So this partition ensures that he can never realise an $n \not \in [m^2,m^2+2m]$, and the one from before rules out all the multiples of $m$. Tough luck, eh, Boris? It's not looking good for you, brother... anyway: if $n \neq m^2, m^2+m$ we've won (assuming that $m$ is odd, that is). What do we do if $n=m^2$, say? What other invariant can I come up with? I've already used "size" and "residue class modulo $m$". Can I make sure that the sum is always odd, for example? This would require me to pair together numbers of the same parity (if for even just one pair Boris can choose between numbers of opposite parity then I have no control on the parity of the sum). Can I do it, even for small values of $m$? Say $m=4$: then I should try $\{1,3\},\{2,4\}$, so the sum is indeed always odd. But this probably depends on $m$ modulo 4, so I run into further trouble if $4 \mid m$.

Let me check: $m=4$, $\{1,5\}, \{2,6\}, \{3,7\}, \{4,8\}$. Then the sum is... well, whatever it is, this is a partition we already considered, so it cannot give me any new information (come to think about it, why did I try $m=4$ instead of $m=3$?). No, we need to find a different way.

While I'm thinking about this, let me work out which numbers in the interval $[m^2,m^2+m]$ I need to worry about when $m$ is even. It's those numbers $N$ such that $N \equiv \frac{m(m+1)}{2} \pmod{m}$, where $m=2k$. Then $N \equiv k(2k+1) \equiv k \pmod{2k}$, and the only such number in the interval $[m^2,m^2+m]$ seems to be $m^2+k = m^2+\frac{m}{2}$. So this is actually 'easier', at least in the sense that there's just a single number we need to make sure Boris cannot achieve.

This, however, does not solve the problem of how to actually stop that pesky Boris from making his sum equal to those few numbers left. To be fair, there are so few numbers I don't know how to deal with that maybe I can afford to leave Boris some choice, though I still don't want his sum to vary too wildly, at least with respect to some property (I mean: it can vary all it likes in size, so long as its residue class modulo something is fixed, for example). Maybe I can force Boris to choose between a sum that is "large", but of the wrong parity, and one that is of the correct parity, but too small to be $m^2$? This is worth a try: I should probably pair $\{1,2m\}$, and then pair the rest of the numbers so that numbers in every pair have the same parity and roughly the same size (so that, ideally, when Boris chooses between $1$ and $2m$, he either overshoots – if he picks $2m$ – or undershoots – if he picks $1$). I realize that I'm talking about over- and under-shooting and not caring about parity, but maybe parity will intervene in some mysterious way? I don't know: let's see this in action for a smallish $m$, say $m=3$. Following the recipe above, I should take $\{1,6\}; \{2,4\}; \{3,5\}$, and the numbers to avoid are $9, 9+3=12$. Let me check... this seems to work! I'm not sure whether this is just luck, though; I feel like trying another small case. Let's say $m=5$, so that the partition is $\{1,10\}, \{2,4\}, \{3,5\}, ...$. Ah. I was going to write $\{4,6\}$, but $4$ is already taken. So I need to have $\{6,8\}$... mmh, this does not sound very promising. Anyway, here is the partition:
\[
\{1,10\}, \{2,4\}, \{3,5\}, \{6,8\}, \{7,9\},
\]
and the numbers to avoid are $25$ and $25+5=30$. Darn, I can see that tiresome Boris gloating already... $10+2+3+8+7=30$. Nope, this doesn't work.

Going back to the idea of 'almost-forcing-Boris-to-do-something-but-not-quite', combined with 'there should be a single pair for which Boris' choice matters, and even then neither of the two choices should work (muahahaha evil laugh)', I'm eventually lead – after a significant amount of doodling, writing down partitions, noticing that they do not work, and cursing – to considering the following alternative. Let's try to fix the congruence class of the sum modulo some $M$ which is not quite $m$, but it's close enough that we can arrange most pairs to have elements that are congruent modulo $M$. In other words: let's try to force the sum to take some value modulo $M$; we'll fail, but maybe we can fail not tooo badly, so that the sum can only take very few values modulo $M$.

Natural choices are $M=m+1$ and $M=m-1$; let's try the former. The partition would then be
\begin{equation}
\begin{array}{cccccc}
1 & 2 & 3 & \cdots & m-1 & m \\
m+2 & m+3 & m+4 & \cdots & 2m & m+1;
\end{array}\tag{$\star$}\label{eq:FinalPartition}
\end{equation}
can we finally trick Boris into making the wrong choice? Whatever he decides to do, he will end up with a sum which is either $1+2+\cdots+(m-1)+m$ or $1+2+\cdots+(m-1)+(m+1)$ modulo $m+1$. So, writing $S$ for Boris' sum, $S \equiv \frac{m(m-1)}{2} + \begin{cases} -1 \\ 0\end{cases} \pmod{m+1}$.
Now the numbers we want to avoid are (let me take $m$ odd again...) $m^2+m \equiv (-1)^2-1 \equiv 0 \pmod{m+1}$ and $m^2 \equiv 1 \pmod{m+1}$, while (using that $m=2k+1$ is odd)
\[
S \equiv \frac{(2k+1)(2k)}{2} + \begin{cases} -1 \\ 0\end{cases} \equiv k(-1) + \begin{cases} -1 \\ 0\end{cases} \pmod{2k+2}.
\]
Oooh this looks very promising: it means we're done, provided that
\[
- k + \begin{cases} -1 \\ 0\end{cases} \not \equiv \begin{cases} 0 \\ 1\end{cases} \pmod{2k+2},
\]
that is, we have problems only if $k \equiv 0,-1,-2 \pmod{2k+2}$. But plainly this cannot happen, because a positive integer that is congruent to $0,-1,-2$ modulo $2k+2$ is at least equal to $2k$, so it cannot be equal to $k$.
This only leaves us with the case of even $m=2k$. In this case the sum is
\[
S \equiv \frac{(2k)(2k-1)}{2} + \begin{cases} -1 \\ 0\end{cases} \equiv -2k+ \begin{cases} -1 \\ 0\end{cases} \pmod{2k+1}
\]
while the only $n$ we have to avoid is $m^2+\frac{m}{2} = 4k^2+k \equiv k(4k+1) \equiv 2k^2 \equiv -k \pmod{2k+1}$. And again we are done, provided that we do not have
\[
-2k + \begin{cases} -1 \\ 0\end{cases} \equiv -k \pmod{2k+1},
\]
that is $k \equiv -1,0 \pmod{2k+1}$, which is again impossible unless $k=0$, which however means $m=1$, that we do not need to consider. Yay, take that, Boris!

In conclusion,

• If $n \not \in [m^2,m^2+m]$, we present Boris with the partition $\{1,2\},\{3,4\},\cdots,\{2m-1,2m\}$: this forces his sum to lie in the interval $[m^2,m^2+m]$, and therefore different from $n$.
• If $m$ is odd and $n \in [m^2,m^2+2m]$ is not $m^2,m^2+m$, then we give Boris the partition $\{1,m+1\}, \cdots, \{m,2m\}$. This forces him to end up with a sum that is congruent to $\frac{m(m+1)}{2} \pmod{m}$, which in particular is different from $n$. We use the same partition if $m$ is even, $n \in [m^2,m^2+2m]$, and $n \neq m^2+\frac{m}{2}$.
• Finally, for the few remaining values of $n$ (namely $n=m^2+m/2$ if $m$ is even, $n=m^2, m^2+m$ if $m$ is odd), we foil Boris' evil plans by using the partition in \eqref{eq:FinalPartition}: Boris cannot obtain $n$ as sum, because this would lead to a contradiction modulo $m+1$.

Comments. While this problem is not very easy, there are many low-hanging fruits that one should reach early on in their solution attempts. Namely, the partitions $\{1,2\}, \{3,4\}, \ldots, \{2m-1,2m\}$ and $\{1,m+1\},\{2,m+2\}, \ldots, \{m,2m\}$ already rule out most of the values of $n$, and an experienced problem solver should take very little time to notice that they work most of the time. As for the extra idea to rule out the few remaining cases, it is less standard and certainly partially helped by doodling and making examples, but one should also keep in mind that (unless the problem is really hard!) there should be an easy description for these partitions. In other words: either we're completely off track, and the problem is done in an entirely different way¹, or there has to be a way to write down the partitions we're missing. So it only makes sense to try very regular partitions, obtained by following very simple patterns; and I wouldn't rule out the possibility that, among the reasonable partitions that one might write down, there's more than one that works for – say – $n=m^2$. As a matter of fact, more 'regular' (='easy to describe algorithmically') partitions are a priori better not just because there's a bias in olympiad problems towards having 'simple' solutions², but also because their simple description is often our only hope of proving something about them (in our case, congruences on the sums that can be obtained). In other words, what I'm saying is that, while you despair and attack various small cases, you should not waste time trying random partitions, because even if they did work, you would have no idea how to replicate that pattern for different values of $m$ and $n$.

¹ maybe by counting how many partitions there are in total, how many sums can be realized from any given partition, and then coming up with an incredibly clever idea

² yes, this is metagaming. Can you deny it's true?