interesting combinatorics EGMO P5

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

interesting combinatorics EGMO P5

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: EGMO 2015, Problem 5

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

717 posts

#1 h Apr 17, 2015, 10:58 AM • 5 Y

Y by JustinHW, Adventure10, Mango247, HoRI_DA_GRe8, GeoKing

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$ .

This post has been edited 2 times. Last edited by v_Enhance, Apr 18, 2015, 5:12 PM
Reason: \dots

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

652 posts

#2 h Apr 17, 2015, 11:07 AM • 4 Y

Y by JustinHW, Adventure10, Mango247, HoRI_DA_GRe8

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

255 posts

#3 h Apr 17, 2015, 11:37 AM • 4 Y

Y by JustinHW, Adventure10, Mango247, HoRI_DA_GRe8

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

314 posts

#4 h Apr 17, 2015, 2:06 PM • 4 Y

Y by JustinHW, Adventure10, Mango247, HoRI_DA_GRe8

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).

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6877 posts

#5 h Apr 18, 2015, 5:08 PM • 6 Y

Y by Wizard_32, rashah76, JustinHW, Adventure10, Mango247, HoRI_DA_GRe8

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.

This post has been edited 1 time. Last edited by v_Enhance, Apr 18, 2015, 5:11 PM
Reason: clarify starcraft analogy

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3 posts

PaweU

#6 h May 17, 2016, 9:30 AM • 5 Y

Y by JustinHW, Adventure10, Mango247, HoRI_DA_GRe8, kiyoras_2001

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\}$ ?

This post has been edited 1 time. Last edited by PaweU, May 17, 2016, 9:30 AM
Reason: Mistake

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1671 posts

pad

#8 h Jul 18, 2020, 11:07 PM • 3 Y

Y by JustinHW, Mango247, HoRI_DA_GRe8

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$ .

Remarks

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2726 posts

#9 h Sep 9, 2020, 2:44 AM • 2 Y

Y by Mango247, HoRI_DA_GRe8

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$

This post has been edited 1 time. Last edited by jj_ca888, Sep 9, 2020, 2:45 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

GeronimoStilton

1521 posts

GeronimoStilton

#10 h Dec 5, 2020, 9:14 PM • 6 Y

Y by awang11, jozuch, Mango247, Mango247, Mango247, HoRI_DA_GRe8

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5001 posts

#11 h May 18, 2021, 12:31 PM • 4 Y

Y by centslordm, Mango247, Mango247, HoRI_DA_GRe8

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

579 posts

#12 h Dec 25, 2021, 4:40 AM • 1 Y

Y by HoRI_DA_GRe8

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

121 posts

mijail

#13 h Feb 16, 2022, 8:21 PM • 1 Y

Y by HoRI_DA_GRe8

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8859 posts

#14 h Dec 27, 2023, 3:49 AM • 2 Y

Y by HoRI_DA_GRe8, GeoKing

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

597 posts

#17 h Jan 2, 2024, 5:49 PM • 2 Y

Y by sanyalarnab, GeoKing

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$

This post has been edited 2 times. Last edited by HoRI_DA_GRe8, Jan 2, 2024, 7:35 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

457 posts

#19 h Mar 3, 2024, 2:39 PM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1865 posts

#20 h Mar 12, 2024, 10:45 PM

Y by

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cursed_tangent1434

620 posts

cursed_tangent1434

#21 h Aug 24, 2024, 5:57 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

71 posts

#22 h Dec 6, 2024, 7:54 PM

Y by

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.

This post has been edited 1 time. Last edited by emi3.141592, Dec 6, 2024, 7:54 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

719 posts

#23 h Feb 20, 2025, 11:25 AM

Y by

Similar

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

616 posts

#24 h Feb 28, 2025, 3:53 PM

Y by

First note that $(1, m + 1), (2, m + 2), \dots, (m, 2m)$ implies it suffices to prove the statement when $n\equiv \frac{m(m+1)}2\pmod m.$ From $(1, 2), (3, 4), \dots, (2m - 1, 2m),$ it suffices to prove the statement for $n\in[m^2, m^2 + m].$ We now do casework on parity of $m$ .

If $m\equiv0\pmod{2},$ then it suffices to prove statement for $n = m^2 + \frac m2.$ Take $(1, m + 2), (2, m + 3), \ldots, (m - 1, 2m), (m, m + 1)$ . From modulo $m + 1,$ this is impossible unless $m\leq2.$ $m = 2$ is easy to hand check.

If $m\equiv1\pmod2,$ then we prove statement for $n = m^2, m^2 + m.$ Take $(1, m + 2), (2, m + 3), \ldots, (m - 1, 2m), (m, m + 1)$ . Modulo $m + 1$ finishes for $m\geq5.$ Handcheck $m = 1, 3.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

37 posts

Avron

#25 h Mar 9, 2025, 10:11 PM

Y by

Fun one

By taking the pairs $(i,i+1)$ the minimum sum Boris can make is $1+3+...+(2m-1)=m^2$ and the maximum is $2+4+...+2m=m^2+m$ so we only need to consider $m^2\leq n\leq m^2+m$ . By taking the pairs $(i,m+i)$ every sum is $1+2+...+m=\frac{m(m+1)}{2}\equiv 0,\frac{m}{2}$ mod $m$ depending on the parity of $m$ .

Assume $n$ is odd and $n\in\{m^2,m^2+m\}$ . Take the pairs $(i,i+m+1)$ for $0<i<m+1$ (instead of $2m+1$ write $m+1$ ). Modulo $m+1$ every sum is $\frac{m(m-1)}{2}+b\equiv b-\frac{m-1}{2}$ where $b\in\{0,m\}$ , so it is clearly not congruent to $m^2$ nor $m^2+m$ . For $m$ even take the same pairing then the possible values modulo $m+1$ are $\frac{m(m-1)}{2}+b\equiv b-m$ so it is again not congruent to $m^2+\frac{m}{2}$ and we're done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

45 posts

#26 h Apr 19, 2025, 6:31 AM

Y by

Nice, we have two constructions -

Claim: $(1,m +1), (2,m +2), (3, m+3)... (m, 2m)$ will only yield sum that is $S \equiv m(m +1)/2 \mod m$ ,
Because even if we change the terms we pick inside the pairs, it will only change by a sum of $m$
$\blacksquare$

Claim: $(1,2), (3,4), (5,6)... (2m - 1, m)$ can yield any number between $m^2$ and $m^2 + m$
because the difference between the terms in each pair is exactly $1$ , so if $S$ is achievable, so is $S +1$ as long as it is lesser than or equal to the maximum possible sum.
$\blacksquare$

so, in claim 2, we can only obtain $S$ such that -

$m^2 \leq S \leq m^2 + m$
and note that no such $S \equiv m(m+ 1)/2 \mod m$ , so they are disjoint and if $S$ falls in any one of the categories, we simply pick the other one.

$\square$
:starwars:

:starwars:

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a