Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2013 Canadian MO Problems/Problem 2

Problem

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

Solution

First, we show that this is impossible for even numbers. Let n be an even number. Consider the first sum: 0. This obviously leaves a remainder of 0 when divided by $n+1$. Then, consider the final sum. This sum will be equal to the sum of the first $n$ integers, which is equal to $\frac{(n)(n+1)}{2}$. Since $\frac{n}{2}$ is an integer, $\frac{n}{2} * (n+1)$ is a multiple of $n+1$, and therefore also leaves a remainder of 0 when divided by $n+1$. Since the first and last sums leave the same remainder, we have proven that n cannot be even.


Next, we show a construction for any odd n. consider the sequence $0, 1, n-1, 3, n-3, \dots, n-2, n-(n-2), n$. since n is odd, when we subtract an odd number from it, we get an even number. Therefore in this sequence, the odd indexed terms start with 0, then they constitute the even numbers starting from n-1 and descending down through the consecutive even numbers down to 2. The even indexed terms start with 1 and constitute the ascending odd numbers, ending with n. Therefore this sequence contains all the numbers from 0 to n inclusive without repeats. Next, we consider the sequence of remainders. These go $0, 1, n, 2, n-1, \dots \frac{n+1}{2}, \frac{n-1}{2}$. It is clear to see why the first three remainders are what they are. If you start with the third term in our original sequence and consider sums of two adjacent numbers, the sequence goes $n+2, n, n+2 \dots$. That means that to get from the term in index 2N+1 to index 2N+3, we add $(n+2) mod (n+1) = 1$. so, the odd indexed terms go up by one each time. similarly, to get from the term in index 2N to the term in index 2N+2 we add $(n) mod (n+1) = -1$. So, the terms in even indexes go down by one each time. Therefore, every number between 0 and n appears in the sequence of remainders, and this construction works with every odd number.


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2013_Canadian_MO_Problems/Problem_2&oldid=247572"