Repovive
  • Dashboard
  • Ranking
  • Submissions
  • Discussion
  • Rules
  1. Contests
  2. Math Contest Round 1
  3. M1D

My submissions

/
/
/
/

Announcements

My submissions

/
/
/
/

Announcements

Using prefix sums

Put m=n+1m=n+1m=n+1. Let X,YX,YX,Y be the sets of prefix sums of the two sequences, including zero. Each has mmm elements.

A collision x+y=x′+y′x+y=x'+y'x+y=x′+y′ between distinct pairs is equivalent to a common positive difference in X,YX,YX,Y: after exchanging the pairs, x−x′=y′−y>0x-x'=y'-y>0x−x′=y′−y>0. These differences are exactly nonempty segment sums.

Thus all m2m^2m2 sums are distinct. Their maximum is

max⁡X+max⁡Y=n(n+2)=m2−1,\max X+\max Y=n(n+2)=m^2-1,maxX+maxY=n(n+2)=m2−1,

so they represent every integer in {0,…,m2−1}\{0,\ldots,m^2-1\}{0,…,m2−1} exactly once.

Conversely, such sets give positive sequences with disjoint segment sums by taking consecutive differences of their sorted elements. We must also check that neither sequence is constant.