Nice problem! I hope some kind of parity argument will help....

I think she should arrange in such a way that each pair sum will be equal to $n$ or factors of $n$...

First,partiotion $(1,m+1),(2,m+2),...(m,2m)$ can have only numbers $m*(m+1)/2$ $modm$ and the partiotion $(1,2),(3,4),...(2m-1,2m)$ can have only numbers that are beetwen $m*m$ and $m*m+m$.Now,we have two cases: Case $1$:$m$ is even.Let $m=2k$.Now,we are only left to prove that for $n=k*(4k+1)$ is a partition and take $(1,4k),(2,3),(4,5),....(4k-2,4k-1)$.Now,if we pick $4k$ the least sum will be $4k*k+2*k$ and if we pick $1$ the maximum sum will be $4k*k$,so we can't get $k*(4k+1)$. Case $2$:$m$ is odd.We only need a partition for $m^2$ and $m*m+m$,these are obviosly equivalent and the partition $(1,2m-1),(2,2m),(3,4),...(2m-3,2m-2)$ satisfayes the conditions(the reasoning is pretty much the same as in the previous case).

Cute problem. The idea of trying to find a few constructions which eradicate all the cases works; find a couple nice ones that eliminate all but a few survivors, then attack the few holdouts. (It's like using reavers on zerglings: knock out 90% of the lings with a couple scarabs and then have the zealots finish the rest.) For all $m$, we can consider the following two pairings: \[ \begin{array}{ccccc} 1 & 3 & \dots & 2m-3 & 2m-1 \\ 2 & 4 & \dots & 2m-2 & 2m \end{array} \qquad\text{and}\qquad \begin{array}{ccccc} 1 & 2 & \dots & m-1 & m \\ m+1 & m+2 & \dots & 2m-1 & 2m \end{array} \] The former pairing eradicates all numbers outside $[m^2, m^2+m]$ while the latter eradicates all numbers which are not $\tfrac 12 m(m+1) \pmod m$. In what follows, assume $m \ge 4$ (smaller cases can be dispensed with by hand). If $m$ is odd, we need to annihilate the values $m^2$ and $m^2+m$. We can do this with the pairing \[ \begin{array}{ccccc} 1 & 2 & \dots & m-1 & m \\ m+2 & m+3 & \dots & 2m & m+1 \end{array} \] The possible values of this modulo $m+1$ are $\tfrac 12 m(m+1) + \{0,1\} \equiv \tfrac12(m+1) + \{0,1\} \pmod{m+1}$ since $m$ is odd. But $m^2$ and $m^2+m$ leave residues $1$ and $2$ modulo $m$, done. If $m$ is even (so $m+1$ is odd), then the only value we need to eliminate is $m^2 + \tfrac 12 m$, which is $\tfrac 12 \pmod{m+1}$. The same pairing as in the even cases has possible values $\tfrac 12m (m+1) + \{0,1\} \equiv \{0,1\} \pmod{m+1}$. This completes the proof.

Do you guys have any idea how that could work with Anstasia instead of making pairs of $\{ 1,2, \ldots, 2k\}$ would make m-tuples of $\{ 1,2, \ldots, mk\}$?

We want to show that there cannot be an $n$ which is a possible sum for each pair-partition. Suppose such an $n$ existed. Then $n$ is a possible sum for $(1,m+1),(2,m+2),\ldots,(m,2m)$. Every sum in this pair-partition is $1+2+\cdots+m \equiv \tfrac{m(m+1)}{2} \pmod{m}$. Hence $n\equiv \tfrac{m(m+1)}{2} \pmod{m}$. This is 0 mod $m$ for odd $m$ and $m/2 \mod m$ for even $m$. $(1,2),(3,4),\ldots,(2m-1,2m)$. Every sum in this pair-partition is in the range $1+3+\cdots+(2m-1)=m^2$ and $2+4+\cdots+2m=m^2+m$, and clearly any number in $[m^2,m^2+m]$ is achievable. So $n \in [m^2, m^2+m]$. These two narrow down $n$ to being $n=m^2, m^2+m$ for odd $m$, and $m^2+m/2$ for even $m$. Consider the partition $(1,m+2),(2,m+3),\ldots,(m-1,2m),(m,m+1)$. This is $\tfrac{m(m-1)}{2}$ minus 0 or 1 mod $m+1$. Case 1: $m$ is odd. The above becomes $\tfrac{1-m}{2}, \tfrac{-1-m}{2}\pmod{m+1}$. Since $m^2\equiv 1, m^2+m\equiv 0 \pmod{m+1}$, this proves there are no values of $n$ for odd $m$. Case 2: $m$ is even. Then $\tfrac{m(m-1)}{2} \equiv \tfrac{m}{2}\cdot (-2) \equiv 1 \pmod{m+1}$. And $m^2+\tfrac{m}{2} \equiv 1+\tfrac{m}{2} \pmod{m+1}$, which is enough to finish for odd $m$.

Consider the pairings $\{(1, m+1), (2, m+2), \ldots , (m, 2m)\}$ and $\{(1, 2), (3, 4), \ldots , (2m-1, 2m)\}$. In the first pairing, no matter how Boris chooses, the final sum $n$ must be $\tfrac12 {m(m + 1)} \pmod{m}$ so Anastasia can always choose this pairing to kill $n \not \equiv \tfrac12 {m(m + 1)} \pmod m$. In the second pairing, the sum $n$ is bounded between values $1 + 3 + \ldots + 2m-1 = m^2$ and $2 + 4 + \ldots + 2m = m(m+1)$ independent of Boris's choices. Hence Anastasia can always choose this pairing to kill $n > m^2 + m$ and $n < m^2$. It remains to consider when $n \equiv \tfrac12m(m+1) \pmod m$ and $n \in [m^2, m^2 + m]$. We split cases based on whether $m$ is even or odd: If $m$ is odd, then $n$ must be either $m^2$ or $m^2 + m$. We may choose the pairing\[\{(1, m+2), (2, m+3), \ldots , (m-1, 2m), (m, m+1)\}.\]No matter how Boris chooses his numbers, $n$ must be $(1 + 2 + \ldots m-1) - 0, 1 = \tfrac12m(m-1) - 0, 1$ modulo $m + 1$. Replacing $m$ with $-1$ and adding $m+1$ simplifies this to $\tfrac12(m + 1)$ or $\tfrac12(m + 3)$ modulo $m + 1$. Finally note that we have $m^2 + m \equiv 0$ modulo $m + 1$ which is not possible, and $m^2 \equiv 1$ modulo $m + 1$, which is also not possible. If $m$ is even, then $n$ must be $m^2 + \tfrac12m$. We again choose the pairing\[\{(1, m+2), (2, m+3), \ldots , (m-1, 2m), (m, m+1)\}.\]Taking modulo $m+1$ again we see that $n$ must again be $\tfrac12m(m - 1) - 0, 1$ modulo $m + 1$ and simplifying this by replacing $m-1$ with $-2$ and then adding $m + 1$ yields $n \equiv 0, 1$ modulo $m + 1$. However\[n = m^2 + \frac12m \equiv \frac12m + 1 \not \equiv 0, 1 \pmod{m+1}\]which is not possible. So indeed, we have proven that Anastasia can always cuck Boris given $m$ and $n$. $\blacksquare$

We use the following silly argument. Let $N$ denote the number of sets of $m$ elements of $\{1,2,\dots,2m\}$ summing to $n$. For any particular such set, the probability that a random selection of pairs by Anastasia will not make it impossible is \[\frac{m!}{\displaystyle\binom{2m}{\underbrace{2,\dots,2}_{m\mbox{ times}}}} = \frac{m!}{\displaystyle\frac{2m!}{2^m}} = \frac{m!}{m!\cdot (2m-1)!!} = \frac{1}{(2m-1)!!}.\]So by linearity of expectation, it suffices to show $N<(2m-1)!!$. In fact, for any $i,n,m$ with $m>1$ we claim that the number of sets of $i$ elements of $\{1,\dots,2m\}$ with sum $n$ is less than $(2m-1)!!$. The proof is by induction on $m$. For the case of $m=2$, note the result is trivial for $i\in\{0,1,3,4\}$ because the sets of $i$ elements all have different sums in each case, and for $i=2$ it suffices to count the possible sets for each $n$. The possibilities are $3=1+2,4=1+3,5=1+4=2+3,6=2+4,7=3+4$. Since the most sets for any value of $n$ is $2$ and $2<3!!=3$, we are done. For the induction step, note that for any set of $i$ elements with sum $n$ either both $2m,2m-1$ are included, exactly one of $2m,2m-1$ is included, or none of $2m,2m-1$ is included. By the induction hypothesis, this yields at most $2^2\cdot (2m-3)!! = 4\cdot (2m-3)!! < (2m-1)!!$ sets, so we are done.

I'm never sure what to feel about problems that are construction and only construction. Anastasia can always select the partition $(1,2),(3,4),\ldots,(2m-1,2m)$ to eliminate everything except for $[m^2,m^2+m]$. She can also always select the partition $(1,m+1),(2,m+2),\ldots,(m,2m)$, which eliminates everything except for the set: $$S=\left\{\frac{m(m+1)}{2},\frac{m(m+3)}{2},\ldots,\frac{m(3m+1)}{2}\right\}.$$Now we consider the two cases based on the parity of $m$: Case 1: $m$ is even. Then the intersection of $S$ and $[m^2,m^2+m]$ is $\tfrac{1}{2}m(2m+1)$. To show $\tfrac{1}{2}m(2m+1)$ cannot be achieved, consider the partition: $$(1,2m),(2,3),(4,5),\ldots,(2m-2,2m-1).$$From $(2,3),(4,5),\ldots,(2m-2,2m-1)$, Boris can obtain only the sums in the set: $$S=\{m^2-m,m^2-m+1,\ldots,m^2-1\}.$$Hence the set of sums Boris can obtain with this partition is equal to: $$S+\{1\}\cup S+\{2m\}=\{m^2-m+1,m^2-m+2,\ldots,m^2\}\cup \{m^2+m,m^2+m+1,\ldots,m^2+2m-1\}.$$But we have $\tfrac{1}{2}m(2m+1)=m^2+\tfrac{1}{2}m$, hence: $$m^2<m^2+\frac{1}{2}m<m^2+m,$$so with this partition Boris cacnnot achieve $\tfrac{1}{2}m(2m+1)$. Hence Anastasia can always select the pairs so Boris cannot make the sum equal to $n$ for even $n$. Case 2: $m$ is odd. Then the intersection of $S$ and $[m^2,m^2+m]$ is $m^2,m^2+m$. To show that $m^2,m^2+m$ cannot be achieved, consider the partition: $$(1,m),(2,m+1),\ldots,(m-1,2m-2),(2m-1,2m).$$The sum Boris can obtain from $(1,m),(2,m+1),\ldots,(m-1,2m-2)$ is in the set: $$S=\left\{\frac{m(m-1)}{2},\frac{(m+2)(m-1)}{2},\ldots,\frac{(3m-2)(m-1)}{2}\right\}.$$Suppose Boris picks $2m$ from its pair. Then we want to show that $m^2-2m,m^2-m$ are not in $S$. We can easily see that $S$ is exactly the numbers $\tfrac{1}{2}(m+2k)(m-1)$, where $0 \leq k <m$. Suppose $m^2-2m \in S$. Then: $$\frac{(m+2k)(m-1)}{2}=m^2-2m \implies -2k \equiv 0 \pmod{m} \implies m \mid k,$$snce $m$ is odd, but this is impossible since $k<m$. We can eliminate $m^2-m$ with the exact same procedure, hence Anastasia can always select the pairs so Boris cannot make his sum equal to $n$ for odd $m$. And we're done. $\blacksquare$

Consider the set of pairs $(1,2),(3,4),\ldots (2m-1,2m)$, which only hit values in $[m^2,m^2+m]$. Next, consider the set of pairs $(1,2m),(2,3),(4,5),\ldots (2m-2,2m-1)$, which only hits values in $\{1,2m\} + [m^2-m, m^2-1]= [m^2-m+1,m^2] \cup [m^2+m,m^2+2m-1]$. We now deal with $m^2$ and by extension $m^2+m$ to finish. Firstly, $m=3$ works with $(1,6),(2,4),(3,5)$. If $m$ is even, then the set $(1,m+1),(2,m+2),\ldots, (m,2m)$ kills $m^2$ because $\frac{m(m+1)}{2}+k\cdot m = m^2$ has no solutions. If $m$ is odd, the set $(1,2m),(2,m+1),(3,m+2),\ldots, (m,2m-1)$. Firstly, $m^2\equiv 1 \pmod{m-1}$ and $1+2+3+\cdots + m\equiv \frac{m+1}{2} \pmod{m-1}$. We can only add $2m-1\equiv 1$ or $m-1\equiv 0$, neither of which gets us to $1$ for $m\geq 5$. Thus, all possible values can be excluded, so we are done. $\blacksquare$.

Nice problem! Suppose that the problem it's false. Then consider the pairs $\{ (1,2); (3;4); \dots (2i-1,2i) \dots (2m-1,2m) \}$ then $n \in [m^2, m^2+m] $ Now consider the collections of pairs $\{(1,m+1); (2,m+2) \dots (i,i+m) \dots (m, 2m)\}$ and $\{(1,m+2); (2,m+3) \dots (i,i+m+1) \dots (m-1,2m); (m,m+1) \}$. With the first collection we have that: $$n \equiv 1+2+ \dots + m \equiv \frac{m(m-1)}{2} \pmod m $$ Also with the second collection we have: $$n \equiv 1 + 2+ \dots + (m-1) + e \equiv \frac{m(m-1)}{2} +e \pmod {m+1}$$ With $e \in \{0,-1\}$ then $ n = \frac{m(m-1)}{2} + mt \equiv \frac{m(m-1)}{2} +e \pmod {m+1} \implies m+1 \mid t+e$ But $n \in [m^2, m^2+m] \implies t \in [\frac{m+1}{2}, \frac{m+3}{2}] \implies t+e \in [\frac{m-1}{2}, \frac{m+3}{2}] $. This is contradicction becuase $m+1 \leq t+e$. $\blacksquare$

Quite a cute problem; the details come together very nicely. Consider the following three groupings: Grouping A, $(1, 2), (3, 4), (5, 6), \dots, (2m-1, 2m)$. Grouping B, $(1, 2m), (2, 3), (4, 5), \dots, (2m-2, 2m-1)$. Grouping C, $(1, 2m-1), (2, 2m), (3, 4), \dots, (2m-3, 2m-2)$. Notice that Grouping A restricts all possible $n$ to those between $1+3+\cdots+2m-1 = m^2$ and $2+4+\cdots+2m = m^2+m$. On the other hand, considering Grouping B, the largest sum attainable without selecting $2m$ from the first pair is $m^2$, while the smallest sum attainable while selecting $2m$ is $m^2+m$. Finally, by considering Grouping C, notice that we can form a sum of $1+2m+4+6+\cdots+2m-2 = m^2+m-1$. The next largest sum must substitute $2m$ for $2$. If $1$ is substituted for $2m-1$, the maximal sum still remains at $m^2+m-1$; otherwise, it jumps to greater than $m^2+m$. Thus $m^2+m$ cannot be attained through Grouping C. Similarly, $m^2$ cannot be attained through Grouping C either. Combining all three groupings thus eliminates all possible values of $n$.

Solved with Kamatadu, Distorteddragon1o4 and sanyalarnab Consider 4 groupings 1. Grouping A, $\boxed{(1, 2), (3, 4), (5, 6), \dots, (2m-1, 2m)}$.This restricts $n$ in the range $[m^2,m^2+m]$ 2.Grouping B, $\boxed{(1,m+1), (2, m+2), (3,m+3), \dots, (m,2m)}$.In this grouping any $n$ produced should be always congruent to $0 \pmod m$ for $m$ odd as, $$n \equiv 1+2+3+\cdots +m \equiv \frac{m(m+1)}{2} \equiv 0 \pmod m$$So only $n$ left for odd is $m^2,m^2+m$ the Grouping C avoids it (to be proved). For $n$ even , $$n \equiv 1+2+3+\cdots +m \equiv \frac{m(m+1)}{2} \equiv \frac{m}{2} \pmod m$$So for $m$ even $n$ restricts to $[m^2+\frac{m}{2}]$ 3.Grouping C, $\boxed{(1,2m),(2,m+1),\cdots,(m,2m-1)}$ Any sum of grouping C should be of the form $\boxed{\frac{m(m+1)}{2}+(2m-1)\cdot e+(m-1) \cdot k}$ where $e=0,1$ and $0 \leq k \leq m-1$. Now if, $\frac{m(m+1)}{2}+(2m-1)+(m-1) \cdot k=m^2$ ,then by arranging we get that $m-1 |\frac{m+1}{2}$ but $\frac{m+1}{2}\le m-1 $ for $m \ge 3$ but for $m=3$ it can be manually checked that this construction works.If $\frac{m(m+1)}{2}+(m-1) \cdot k=m^2$ then we have $k=\frac{m}{2}$ ,impossible since $m$ is odd. Now ,$\frac{m(m+1)}{2}+2m-1+(m-1) \cdot k=m^2+m \implies k \equiv m-1 \pmod m$ but putting $k=m-1$ gives $m=\frac{m(m+1)}{2}$ but we seriously don't care about $1$.If $\frac{m(m+1)}{2}+(m-1) \cdot k=m^2+m$ then $m-1|\frac{m+1}{2} $ a.k.a "a joke" 4.Grouping D,$\boxed{(1,m+2),(2,m+3),\cdots (m-1,2m),(m,m+1)}$ for $m$ even The sums are of the form ,$\boxed{\frac{m(m+1)}{2}+(m+1)k+0/1}$ Now, $$\frac{m(m+1)}{2}+(m+1)k+0/1=m^2+\frac{m}{2} \implies m+1 |\frac{ m^2}{2}/\frac{m^2-2}{2}$$But $m+1|m^2-1$ so it can't divide either one of $\frac{m^2}{2}$ or $\frac{m^2-2}{2}$ and hence grouping D avoids $m^2+\frac{m}{2}$ for all even $m$. Since all numbers could be avoided by the above $4$ groupings, we are done $\blacksquare$

:knock knock :who's in there? :Codeforces 1404D

1. $(1, 2), (3, 4), ..., (2m-1, 2m)$ eliminates $n < m^2$ and $n > m^2+m$. 2. $(1, 2m), (2, 3), (4, 5), ..., (2m-2, 2m-1)$ eliminates $m^2 < n < m^2+m$. 3. $(1, 2m-1), (2, 2m), (3, 4), (5, 6), ..., (2m-3), (2m-2)$ eliminates $m^2$ and $m^2+m$.

We first consider $n < m^2$ and $n > m^2+m$. Then, Anastasia provides the pairing \[\frac{1}{2} \frac{3}{4} \dots \frac{2m-1}{2m} \]Note that then, \[S \ge 1+3+\dots + 2m-1 = m^2\]and \[S \le 2 + 4+ \dots + 2m = m^2 +m\]implying that for all $n < m^2$ or $n > m^2+m$ Boris cannot make his sum equal to $n$. Now, we have two cases to examine. Case 1 : $m$ is even, and $m^2 \le n \le m^2+2$. Here, say $n \ne m^2 + \frac{m}{2}$, then Anastasia will provide the pairing, \[\frac{1}{m+1} \frac{2}{m+2} \dots \frac{m}{2m} \]Then, from each pair Boris must chose a number which is $1,2,\dots , 0 \pmod{m}$ and thus, \[S \equiv 0 + 1 + 2 + \dots + m-1 \equiv \frac{m(m+1)}{2} \equiv \frac{m}{2} \pmod{m}\]Thus, since $m^2 \le n \le m^2+2$ and $n \ne m^2 + \frac{m}{2}$, it is impossible for Boris to make his sum equal to $n$. Now, if $n=m^2 + \frac{m}{2}$, for $m=2$, Anastasia provides the pairing \[\frac{1}{4} \frac{2}{3}\]from which it is obviously impossible to make a sum of 5. For $m >2$, we consider an odd prime $p \mid m-1$ (must exist since $m-1>1$ is odd) and then, Anastasia provides the pairing, \[\frac{1}{m} \frac{2}{m+1} \dots \frac{m-1}{2m-2}\frac{2m-1}{2m}\]Then, from the first $m-1$ pairs, Boris must chose a number which it $1,2,\dots , 0 \pmod{m-1}$ and from the last pair, a number which is either 1 or 2 $\pmod{m-1}$. Thus, \[S \equiv 0 + 1 + 2 + \dots + m-2 + a \equiv \frac{m(m-1)}{2} + a \equiv a \pmod{m-1}\]where $a\equiv 1,2\pmod{m-1}$. But, note that letting $m=2k$, \[m^2 + \frac{m}{2} \equiv k+1 \pmod{m-1}\]which is not $1,2 \pmod {m-1}$ for all $k > 1$. Thus, Boris can never make his sum equal to $n$ in this case. Case 2 : $m$ is odd, and $m^2 \le n \le m^2+2$. Here, say $n \not \in \{m^2,m^2+m\}$, then Anastasia will provide the pairing, \[\frac{1}{m+1} \frac{2}{m+2} \dots \frac{m}{2m} \]Then, from each pair Boris must chose a number which is $1,2,\dots , 0 \pmod{m}$ and thus, \[S \equiv 0 + 1 + 2 + \dots + m-1 \equiv \frac{m(m+1)}{2} \equiv 0 \pmod{m}\]Thus, since $m^2 \le n \le m^2+2$ and $n \not \in \{m^2,m^2+m\}$, it is impossible for Boris to make his sum equal to $n$. Now, if $n \in \{m^2,m^2+m\}$, and $m=3$, Anastasia provides the pairing, \[\frac{1}{5} \frac{2}{6} \frac{3}{4} \]from which it is easy to check that Boris cannot make a sum of either $9$ or $12$. When $m=5$, Anastasia provides the pairing, \[\frac{1}{2} \frac{3}{7} \frac{4}{9} \frac{5}{6} \frac{8}{10}\]from which it can be confirmed that Boris cannot make a sum of either $25$ or $30$. Now, when $m >5$, Anastasia provides the pairing, \[\frac{1}{m-1} \frac{2}{m} \dots \frac{m-2}{2m-4}\frac{2m-3}{2m-1} \frac{2m-2}{2m}\]Then, from each of the first $m-2$ pairs Boris must chose a number which is $1,2,\dots , 0 \pmod{m-2}$ and thus, \[S \equiv 0 + 1 + 2 + \dots + m-3 + a + b\equiv \frac{({(m-2)(m-1)}}{2} + a+ b \equiv a+b \pmod{m}\]Now, $m^2 \equiv 4 \pmod{m-2}$ and $m^2 +m \equiv 6 \pmod{m-2}$. But, it is easy to see from the pairing that since $2m-1 \equiv 3 , 2m-2 \equiv 2 , 2m-2 \equiv 2 $ and $2m \equiv 4 \pmod{m-2}$ none of the possible choses from the last two pairs allow this. Thus, in thic case as well Boris cannot make the sum of the numbers equal to $n$ and we are done.

Consider the following pairings: \[ (1, 2), (3, 4), \ldots, (2m-1, 2m) \]\[ (1, m+1), (2, m+2), \ldots, (m, 2m). \]The first discards all \(n < m^2\) and \(n > m^2 + m\). The second discards all \(n \not\equiv \frac{m(m+1)}{2} \pmod{m}\). Now, we consider two cases. Case 1: If \(m\) is odd, we only need to discard \(n = m^2, m^2+m\). For this, consider the pairing: \[ (1, m+2), (2, m+3), \ldots, (m-1, 2m), (m, m+1). \]The only values that can be obtained are \[ n \equiv \frac{m(m+1)}{2} + 0, 1 \pmod{m+1}. \]But \(m^2 \equiv 1 \pmod{m+1}\) and \(m^2 + m \equiv 0 \pmod{m+1}\). Case 2: If \(m\) is even, we need to discard \(n = m^2 +\frac{m}{2}\equiv\frac{m}{2}+1 \pmod{m+1}\). Using the same arrangement as the previous case, the only values we can obtain are \[ n \equiv \frac{m(m+1)}{2} + 0, 1 \pmod{m+1}. \]And we are done.