Let $n>1$ be a positive integer. Call a rearrangement $a_1,a_2, \cdots , a_n$ of $1,2, \cdots , n$ nice if for every $k = 2,3, \cdots , n$, we have that $a_1 + a_2 + \cdots + a_k$ is not divisible by $k$. (a) If $n>1$ is odd, prove that there is no nice arrangement of $1,2, \cdots , n$. (b) If $n$ is even, find a nice arrangement of $1,2, \cdots , n$.
Problem
Source: RMO 2024 Q1
Tags: number theory
03.11.2024 13:55
Ok since this latexed I delete my post This is trivial Note that for n odd just consider a1 +a2 + an and it’s n(n+1)/2 which is divisible by n For n even let n be 2k and do the arrangement (1,2,4,3,6,5,…,2k, 2k - 1) which is easily probed by induction
03.11.2024 14:03
(i) $n$ being odd , $a_1+a_2+\cdots+a_n=\frac{n(n+1)}{2}$ divisible by $n$ (ii) $n$ being even define $$a_{2m}=2m-1,a_{2m-1}=2m$$Now Induction kills
03.11.2024 14:26
2,1,4,3,6,5,....,2m, 2m-1.
03.11.2024 14:32
We note that $n\mid \frac{n(n+1)}{2}$ iff $n$ is odd. (a) For $k=n$, we have $\sum_{i=1}^k a_i=\frac{n(n+1)}{2}\equiv 0\pmod{n}$, so a nice arrangement does not exist. (b) Consider this sequence: $a_1=1$ and for $k\geq 2$, $$a_k=\begin{cases} \frac{k(k+1)}{2}-\sum_{i=1}^{k-1} a_i,& k\equiv 0\pmod{2}\\ k+1,& k\equiv 1\pmod{2}. \end{cases}$$For any even $k$, clearly $k\nmid \frac{k(k+1)}{2}$, and for odd $k$ we have $k\nmid \frac{k(k-1)}{2}+1$ as well, so we are done.
03.11.2024 15:17
Way too simple. For n odd, We have $n | a_1 + \dots + a_n = \frac{n(n+1)}{2}$. For $n$ even, consider the first $n$ elements of $\{2, 1, 4, 3, 6, 5, 8, 7, 10, 9, \dots \}$.
03.11.2024 15:37
From the OMC RMO livesolve. solved with rawlat_vanak, AdhityaMV, zvfrozel, and mathscrazy. (a) For this part, we note that $n \mid \frac{n(n+1)}{2}$ and thus the condition fails for $i = n$ no matter the order. $\square$ (b) For this part, we do $a_i = 1 + ((i-1) \oplus 1)$, where $\oplus$ is the so called Bitwise XOR. It may be verified that this works, since at odd indices we have an "off by one" error, whereas evens are doomed to fail. For example, for $n = 6$, this sequence is \[2, 1, 4, 3, 6, 5.\]$\square$
03.11.2024 15:38
wait how did you think of this bitwise xor thing
03.11.2024 15:47
(a) Note that if $k=n$, we have $$a_1+a_2+\dots+a_n=\frac{n(n+1)}{2}$$is divisible by $n$. (b) This is much trickier. The sequence for $n=8$ is $$2, 1, 4, 3, 6, 5, 8, 7,$$and this clearly generalizes. One can verify that this works via induction.
03.11.2024 15:59
(a) For $n = 2k+1$, $\sum_{i=1}^{n} i = (2k+1)(k+1) \equiv 0 \pmod{n}$. (b) Consider the sequence $2,1,4,3,6,5,8,7,.....,2k,2k-1$.
03.11.2024 18:37
I did Q3 and 6 full, Q5 and 1 partial from class 12 west bengal. Do you think I have any chance at all?
03.11.2024 18:47
D Determinant_is_Volume wrote: I did Q3 and 6 full, Q5 and 1 partial from class 12 west bengal. Do you think I have any chance at all? maybe good chance yes did you do q5 fully?
03.11.2024 19:02
In Q5 I assumed (but couldn’t prove) $\triangle OBD\sim\triangle OLP$, where P is the midpoint of BC. Then OB/OD=OL/LP which means OB*LP=OL*BD which in turn means OB*(AB+CD)/2=OL*(AC+BD)/2. I wrote all required explanations and drew a pretty nice figure I think.
03.11.2024 19:13
For Q1 I only got time to do (a) and write an example case for n=4 in (b). How much can I expect?
03.11.2024 19:15
part (a) is like 3 marks and n = 4 can give max 1 mark so you should expect <= 4 marks
03.11.2024 19:20
(a) For an odd $n,$ we see that $a_1+a_2+....+a_n=\frac{n(n+1)}{2},$ thus $n$ is a divisor of $\frac{n(n+1)}{2},$ (this is since we have $\frac{n+1}{2}$ which is an integer since $n+1$ is even) resulting in a contradiction. (b) We can take the sequence $2,1,4,3,6,5,8,7,…….$ we claim that this sequence is always good for an even number of terms. If we are taking the sum of the first $k$ terms where $k$ is even. Note that this sum is $1+2+3+4+5+6+7+8+…..k=\frac{k(k+1)}{2},$ we see that $\frac{\frac{k(k+1)}{2}}{k}=\frac{k+1}{2},$ which is not an integer since $k+1$ is odd. Now for the other case, this sum is $1+2+3+4+…..+(k-1)+(k+1)=\frac{k(k-1)}{2}+k+1=\frac{k(k+1)}{2}+1,$ dividing by $k$ yields $\frac{k+1}{2}+\frac{1}{k},$ note that since $k$ is a odd number, $\frac{k+1}{2}$ is an integer, we see that since $k>1,$ then $\frac{1}{k},$ is not an integer. Thus this sequence is a good sequence.
03.11.2024 19:24
alexanderhamilton124 wrote: part (a) is like 3 marks and n = 4 can give max 1 mark so you should expect <= 4 marks And what do you think for question 5?
03.11.2024 23:33
Determinant_is_Volume wrote: In Q5 I assumed (but couldn’t prove) $\triangle OBD\sim\triangle OLP$, where P is the midpoint of BC. Then OB/OD=OL/LP which means OB*LP=OL*BD which in turn means OB*(AB+CD)/2=OL*(AC+BD)/2. I wrote all required explanations and drew a pretty nice figure I think. maybe 7-8? you should ask someone more experienced on this matter since this is like my 2nd time doing oly
04.11.2024 16:45
I did the second part but I think my explaination wasn't perfect. I first proved that if $ n$ is even then a nice arrangment exists. $\because$ when $k$ is odd it is not possible to keep them arrangened in the real pattern like $1,2,3,4.......n.$ All I need is to disturb this sequence for odd numbers and let it be same for even places. So we will shift all the numbers at odd places to the even places. So the sum till odd places is disturbed but sum for all the even places remains the same. Hence the nice arrangment is $1,2,4,3,6,5,8,7.........$. I gave this sequence but I mentioned that two nice arrangments exist and mentioned this $2,1,4,3,6,5,8,7.........$ at last. Can anyone tell how much marks can I get in this?
05.11.2024 11:19
just k = n for first part induct for second boom 17 marks
05.11.2024 12:59
$OG!$ I will try to write as far as I remember the exact same quotation as I did in the contest $(a)$ Assume for the sake of contradiction that there exists a nice rearrangement $a_1 \cdots a_n$ if $n$ is odd. Now since, $a_1 \cdots a_n$ is a rearrangement of $1,2 \cdots n$, we find $a_1+ \cdots +a_n =1+2 \cdots +n=\frac{n(n+1)}{2}$ Now observe that $n|a_1+ \cdots +a_n= \frac{n(n+1)}{2} \iff 2n|n(n+1) \iff 2|n+1$ which is true as $n$ is odd, so $n+1$ is even Hence, a contradiction, so we are done. $(b)$ We claim the construction $2,1,4,3,6,5,7,6... 2n,2n+1$ is a nice rearrangement where $a_n = n+1$ if $n$ is odd. $a_n = n-1$ if $n$ is even. Proof: Case1: $n$ is even set $n=2k$. Then we observe that the sequence ${a_1 \cdots a_{2k}}$ is a permutation of ${1 \cdots 2k}$ Thus, $a_1+ \cdots +a_{2k}= 1+ \cdots+ 2k = \frac{2k(2k+1)}{2}$ Now assume for the sake of contradiction that $n=2k| a_1+.....a_n=a_1+ \cdots +a_{2k}= 1+ \cdots+ 2k = \frac{2k(2k+1)}{2}$ $\implies 2k|\frac{2k(2k+1)}{2} \implies 2|2k+1 \implies 2|1$. A contradiction! Case2: $n$ is odd set $n=2k+1$. Then, by our sequence ${a_1 \cdots a_{2k+1}}$ is ${2,1\cdots 2k-2,2k-3,2k-1,2k,2k+2}$ Thus, $a_1+ \cdots +a_{2k+1}= 1+ \cdots+ 2k + 2k+2 = \frac{2k(2k+1)}{2} +2k+2 = k(2k+1)+2k+2 k$ Now assume for the sake of contradiction that $n=2k+1| a_1+.....a_n=a_1+ \cdots +a_{2k+1}= k(2k+1)+2k+2 $ $\implies 2k+1|k(2k+1)+2k+2 \implies 2k+1|2k+2 =(2k+1)+1\implies 2k+1|1$. So $2k+1= 1$ or $-1$, but since $n=2k+1 \in {2,3 \cdots n}$ This is a contradiction! Hence, done
23.11.2024 22:53
a) The problem is trivial. Simply add the numbers from \(1\) to \(n\), and observe that \(2\) divides \(n+1\). Hence, the result follows. b) To construct the sequence, I'll explain my intuition: Initially, I tried placing all the odd numbers first, followed by all the even numbers. However, this approach doesn't work because \(1 + (\text{any odd number})\) results in an even number, which is divisible by \(2\). Thus, \(1\) must be followed by either \(2\) or another even number. The best guess was \(2\). Through some trial and error, I arrived at the following construction: \[ a_n = \begin{cases} n + 1 & \text{if } n \text{ is odd}, \\ n - 1 & \text{if } n \text{ is even}. \end{cases} \] This construction can be proven by induction:
13.12.2024 13:24
how to prove the b part with induction??
18.01.2025 11:19
(a) Taking $n=k$, so \[\sum_{i=1}^{k}a_{k}=\frac{n(n+1)}{2}\]which is divisible by $n$ for odd $n$. Hence there is no nice arrangement. (b) Take $n=2a$, then we show that the sequence \[2,1,4,3,\dotsc, 2a,2a-1\]works. If $k$ is even then \[k\nmid \sum_{i=1}^{k}a_{i}=\frac{k(k+1)}{2}\]If $k$ is odd then \[k\nmid \sum_{i=1}^{k}a_{i}=\frac{k(k-1)}{2}+k+1\]for $k>1$. Thus the sequence is a nice arrangement.