two sequences of positive integers and inequalities

The post below has been deleted. Click to close.

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

rmtf1111

698 posts

rmtf1111

#1 h Apr 10, 2019, 11:12 AM • 5 Y

Y by Resolut1on07, Adventure10, Mango247, anantmudgal09, cubres

Let $n\ge 2$ be an integer, and let $a_1, a_2, \cdots , a_n$ be positive integers. Show that there exist positive integers $b_1, b_2, \cdots, b_n$ satisfying the following three conditions:

$\text{(A)} \ a_i\le b_i$ for $i=1, 2, \cdots , n;$

$\text{(B)} \$ the remainders of $b_1, b_2, \cdots, b_n$ on division by $n$ are pairwise different; and

$\text{(C)} \$ $b_1+b_2+\cdots b_n \le n\left(\frac{n-1}{2}+\left\lfloor \frac{a_1+a_2+\cdots a_n}{n}\right \rfloor \right)$

(Here, $\lfloor x \rfloor$ denotes the integer part of real number $x$ , that is, the largest integer that does not exceed $x$ .)

This post has been edited 1 time. Last edited by darij grinberg, Nov 28, 2020, 5:26 PM
Reason: typo

Z K Y

The post below has been deleted. Click to close.

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

62861

3564 posts

62861

#2 h Apr 10, 2019, 11:34 AM • 7 Y

Y by BobaFett101, Illuzion, star32, Aniruddha07, IAmTheHazard, aopsuser305, Adventure10

Solution

Z K Y

The post below has been deleted. Click to close.

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

juckter

322 posts

juckter

#3 h Apr 10, 2019, 11:48 AM • 4 Y

Y by star32, Illuzion, trololo23, Adventure10

Let $r = (a_1 + a_2 + \dots + a_n) \pmod{n}$ , and let $d_i = b_i - a_i$ . Then we have

$b_1 + b_2 + \dots + b_n \leq n\left(\frac{n - 1}{2} + \frac{a_1 + a_2 + \dots + a_n - r}{n}\right)$ $\iff$ $d_1 + d_2 + \dots + d_n = (b_1 - a_1) + \dots + (b_n - a_n) \leq \frac{n(n - 1)}{2} - r$
So now we can see the problem as follows: We have a vector $(a_1, a_2, \dots, a_n)$ in $\mathbb{Z}_n^n$ and we're allowed to make a move that adds $1$ to one of the coordinates. We want to prove that we can make all the coordinates distinct in at most $\frac{n(n - 1)}{2} - r$ moves. Notice that a trivial way to attain this is to fix a vector $v = (v_1, v_2, \dots, v_n)$ with all distinct coordinates and gradually transform $a_i$ into $v_i$ . Consider doing this for all $n$ choices of $v$ which are rotations of $(0, 1, 2, \dots, n - 1)$ . By looking at the moves that we perform at each coordinate we can see that we perform

$n\left(\frac{n(n - 1)}{2}\right)$
Moves in total, so one of these rotations uses at most $\frac{n(n - 1)}{2}$ moves. But by considering the sum modulo $n$ we see that every valid sequence must use a number of moves congruent to $\frac{n(n - 1)}{2} - r \pmod{n}$ , since at the end the sum is $0 + 1 + \dots + n - 1 \equiv \frac{n(n - 1)}{2} \pmod{n}$ and at the start it is $r$ . So this choice in fact uses at most $\frac{n(n - 1)}{2} - r$ moves, as desired.

Z K Y

The post below has been deleted. Click to close.

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

Sepled

10 posts

Sepled

#4 h Apr 10, 2019, 11:56 AM • 6 Y

Y by MazeaLarius, BG71, MathbugAOPS, star32, Adventure10, Mango247

The key idea is quite simple.
Solution

This post has been edited 2 times. Last edited by Sepled, Apr 10, 2019, 12:01 PM

Z K Y

The post below has been deleted. Click to close.

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

v_Enhance

6865 posts

v_Enhance

#5 h Apr 10, 2019, 12:28 PM • 12 Y

Y by Assassino9931, Math-Ninja, MihaiT, MathbugAOPS, star32, v4913, MrOreoJuice, PIartist, sabkx, Adventure10, vrondoS, MS_asdfgzxcvb

Cute/fun problem. (But not really number theory.)

Note that if $a_i > n$ , we can replace $a_i$ with $a_i-n$ and $b_i$ with $b_i-n$ , and nothing changes. So we may as well assume $a_i \in \{1, \dots, n\}$ for each $i$ .

Pick a uniformly random permutation $\sigma$ on $\{1, \dots, n\}$ and define $b^\sigma_i = \begin{cases} n + \sigma(i) & a_i > \sigma(i) \\ \sigma(i) & \text{otherwise}. \end{cases}$ In that case, $\sum_i b^\sigma_i = (1+\dots+n) + n e_\sigma$ , where $e_\sigma$ is the number of indices $i$ with $a_i > \sigma(i)$ . Note that $\mathbb E[e_\sigma] = \sum_{i=1}^n \frac{a_i-1}{n}$ by linearity of expectation.

Thus there is some choice of $\sigma$ with $e_\sigma \le \left\lfloor \sum_i \frac{a_i-1}{n} \right\rfloor$ and that choice works.

This post has been edited 2 times. Last edited by v_Enhance, Apr 10, 2019, 2:40 PM

Z K Y

The post below has been deleted. Click to close.

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

ubermensch

820 posts

ubermensch

#6 h Apr 10, 2019, 2:20 PM • 2 Y

Y by Adventure10, Mango247

Wow this was a not too complicated but yet nice problem... who proposed this?

This post has been edited 1 time. Last edited by ubermensch, Apr 10, 2019, 2:21 PM

Z K Y

The post below has been deleted. Click to close.

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

prague123

230 posts

prague123

#7 h Apr 10, 2019, 2:37 PM • 1 Y

Y by Adventure10

v_Enhance wrote:

Thus there is some choice of $\sigma$ with $e_\sigma < \left\lfloor \sum_i \frac{a_i-1}{n} \right\rfloor$ and that choice works.

This statement definitely need a proof. In particular, it needs a proof for cases like $a_1=a_2=\cdots=a_n=1$ , and for other cases where the righthand side is 0.

Z K Y

The post below has been deleted. Click to close.

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

prague123

230 posts

prague123

#8 h Apr 10, 2019, 2:40 PM • 2 Y

Y by Adventure10, Mango247

ubermensch wrote:

Wow this was a not too complicated but yet nice problem... who proposed this?

I have heard that is has been proposed by Poland but I do not know the author.

Z K Y

The post below has been deleted. Click to close.

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

v_Enhance

6865 posts

v_Enhance

#9 h Apr 10, 2019, 2:40 PM • 3 Y

Y by v4913, Adventure10, Mango247

prague123 wrote:

v_Enhance wrote:

Thus there is some choice of $\sigma$ with $e_\sigma < \left\lfloor \sum_i \frac{a_i-1}{n} \right\rfloor$ and that choice works.

This statement definitely need a proof. In particular, it needs a proof for cases like $a_1=a_2=\cdots=a_n=1$ , and for other cases where the righthand side is 0.

Typo, I meant $\le$ there.

Z K Y

The post below has been deleted. Click to close.

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

hwl0304

1840 posts

hwl0304

#10 h Apr 10, 2019, 7:48 PM • 2 Y

Y by Adventure10, Mango247

First, zero-index the sequences (i.e. so they are $a_0,\ldots, a_{n-1}$ and $b_0,\ldots b_{n-1}$ ). Moreover, we prove the general case where $a_i,b_i$ are nonnegative.

Note that if the problem holds for some $a_i$ , we can perform the following invertible operations to prove it for a modified $a_i$ :
- We can sort/reorder the $a_i$ by symmetry.
- We can add/subtract $1$ from each $a_i$ and $b_i$ - this increases/decreases each side of the inequality in $C$ by $n$ , and maintains everything else.
- We can add/subtract $n$ from one of the $a_i$ and $b_i$ - similar reason.

Claim: We can modify any $a_i$ such that $a_i\le i$ for all $0\le i\le n-1$ . This clearly solves the problem, as we can just set $b_i=i$ for all $0\le i\le n-1$ , then invert the process (sidenote: this appears wrong because it gives the bound $\le n(n-1)/2$ , but the transformation utilizes the "breathing space").

First, we can force everything to be $\le n-1$ by subtracting by the appropriate factors of $n$ . Moreover, we can sort the integers and shift down accordingly so that $0=a_0\le a_1\le \ldots\le a_{n-1}\le n-1$ .

Now, consider the following process, assuming that there exists $a_i>i$ . We claim that $\sum_{k=0}^{n-1}a_k-k$ is strictly decreasing.

Let $i$ be the minimum number such that $a_{i}>i$ (note $i\neq 0$ ). Shift the subsequence $a_0,\ldots, a_{i-1}$ to the right by $n-i$ , then add $n$ , such that the new sequence is $a_i, a_{i+1},\ldots, a_{n-1}, a_{0}+n, a_{1}+n, \ldots, a_{i-1}+n$ .

Redefining the indices, we can see that $a_k-k$ has now increased by $i$ for each $k$ , because if originally $k\ge i$ , then $k$ had been shifted to the left by $i$ , and if originally $k<i$ , then $k$ had been shifted to the right by $n-i$ but $a_k$ had been increased by $n$ . Thus, the sum has increased by $in$ .

Now, we subtract what was originally $a_i>i$ from every index. This decreases the sum by $a_in$ . Thus, each step of this process decreases the desired sum by $n(a_i-i)$ , while maintaining the fact that the numbers are between $0$ and $n-1$ .

Assuming that the process can be carried out infinitely, $\sum_{k=0}^{n-1}a_k-k$ is eventually small enough so that we force one of $a_i$ to be negative, contradiction. Thus, the process must eventually stop, so that $a_i\le i$ for all $i$ , as desired.

Z K Y

The post below has been deleted. Click to close.

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

Morskow

46 posts

Morskow

#11 h Apr 11, 2019, 9:37 AM • 7 Y

Y by JANMATH111, MazeaLarius, anser, Illuzion, Infinityfun, Adventure10, Mango247

First, construct the $b_i$ one after the other as follows: Let $b_i\in \{a_i, a_i+1, \ldots, a_i+(i-1)\}$ such that the remainder of $b_i$ modulo $n$ is not equal to any remainder of the previously constructed $b_1, b_2, \ldots, b_{i-1}$ (pigeonhole principle forces this to work). If there are multiple choices, pick arbitrarily.

We claim the constructed set satisfies the conditions of the problem. Indeed, for all $i$ , define $c_i=b_i-(i-1)$ . By our construction, $c_i\leq a_i$ and $n\;|\;c_1+c_2+\ldots+c_n$ , therefore

$\begin{align*} b_1+b_2+\ldots+b_n&=c_1+c_2+\ldots+c_n+\frac{n(n-1)}{2}\\ &=n\left(\frac{n-1}{2}+\left\lfloor\frac{c_1+c_2+\ldots+c_n}{n}\right\rfloor\right)\\ &\leq n\left(\frac{n-1}{2}+\left\lfloor\frac{a_1+a_2+\ldots+a_n}{n}\right\rfloor\right), \end{align*}$
as desired.

Z K Y

The post below has been deleted. Click to close.

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

v_Enhance

6865 posts

v_Enhance

#12 h Apr 11, 2019, 11:42 PM • 5 Y

Y by Polynom_Efendi, v4913, Adventure10, Mango247, tediousbear

Here is the same solution I posted earlier, but phrased in a way that I think is more natural (albeit longer), and also how I actually thought about the problem when I was solving it. Hopefully more instructive.

Note that if $a_i > n$ , we can replace $a_i$ with $a_i-n$ and $b_i$ with $b_i-n$ , and nothing changes. So we may as well assume $a_i \in \{1, \dots, n\}$ for each $i$ .

We choose our $b_i$ 's in the following way. Draw an $n \times n$ grid and in the $i$ th column fill in the bottom $a_i-1$ cells red. We can select $b_i$ by marking $n$ cells, one in each row or column. If we chose $j$ th lowest row in the $i$ th column, then we would set $b_i = j$ on non-red cells and $b_i = j + n$ on red cells.

In this way, define the penalty $p$ as the number of selected cells which are red. Then $b_1 + \dots + b_n = (1+2+\dots+n) + n \cdot p = n \cdot \frac{n-1}{2} + n \cdot (p-1).$ and we seek to minimize the penalty $p$ .

$[asy]defaultpen(fontsize(8pt)); size(8cm); fill( (1,0)--(1,2)--(2,2)--(2,3)--(4,3)--(4,4)--(5,4)--(5,0)--cycle, palered); for (int i=0; i<=5; ++i) { draw((i,0)--(i,5), grey); draw((0,i)--(5,i), grey); } draw(scale(5)*unitsquare); label("$b_i \equiv 1 \pmod 5$", (0,0.5), dir(180), lightblue); label("$b_i \equiv 2 \pmod 5$", (0,1.5), dir(180), lightblue); label("$b_i \equiv 3 \pmod 5$", (0,2.5), dir(180), lightblue); label("$b_i \equiv 4 \pmod 5$", (0,3.5), dir(180), lightblue); label("$b_i \equiv 5 \pmod 5$", (0,4.5), dir(180), lightblue); label("$a_1-1$", (0.5,0), dir(-90), lightred); label("$a_2-1$", (1.5,0), dir(-90), lightred); label("$a_3-1$", (2.5,0), dir(-90), lightred); label("$a_4-1$", (3.5,0), dir(-90), lightred); label("$a_5-1$", (4.5,0), dir(-90), lightred); label("$b_1$", (0.5, 3.5), blue); label("$b_2$", (1.5, 2.5), blue); label("$b_3$", (2.5, 4.5), blue); label("$b_4$", (3.5, 0.5), blue); label("$b_5$", (4.5, 1.5), blue); [/asy]$

But the expected penalty of a random permutation is the red area divided by $n$ , which is $\mathbb E[p] = \frac{(a_1-1) + \dots + (a_n-1)}{n}$ and so there exists a choice for which the penalty is at most $\lfloor \mathbb E[p] \rfloor$ . This gives the required result.

This post has been edited 3 times. Last edited by v_Enhance, Apr 12, 2019, 12:41 PM

Z K Y

The post below has been deleted. Click to close.

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

yayups

1614 posts

yayups

#13 h May 19, 2019, 6:03 PM • 1 Y

Y by Adventure10

Let $x_i=b_i-a_i$ . We want $\{x_i+a_i\}$ to be a complete residue system modulo $n$ . To this end, pick a uniformly random permutation
$\sigma:[n]\to\mathbb{Z}/n\mathbb{Z},$ and pick $x_i$ to be the smallest non-negative number such that $x_i+a_i\equiv \sigma(i)\pmod{n}$ . We see that $x_i$ has an equal chance to be any of $0,\ldots,n-1$ , so
$\mathbb{E}(x_i)=\frac{n-1}{2}.$ Thus,
$\mathbb{E}(x_1+\cdots+x_n)=\frac{n(n-1)}{2},$ so there exists a valid choice of the $x_i$ s such that
$x_1+\cdots+x_n\le\frac{n(n-1)}{2}.$ However, we have that
$\sum a_i+\sum x_i\equiv 0+\cdots+(n-1)=\frac{n(n-1)}{2}\pmod{n},$ so $\sum x_i=\frac{n(n-1)}{2}-\left(\sum a_i\pmod{n}\right)+kn$ for some integer $k$ . Thus, we see that in fact, the $x_i$ s we chose must further satisfy
$\sum x_i\le \frac{n(n-1)}{2}-\left(\sum a_i\pmod{n}\right).$ Adding $\sum a_i$ to both sides yields the desired conclusion.

Z K Y

The post below has been deleted. Click to close.

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

spartacle

538 posts

spartacle

#15 h May 31, 2019, 6:31 PM • 3 Y

Y by Assassino9931, tapir1729, Adventure10

Relabel $a_n, b_n$ as $a_0, b_0$ . WLOG $0 \le a_i \le n-1$ for all $i$ , and further WLOG $a_0 \le a_1 \le \ldots \le a_{n-1}$ .

We use a simple greedy algorithm. For $0 \le i \le n-1$ , select $b_i$ to be the smallest number such that $b_i \ge a_i$ and $b_i \not \equiv b_{i-1}, \ldots, b_0$ . Since only $i$ of the $b_j$ have been selected already, clearly we will have $b_i \le a_i + i$ . Summing this across all $i$ , we have $b_0 + b_1 + \ldots b_{n-1} \le a_1 + a_2 + \ldots + a_{n-1} + 1 + 2 + \ldots + n-1$ , which is almost (but not quite) what we want.

However, we can do better. Since $b_0, \ldots, b_{n-1}$ is a permutation of $0, \ldots, n-1 \pmod{n}$ , $b_0 + \ldots + b_{n-1} - 0 - 1 - \ldots - {n-1}$ is a multiple of $n$ . So in fact this quantity is less than or equal to the largest multiple of $n$ which is $\le a_0 + \ldots + a_{n-1}$ , i.e. $n\left \lfloor \frac{a_0 + \ldots + a_{n-1}}{n} \right \rfloor$ . Hence
$b_0 + \ldots + b_{n-1} - 0 - 1 - \ldots - {n-1} \le n\left \lfloor \frac{a_0 + \ldots + a_{n-1}}{n} \right \rfloor \implies b_0 + \ldots + b_{n-1} \le n\left( \frac{n-1}{2} + \left \lfloor \frac{a_0 + \ldots + a_{n-1}}{n} \right \rfloor \right)$ so we are done.

Z K Y

The post below has been deleted. Click to close.

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

GeronimoStilton

1521 posts

GeronimoStilton

#16 h Aug 22, 2019, 9:28 PM • 2 Y

Y by Adventure10, Mango247

For each $a_i$ , we define $x_i$ and $r_i$ such that $x_i n + r_i$ , $0 \le r_i < n$ , and $x_i$ is an integer. Consider a random permutation $\pi$ of the set $\{0, 1, \cdots , n-1\}$ . We define
$\pi(a_i) = n\left\lceil \frac{a_i - \pi(i)}{n} \right\rceil + \pi(i),$ that is, the minimal number greater than or equal to $a_i$ congruent to $\pi(i)$ modulo $n$ . Now, we consider
$\sum_{i = 1}^n \pi(a_i) = \sum_{i = 1}^n \left(n\left\lceil \frac{a_i - \pi(i)}{n} \right\rceil + \pi(i)\right) = \sum_{i = 1}^n \pi(i) + n\sum_{i = 1}^n \left\lceil \frac{a_i - \pi(i)}{n} \right\rceil =$ $\sum_{i = 0}^{n-1} i + n\sum_{i = 1}^n \left\lceil \frac{a_i - \pi(i)}{n} \right\rceil = n\left(\frac{n-1}{2} + \sum_{i = 1}^n \left\lceil \frac{a_i - \pi(i)}{n} \right\rceil\right).$ It suffices to show that there exists a permutation $\pi$ such that
$\sum_{i = 1}^n \left\lceil \frac{a_i - \pi(i)}{n} \right\rceil \le \left\lfloor \frac{\sum_{i = 1}^n a_i}{n}\right\rfloor.$ Substituting in $a_i = x_in + r_i$ , we see that it suffices to show that
$\sum_{i = 1}^n \left(x_i + \left\lceil \frac{r_i - \pi(i)}{n} \right\rceil\right) \le \sum_{i = 1}^n x_i + \left\lfloor \frac{\sum_{i = 1}^nr_i}{n}\right\rfloor,$ or equivalently,
$\sum_{1 \le i \le n, r_i > \pi(i)} 1 = \sum_{i = 1}^n \left\lceil \frac{r_i - \pi(i)}{n} \right\rceil \le \left\lfloor \frac{\sum_{i = 1}^nr_i}{n}\right\rfloor.$ Now, by the probabilistic method, it suffices to show that the expected value of $\sum_{1 \le i \le n, r_i > \pi(i)} 1$ is less than or equal to $\left\lfloor \frac{\sum_{i = 1}^nr_i}{n}\right\rfloor$ , since we will then have that such a permutation $\pi$ exists. We compute that
$\mathbb{E}\left[\sum_{1 \le i \le n, r_i > \pi(i)} 1\right] = \sum_{i=1}^n\mathbb{P}[r_i > \pi(i)] = \sum_{i=1, r_1 \ge 1}^n\frac{r_i - 1}{n} = \frac{\sum_{i=1, r_1 \ge 1}^n r_i}{n} - 1 \le$ $\left\lfloor\frac{\sum_{i=1, r_1 \ge 1}^n r_i}{n}\right\rfloor = \left\lfloor\frac{\sum_{i=1}^n r_i}{n}\right\rfloor.$ Thus, we are done by the probabilistic method. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

cj13609517288

1869 posts

cj13609517288

#38 h Dec 21, 2023, 8:06 PM

Y by

It's not hard to see by global that the statement is true if the floors weren't there(choose any construction and rotate the residues mod $n$ cyclically). The sum of the $b_i$ will then be $\frac{n(n-1)}{2}$ more than a multiple of $n$ , so the floor part follows.

This post has been edited 1 time. Last edited by cj13609517288, Dec 21, 2023, 8:07 PM

Z K Y

The post below has been deleted. Click to close.

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

Aaryabhatta1

1631 posts

Aaryabhatta1

#39 h Dec 22, 2023, 12:47 AM

Y by

Consider choosing $b_i \in \{a_i, a_i + 1, \dots, a_i + (n-1)\}.$ Observe that all possible residues $\pmod{n}$ are encompassed uniquely in the intervals. If we select $(b_1, b_2, \dots, b_n)$ to have residues a permutation of $\{0, 1, \dots, n-1\}$ and assign $b_i$ to the corresponding value in the interval we satisfy conditions $(1), (2).$

The expected value of $b_i - a_i$ is $\frac{n-1}{2}$ since $b_i$ has equal probability of being any residue. Therefore the expected value of $\frac{1}{n}(\sum_{i = 1}^{n} b_i - a_i) = \frac{n-1}{2}$ by LoE. By Pigeonhole Principle, there must exist a tuple $(b_1, b_2, \dots, b_n)$ satisfying,
$\begin{align*} \frac{1}{n} (\sum_{i = 1}^{n} b_i - a_i) &\le \frac{n-1}{2} \\ \frac{1}{n}(b_1 + b_2 + \cdots+ b_n) &\le (\frac{n-1}{2} + \frac{1}{n}(a_1 + a_2 + \cdots + a_n)). \end{align*}$ Observe that $\frac{1}{n}\sum_{i = 1}^{n} b_i - \frac{(n-1)}{2} \equiv \frac{1}{n} \frac{n(n-1)}{2} - \frac{n-1}{2} \equiv 0 \pmod{n}$ hence we conclude,
$(b_1 + b_2 + \cdots+ b_n) \le n(\frac{n-1}{2} + \lfloor \frac{a_1 + a_2 + \cdots + a_n}{n} \rfloor).$

This post has been edited 1 time. Last edited by Aaryabhatta1, Dec 22, 2023, 12:48 AM

Z K Y

The post below has been deleted. Click to close.

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

mannshah1211

651 posts

mannshah1211

#40 h Jan 4, 2024, 6:42 PM

Y by

Let us assume $b_i = q_i \cdot n + r_i,$ with $r$ being a permutation of $\{0, 1, \dots, n - 1 \}$ , so that $r_1 + r_2 + \dots + r_n = \frac{n(n - 1)}{2}$ . Then, we must have $q_1 + q_2 + \cdots + q_n \le \left \lfloor \frac{a_1 + a_2 + \dots + a_n}{n} \right \rfloor,$ and also for the second condition, we must have $a_i \le q_i \cdot n + r_i,$ or $\left \lceil \frac{a_i - r_i}{n} \right \rceil \le q_i,$ or $\left \lfloor \frac{a_i - r_i + n - 1}{n} \right \rfloor \le q_i,$ but if $r_i$ is a permutation of $\{0, 1, \dots, n - 1 \}$ , $n - 1 - r_i$ is a permutation also, so call this $p$ . So, we write this compactly as $q_i \ge \frac{a_i + p_i}{n}$ and our earlier condition doesn't change, just that $r$ is replaced by $p$ so it suffices to show that there exists some permutation $p$ of $\{0, 1, \dots, n - 1\}$ with $\left \lfloor \frac{a_1 + p_1}{n} \right \rfloor + \left \lfloor \frac{a_2 + p_2}{n} \right \rfloor + \dots + \left \lfloor \frac{a_n + p_n}{n} \right \rfloor \le \left \lfloor \frac{a_1 + a_2 + \dots + a_n}{n} \right \rfloor.$ Now, consider the expected value of above expression over all possible $p$ . By LoE, it is just $\frac{\left \lfloor \frac{a_1}{n} \right \rfloor + \left \lfloor \frac{a_1 + 1}{n} \right \rfloor + \dots + \left \lfloor \frac{a_1 + n - 1}{n} \right \rfloor}{n} + \frac{\left \lfloor \frac{a_2}{n} \right \rfloor + \left \lfloor \frac{a_2 + 1}{n} \right \rfloor + \dots + \left \lfloor \frac{a_2 + n - 1}{n} \right \rfloor}{n} + \dots + \frac{\left \lfloor \frac{a_n}{n} \right \rfloor + \left \lfloor \frac{a_n + 1}{n} \right \rfloor + \dots + \left \lfloor \frac{a_n + n - 1}{n} \right \rfloor}{n}.$ But, by Hermite identity, we have $\left \lfloor \frac{a_i}{n} \right \rfloor + \left \lfloor \frac{a_i + 1}{n} \right \rfloor + \dots + \left \lfloor \frac{a_i + n - 1}{n} \right \rfloor = a_i,$ for any $i$ . So, the expected value is $\frac{a_1 + a_2 + \dots + a_n}{n},$ but since the above quantity can only be an integer, it follows that there exists some such permutation with it not exceeding $\left \lfloor \frac{a_1 + a_2 + \dots + a_n}{n} \right \rfloor$ .

This post has been edited 1 time. Last edited by mannshah1211, Jan 4, 2024, 6:44 PM
Reason: \left \right

Z K Y

The post below has been deleted. Click to close.

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

RedFireTruck

4220 posts

RedFireTruck

#41 h Jan 26, 2024, 4:35 AM

Y by

Since subtracting $n$ from $a_i$ and $b_i$ for some $i$ keeps a, b, and c true, we can assume that $0\le a_i < n$ WLOG. For some $i$ , let $b_i\mod n = x$ . Then, $a_i > x$ with probability $\frac{a_i}{n}$ . If $a_i>x$ then $b_i=x$ works, otherwise $b_i=x+n$ works. Notice that $b_1\mod n, b_2\mod n,\dots, b_n\mod n$ is a permutation of $0,1,\dots,n-1$ , so $\mathbb{E}[b_1+\dots+b_n]=\frac{n(n-1)}{2}+n\sum_{i=1}^{n}\frac{a_i}{n}=n(\frac{n-1}{2}+\frac{a_1+\dots+a_n}{n})$ .

Since $b_1+\dots+b_n-\frac{n(n-1)}2$ must be a multiple of $n$ , we must have that $b_1+\dots+b_n\le n(\frac{n-1}{2}+\lfloor\frac{a_1+\dots+a_n}{n}\rfloor)$ for some $b_1,\dots,b_n$ , as desired.

Z K Y

The post below has been deleted. Click to close.

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

InterLoop

250 posts

InterLoop

#42 h Apr 30, 2024, 2:34 PM • 1 Y

Y by Funcshun840

natural
solution

This post has been edited 1 time. Last edited by InterLoop, Apr 30, 2024, 2:35 PM

Z K Y

The post below has been deleted. Click to close.

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

bjump

985 posts

bjump

#43 h Jun 26, 2024, 2:49 PM

Y by

Solution

Z K Y

The post below has been deleted. Click to close.

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

Mathandski

721 posts

Mathandski

#44 h Aug 22, 2024, 12:14 AM

Y by

$\text{[math]}$

Attachments:

Z K Y

The post below has been deleted. Click to close.

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

ihategeo_1969

164 posts

ihategeo_1969

#45 h Sep 10, 2024, 5:33 PM

Y by

Assume the contrary.

Assign each $b_i$ with $\pi(i)$ where $\pi$ is a permutation of $\{1,\dots,n\}$ ; such that $b_i \equiv \pi(i) \pmod n$ . And now greedily choose $b_i$ to be the smallest number to satisfy this and the first condition of the question; and call such sequence $(b_1,\dots,b_n)$ \emph{good}.

And so for all good sequences we have that the third condition is not satisfied. And so we have $\sum_i b_i-a_i \geq \frac{n(n+1)}2-n \left \{\frac{\sum_i a_i}n \right\}$ This is because the LHS and RHS in the third condition is obviously congruent. So now, we will sum up this expression for all such good sequences.

See that for a particular $a_i$ , we have that $\sum b_i-a_i$ for different choices of $b_i$ being assigned to $1$ , $\dots$ or $n$ ; it is equal to $(n+0-a_i+\dots+n+a_i-1-a_i)+(a_i-a_i+\dots+n-1-a_i)=na_i-na_i+\frac{n(n-1)}2=\frac{n(n-1)}2$ And hence the total summation gives us $\begin{align*} &\frac{n(n-1)}2 \cdot (n-1)! \cdot n \geq n! \left(\frac{n(n+1)}2-n \left \{\frac{\sum_i a_i}n \right\} \right) \iff \left \{\frac{\sum_i a_i}n \right\} \geq 1 \end{align*}$ Which is a contradiction.

Z K Y

The post below has been deleted. Click to close.

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

Assassino9931

1198 posts

Assassino9931

#46 h Nov 5, 2024, 9:12 PM

Y by

Why so many solutions with randomness??? Childish greedy suffices, probabilistic stuff is too fancy for this problem.

For each $i$ pick the smallest possible $b_i \geq a_i$ such that the remainder $b_i \pmod n$ does not appear among those of $b_1,\ldots, b_{i-1}$ .
Then for $i$ there are at most $i-1$ forbidden remainders mod $n$ from the previous numbers, so $b_i \leq a_i + i - 1$ for all $i$ and the distinct remainders condition is satisfied. Summing yields $\sum_{i=1}^n b_i - \frac{n(n-1)}{2} \leq \sum_{i=1}^n a_i$ . The left-hand side is a multiple of $n$ (as the $b_i$ give the remainders $0,1,\ldots,n-1$ each once), so it is at most the largest multiple of $n$ not exceeding the right-hand side, i.e. $n\left\lfloor \frac{\sum_{i=1}^n a_i}{n} \right\rfloor$ and we are done.

Z K Y

The post below has been deleted. Click to close.

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

Ywgh1

136 posts

Ywgh1

#47 h Nov 8, 2024, 10:54 AM

Y by

Let $b_i-a_i=c_i$ , we know that the maximum of the sum $c_1+c_2+ \dots +c_n = \frac{n(n-1)}{2}$ . Hence we have that
$\begin{align*} b_1+b_2+\dots +b_n &= (a_1+a_2+ \dots+a_n)+ (c_1+c_2+\dots+c_n)\\ &\leq (a_1+a_2+ \dots+a_n)+ \frac{n(n-1)}{2} \end{align*}$ Now as
$b_1+b_2+\dots+b_n \equiv \frac{n(n-1)}{2}\pmod{n}$ Then we have that.
$n |b_1+b_2+\dots+b_n-\frac{n(n-1)}{2}$
Hence it can at most be the largest multiple of $n$ less than or equal to $a_1+a_2+\dots+a_n$ .

Which means it’s $n\lfloor \frac{a_1+a_2+\dots+ a_n}{n} \rfloor$ , hence we are done.

This post has been edited 17 times. Last edited by Ywgh1, Nov 9, 2024, 5:57 PM

Z K Y

The post below has been deleted. Click to close.

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

thdnder

194 posts

thdnder

#48 h Nov 16, 2024, 4:35 PM

Y by

Nice problem!

Obviously, we can pick non-negative integers $x_1, x_2, \dots, x_n$ such that the set $\{a_1 + x_1, a_2 + x_2, \dots, a_n + x_n\}$ is a complete residue system modulo $n$ . Let $y_i$ be the number of times $i$ appears on the set $\{x_1, x_2, \dots, x_n\}$ . (We can make sure that $0 \le x_1, x_2, \dots, x_n \le n - 1$ .) Then after adding $k$ on each term of the set $\{x_1, x_2, \dots, x_n\}$ and taking modulo $n$ , we see that the sum of our set will become $S_k = \sum_{i=0}^{n-1-k} (i + k)y_i + \sum_{i=n-k}^{n-1} (i + k - n)y_i$ , and note that $\sum_{k=0}^{n-1} S_k = \sum_{i=0}^{n-1} y_i(i + (i+1) + \dots + (n-1) + 0 + 1 + \dots + (i-1)) = \frac{n(n-1)}{2}\sum_{i=0}^{n-1} y_i = \frac{n^2(n-1)}{2}$ . Therefore, by pigeonhole principle, we can choose $k$ such that the sum of the set $\{x_1 + k, x_2 + k, \dots, x_n + k\} (n)$ is less or equal to $\frac{n(n-1)}{2}$ . Let $z_i$ be the remainder of $x_i + k$ upon division by $n$ , and let $r$ be the remainder of $a_1 + a_2 + \dots + a_n$ when divided by $n$ . Then, since $\{a_1 + z_1, a_2 + z_2, \dots, a_n + z_n\}$ is a complete residue system module $n$ , we have $(a_1 + z_1) + (a_2 + z_2) + \dots + (a_n + z_n) \equiv \frac{n(n-1)}{2} (n)$ . $\implies z_1 + z_2 + \dots + z_n \equiv \frac{n(n-1)}{2} - r (n)$ . Since $z_1 + z_2 + \dots + z_n \le \frac{n(n-1)}{2}$ , we get that $z_1 + z_2 + \dots + z_n \le \frac{n(n-1)}{2} - r$ .

Hence, if we set $b_i = a_i + z_i$ , we deduce that $b_1 + b_2 + \dots + b_n = (a_1 + a_2 + \dots + a_n) + (z_1 + z_2 + \dots + z_n) \le \frac{n(n-1)}{2} - r + (a_1 + a_2 + \dots + a_n) = n(\frac{n-1}{2} + \left\lfloor \frac{a_1 + a_2 + \dots + a_n}{n} \right\rfloor)$ , as desired. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

onyqz

195 posts

onyqz

#49 h Jan 7, 2025, 11:03 AM

Y by

wanted greedy, ended up with expected value
solution

Z K Y

The post below has been deleted. Click to close.

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

mariairam

5 posts

mariairam

#50 h Jan 24, 2025, 12:17 PM

Y by

No expected value, just some quick and nice observations with residues.

Lemma: There exist positive integers $c_1,c_2,...,c_n\in\{0,1,2,...,n-1\}$ such that $a_i+c_i \neq a_j+c_j$ (mod $n$ ) $\forall i\neq j$ and $\displaystyle\sum_{i=1}^{n}c_i\le\frac{n(n-1)}{2}$ .

Proof: Obviously, $\{a,a+1,...,a+n-1\}=\{0,1,...,n-1\}$ (mod $n$ ). Now, for each $i=\overline{1,n-1}$ look at $A_i=\{a_i,a_i+1,...,a_i+n-1\}$ and order its elements in ascending order mod $n$ . We can create $n!$ sets that contain $n$ elements, one from each $A_i$ such that no 2 elements are on corresponding positions in their respective $A_i$ and $A_j$ sets. For each such set, we can associate the sum of its elements minus $\displaystyle\sum_{i=1}^{n}a_i$ : call it $s_i\forall i=\overline{1,n!}$ . We get that $\displaystyle\sum_{i=1}^{n!}s_i=n!\cdot\frac{n(n-1)}{2}$ and by PHP, there is $s_i\le\frac{n(n-1)}{2}$ . This means that there is a set $C=\{a_j+c_j|c_j\in\{0,...,n-1\}\forall j\overline{1,n-1}\}$ with the desired properties.

We carry on with the problem. Let $b_i=a_i+c_i$ . The first $2$ conditions clearly hold, so all that remains is to show that the third one is true as well. Let $\displaystyle\sum_{i=1}^{n}a_i=cn+r$ , with $r\le n-1$ . Obviously, $\displaystyle\sum_{i=1}^{n}(a_i+c_i)=\frac{n(n-1)}{2}$ (mod $n$ ), so $\displaystyle\sum_{i=1}^{n}c_i=\frac{n(n-1)}{2}-r$ (mod $n$ ), meaning that $\displaystyle\sum_{i=1}^{n}c_i\le\frac{n(n-1)}{2}-r$ (assuming the contrary quickly leads to a contradiction). We now wish to prove that $\displaystyle\sum_{i=1}^{n}(a_i+c_i)\le \frac{n(n-1)}{2}+\bigg\lfloor\frac{\displaystyle\sum_{i=1}^{n}a_i}{n}\bigg\rfloor$ . Since the $LHS\le nc+r+\frac{n(n-1)}{2}-r=RHS$ we are done.

Z K Y

The post below has been deleted. Click to close.

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

Avron

19 posts

Avron

#51 h Mar 4, 2025, 8:02 PM

Y by

Clearly we can assume that $0 \leq a_i \leq n-1$ .

Order of $(a_n)$ does not matter so sort it non-decreasing. Let $S=\left\lfloor\frac{\sum_{i=1}^n a_i}{n}\right\rfloor$ . We'll prove that $S+k-1 \geq a_k$ for each $k$ . Note that

$S=\left\lfloor\frac{\sum_{i=1}^{k-1} a_i+\sum_{i=k}^n a_i}{n}\right\rfloor\geq \left\lfloor\frac{\sum_{i=1}^{k-1} 0+\sum_{i=k}^n a_k}{n}\right\rfloor= =\left\lfloor\frac{(n-(k-1))a_k}{n}\right\rfloor=\left\lfloor a_k-\frac{(k-1)a_k}{n}\right\rfloor=a_k+\left\lfloor-\frac{(k-1)a_k}{n}\right\rfloor$
so it suffices to prove $k-1\geq-\left\lfloor-\frac{(k-1)a_k}{n}\right\rfloor$ which is true since $a_k<n$ .

Now we claim that the sequence $b_i=S+i-1$ satisfies the conditions.

Conditions $A$ and $B$ follow from construction and the earlier property.

To prove $C$ note that:

$\sum_{i=1}^n b_i=\sum_{i=1}^n(S+i-1)=nS+n\cdot\frac{n-1}{2}=n\left(\frac{n-1}{2}+S\right)$
so we are done.

Z K Y

The post below has been deleted. Click to close.

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

dolphinday

1318 posts

dolphinday

#53 h Mar 15, 2025, 6:28 PM

Y by

Randomize $b_i \pmod{n}$ . Then $b_i$ ranges from $[a_i, a_i + n - 1]$ , so $\mathbb{E}(b_i) = a_i + \frac{n-1}{2}$ . This implies that there is some choice of $b_i$ (by expected value) so that
$\left(\frac{\sum_{i} b_i}{n} \right) \leq \frac{\sum_i a_i}{n} + \frac{n-1}{2}$

If $n$ is odd, then both $\frac{\sum_{i} b_i}{n}$ and $\frac{n-1}{2}$ are integers, so $\frac{\sum_i a_i}{n}$ is also an integer.

If $n$ is even, then $\left(\frac{\sum_{i} b_i}{n} \right) - \frac{n-1}{2}$ is an integer which implies that $\frac{\sum_i a_i}{n}$ is also an integer.

Thus there is some choice of $b_i$ so that
$\left(\frac{\sum_{i} b_i}{n} \right) \leq \left\lfloor \frac{\sum_i a_i}{n} \right\rfloor + \frac{n-1}{2}.$ from our initial existence claim and replacing the fraction with the floor value in the problem statement.
Multiplying by $n$ on both sides gives us the desired, so we are done.

Z K Y