MathDB

5

Part of 2019 EGMO

Problems(1)

two sequences of positive integers and inequalities

Source: EGMO 2019 P5

4/10/2019
Let n≥2n\ge 2 be an integer, and let a1,a2,⋯ ,ana_1, a_2, \cdots , a_n be positive integers. Show that there exist positive integers b1,b2,⋯ ,bnb_1, b_2, \cdots, b_n satisfying the following three conditions:
(A) ai≤bi\text{(A)} \ a_i\le b_i for i=1,2,⋯ ,n;i=1, 2, \cdots , n;
(B) \text{(B)} \ the remainders of b1,b2,⋯ ,bnb_1, b_2, \cdots, b_n on division by nn are pairwise different; and
(C) \text{(C)} \ b1+b2+⋯bn≤n(n−12+⌊a1+a2+⋯ann⌋)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, ⌊x⌋\lfloor x \rfloor denotes the integer part of real number xx, that is, the largest integer that does not exceed xx.)
floor functioninequalitiesalgorithmcombinatoricsEGMO 2019