$N$ in natural. There are natural numbers from $N^3$ to $N^3+N$ on the board. $a$ numbers was colored in red, $b$ numbers was colored in blue. Sum of red numbers in divisible by sum of blue numbers. Prove, that $b|a$
Problem
Source: St Petersburg Olympiad 2014, Grade 11, P3
Tags: number theory, combinatorics, algebra, inequalities
programjames1
24.10.2017 17:53
Let $a_1,a_2,a_3,\dots,a_a;b_1,b_2,b_3\dots,b_b$ be $N^3$ less than each of the numbers.
Then, we are given $bN^3+b_1+b_2+\dots+b_b|aN^3+a_1+a_2+\dots+a_a$. Also, we know that $$a_1+a_2+\dots+a_a+b_1+b_2+\dots+b_b=\frac{N(N+1)}2\Longrightarrow bN^3+b_1+b_2+\dots+b_b|aN^3+\frac{N(N+1)}2-(b_1+b_2+\dots+b_b)$$$$\Longrightarrow bN^3+b_1+b_2+\dots+b_b|(a+b)N^3+\frac{N(N+1)}2=(N+1)N^3+\frac{N(N+1)}2=N(N+1)(N^2+\frac12)$$So, the sum of the $b$ numbers, $S_b$ for short, is $1,N,N+1,N^2+N,N^4+N^3+\frac{N^2+N}2$ or, for even $N$, $N^3+\frac{N}2$. It is easy to show, that unless $N=0,1$ $S_b$ is too small to be $1,N,N+1,$ and $N^2+N$. Checking $N=0$, we find that $S_b=0$, but the pair $(a,b)=(0,1)$ does not work, so for this problem, I am assuming the definition of the natural numbers to be all positive integers, allowing us to throw out $N=0$. Checking $N=1$, it is easy to see that for the cases $1,N,N+1,$ and $N^2+N$, $b=a=1$ so $b|a$.
So, we are left with $S_b=N^4+N^3+\frac{N^2+N}2$ or $N^3+\frac{N}2$. $N^4+N^3+\frac{N^2+N}2$ is just the sum of all the numbers on the board, so $a=0$ and $b|a$. For the second, we see that $b=1$, because $N^3>\frac{N}2\ \forall\ N\in \mathbb{N}$. So, $b|a$. $\blacksquare$
RagvaloD
24.10.2017 17:59
$a+b$ not is nessesary equal $N$.
programjames1
24.10.2017 18:01
I put $a+b=N+1$, because there are $N+1$ numbers between $N^3$ and $N^3+N$ inclusive.
test20
24.10.2017 18:05
But some of the numbers may remain uncolored: The blackboard contains the integers from $N^3$ to $N^3+N$, where $N\ge1$ is an integer. Exactly $r$ of these numbers are colored red, exactly $b$ of these numbers are colored blue, while the remaining numbers are left uncolored. If the sum of the red numbers is a multiple of the sum of the blue numbers, prove that $r$ is a multiple of $b$.
programjames1
24.10.2017 18:07
In that case, I don't know what to do.
cooljoseph
24.10.2017 18:29
I'm getting the inequality $\frac{a}{b}\geq \frac{aN^3+S_a}{bN^3+S_b}>\frac{a}{b+1}$. I don't know where to go from there.
programjames1
24.10.2017 18:50
Is $S_a$ the sum of all $a_1,a_2,\dots,a_a$ (from my post), or the sum of all $a$ colored integers?
dgrozev
25.10.2017 13:56
I prefer the number of red numbers to be denoted by $r$ and the number blue ones - by $b$. Let $\sum_r$ be the sum of red numbers and $\sum_b$ - the sum of blue numbers. We have: \[rN^3 \leq \sum_r \leq r(N^3+N)\]\[bN^3 \leq \sum_b \leq b(N^3+N)\] It yields: $$\frac{rN^3}{b(N^3+N)}\leq \frac{\sum_r}{\sum_b}\leq \frac{r(N^3+N)}{bN^3}$$Since $r/b \in [1/N, N]$ it easily follows: $$ \frac{r}{b}-\frac{1}{N} \leq \frac{\sum_r}{\sum_b}\leq \frac{r}{b}+\frac{1}{N} $$ Since $1\leq r,b\leq N$, if $\frac{\sum_r}{\sum_b}$ is a natural number, it easily follows $r/b$ is also a natural number.
Jjesus
27.05.2023 22:59
dgrozev wrote: Since $1\leq r,b\leq N$, if $\frac{\sum_r}{\sum_b}$ is a natural number, it easily follows $r/b$ is also a natural number. Why??
dgrozev
06.06.2023 20:01
I commented on this in a bit more detail on my blog