Partial Sums of Sequence

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

Partial Sums of Sequence

G H J

Reveal topic tags

modular arithmetic

number theory unsolved

L

G H BBookmark kLocked kLocked NReply

Source: 2013 CMO #2

The post below has been deleted. Click to close.

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

4216 posts

#1 h Mar 31, 2013, 8:43 PM • 3 Y

Y by Davi-8191, Adventure10, Mango247

The sequence $a_1, a_2, \dots, a_n$ consists of the numbers $1, 2, \dots, n$ in some order. For which positive integers $n$ is it possible that the $n+1$ numbers $0, a_1, a_1+a_2, a_1+a_2+a_3,\dots, a_1 + a_2 +\cdots + a_n$ all have different remainders when divided by $n + 1$ ?

Z K Y

The post below has been deleted. Click to close.

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

34 posts

#3 h Apr 1, 2013, 3:33 PM • 1 Y

Y by Adventure10

The answer is n odd. We can easy to see that when consider the sum $a_1+a_2+...+a_n$
If n=2k+1, we will creat a permutation: $0,b_1,b_2,...,b_{2k+1}$ with ${b_i=a_1+...+a_i}$
I have a example: $0,b_1,b_2,...,b_{2k+1}$ = $0,1,2k,2,2k-1,...,k-1,k+1,k$ . You can check the permutation with $a_1+a_2+...+a_n$ respectly sastyfing

Z K Y

The post below has been deleted. Click to close.

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

2180 posts

#4 h Nov 2, 2013, 4:59 PM • 2 Y

Y by Adventure10, Mango247

To see why $n$ even doesn't work just note that $a_1+a_2+\cdots +a_{2k}=\frac{2k(2k+1)}{2}=k(2k+1)\equiv 0\pmod {2k+1}$ . Hence when $n$ is even $0,a_1,a_2,...,a_{2k}$ do not form a complete residue class modulo 2k+1 since $0$ and $a_{2k}$ are both $0\pmod {2k+1}$ .

Z K Y

The post below has been deleted. Click to close.

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

595 posts

#5 h Jan 25, 2015, 9:27 AM • 4 Y

Y by Davi-8191, Adventure10, Mango247, Om245

For odd $n$ the permutation satisfying the property is
$(0,1,n-1,3,n-3,5,n-5....2,n)$
The remainders when divided by $n+1$ are $0,1-1,2,-2...(n+1)/2$ all distinct

Z K Y

The post below has been deleted. Click to close.

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

201 posts

#6 h Apr 2, 2017, 3:44 AM • 1 Y

Y by Adventure10

For even n, $n+1 \mid 1 + 2 + 3 + ... + n = \frac{(n)(n+1)}{2}$ . So it does not hold for even n.

For odd n, the n+1-tuplet (0, 1, n-1, 3, n-3, ... , 2, n) satisfies both conditions. So it holds for all odd n.

This post has been edited 1 time. Last edited by vsathiam, Apr 2, 2017, 3:44 AM
Reason: E

Z K Y

The post below has been deleted. Click to close.

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

185 posts

#7 h Aug 23, 2018, 5:48 PM • 2 Y

Y by Adventure10, Mango247

Can someone provide the insight behind guessing the sequence? I got that odd n work, but I couldn't find a sequence that worked.

Z K Y

The post below has been deleted. Click to close.

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

396 posts

#8 h May 21, 2020, 2:41 PM • 3 Y

Y by Mango247, Mango247, Mango247

Also see 1995 Russia MO, it is the same problem

Z K Y

The post below has been deleted. Click to close.

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

69 posts

#9 h May 17, 2023, 9:12 PM

Y by

Lemma: The evens do not work

The proof is easy. 1+….+n = n(n+1)/2. Then the 2 is canceled from the n, and this is 0 mod n+1. However, 0 already exists, so this shows that even n are unachievable.

Lemma: The odds all work

The issue with the final term does not matter, as n+1 will be divided by 2 and it wouldn’t have created 0 mod n+1. Now we need a valid construction. The construction is 0, 1, n-1, 3, n-3, 5, n-5…… Basically the odds and evens alternated, with n at the end. This indeed works because you get 0, 1, -1, 2, -2, ….. and everything else.

Answer: All odd integers n work

Z K Y

The post below has been deleted. Click to close.

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

187 posts

#10 h Jan 25, 2025, 4:07 PM

Y by

Note that $a_1+a_2+\cdots+a_n=\frac{n(n+1)}{2}$ and it cannot be divisible by $n+1$ , so $n$ is odd. Now, for any odd $n$ consider the construction $a_i=i$ if $i$ is odd and $a_i=n+1-i$ if $i$ is even. It is easy to check that this construction works for all odd $n$ .

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a