0
$\begingroup$

The input consists of a set of positive integers $\{b_1,...,b_2\}$ such that $$\sum_{i=1}^nb_i=CK,$$ with $C$ and $K$ two positive integers.

The question is the following, is there $k\in\{1,...,n\}$ for which the following inequality is true $$\left \lfloor \sum_{i=1,i\neq k}^n\frac{b_i}{C}\right \rfloor \leq \sum_{i=1,i\neq k}^n \left \lfloor \frac{b_i}{x}\right \rfloor,$$ where $x=C-\left(C\left \lceil\frac{b_k}{C}\right \rceil-b_k\right)$, it also means we always have $C\geq x$.

Example with $b_1=7804, b_2=6080, b_3=3376$. We have $7804+6080+3376=3452\times5$. Let's take $C=3452$.

  • For $k=1$, we have $x=3452-\left(3452\left\lceil\frac{7804}{3452}\right\rceil-7804\right)=900$. Then the inequality is true because: $$\left\lfloor \frac{6080}{3452}+\frac{3376}{3452}\right\rfloor < \left\lfloor \frac{6080}{900}\right\rfloor+\left\lfloor \frac{3376}{900}\right\rfloor.$$
  • For $k=2$, we have $x=3452-\left(3452\left\lceil\frac{6080}{3452}\right\rceil-6080\right)=2628$. Then the inequality is true because: $$\left\lfloor \frac{7804}{3452}+\frac{3376}{3452}\right\rfloor = \left\lfloor \frac{7804}{2628}\right\rfloor+\left\lfloor \frac{3376}{2628}\right\rfloor.$$
  • For $k=3$, we have $x=3452-\left(3452\left\lceil\frac{3376}{3452}\right\rceil-3376\right)=3376$. Then the inequality is not true because: $$\left\lfloor \frac{7804}{3452}+\frac{6080}{3452}\right\rfloor > \left\lfloor \frac{7804}{3376}\right\rfloor+\left\lfloor \frac{6080}{3376}\right\rfloor.$$

Is there a way to show that for a set $b$ of integers (with $C$ and $K$ as described above) we always have $k\in\{1,...,n\}$ for which the inequality is true?

$\endgroup$
2
$\begingroup$

Yes. At first, if $b_i>C$ for some $i$, replace $b_i$ to $b_i-C$. If new set is ok, then the old also was ok. If all $b_i$'s do not exceed $C$, just choose $k$ for which $b_k$ is minimal. RHS is not less then $n-1$, LHS is at most $n-1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.