Maths Olympiad Prep

Library / /282 of 520

Combinatorics Difficulty 5.3 AIME, harder Find the answer

Example 5. Find the largest integer AA, such that for any permutation of all natural numbers from 1 to 100, there are 10 consecutive numbers whose sum is greater than or equal to AA.
[22nd Polish Mathematical Olympiad]

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

This problem, although it is to find the maximum integer AA, is actually an existence problem, i.e., there exists a maximum integer AA such that the sum of 10 consecutive numbers is not less than AA.

Solution: Let T=(a1,a2,,a100)T=\left(a_{1}, a_{2}, \cdots, a_{100}\right) be a permutation of the natural numbers from 1 to 100.
Consider the sum of 10 consecutive terms
k=110aa+k,n=1,2,,90. \sum_{k=1}^{10} a_{a+k}, \quad n=1,2, \cdots, 90 .

This is a finite set, and in a finite set, there must be a maximum number, denoted as
AT=max1n90io D=1an+x0 A_{\mathrm{T}}=\max _{1 \leqslant n \leqslant 90}^{\text {io }} \sum_{\mathrm{D}=1} a_{n}+x_{0}
Any other sum of 10 consecutive terms does not exceed AxA_{x}.
By the definition of AΓA_{\Gamma}, we have
ATa1+a2++a10ATa11+a12++a20,AXa61+a82++a100 \begin{array}{l} A_{\mathrm{T}} \geqslant a_{1}+a_{2}+\cdots+a_{10} \\ A_{\mathrm{T}} \geqslant a_{11}+a_{12}+\cdots+a_{20}, \\ \quad \cdots \cdots \\ A_{\mathrm{X}} \geqslant a_{61}+a_{82}+\cdots+a_{100} \end{array}

Adding these up, we get
10Ar1=1100a1=5050, 10 A_{\mathrm{r}} \geqslant \sum_{1=1}^{100} a_{1}=5050,
mosers\rightarrow \operatorname{mosers}
AT>505 A_{\mathrm{T}}>505 \text {. }

According to the problem, we need to find the smallest AxA_{x} among all permutations TT, i.e.,
A=minAr A=\min A_{\mathrm{r}}

Below, we can find a permutation TT^{\prime} such that for the permutation TT^{\prime}, its AT505A_{\mathrm{T}}{ }^{\prime} \leqslant 505.
For example, we can arrange the numbers from 1 to 100 as follows:
T=(100,1,99,2,98,3,97,4,,51,50), \begin{array}{c} T^{\prime}=(100,1,99,2,98,3,97, \\ 4, \cdots, 51,50), \end{array}

which satisfies
a2Ω+1=100n,0n49,a2n=n,1n50. \begin{array}{l} a_{2 \Omega+1}=100-n, 0 \leqslant n \leqslant 49, \\ a_{2 \mathrm{n}}=n, 1 \leqslant n \leqslant 50 . \end{array}

At this point, we have
a2k+a2k+1++a2k+2=(a2k+a2k+2+a2k+4+a2k+0+a2k+8)+(a2k+1+a2k+8+a2k+5+a2k+1+a2k+0)=(k+k+1+k+2+k+3+k+4)+[100k+100(k+1)+100(k+2)+100(k+3)+100(k+4)]=500a2k+1+a2k+2++a2k+10=(a2k+a2k+1)+(a2k+2+a2k+8)+ \begin{array}{l} a_{2 k}+a_{2 k+1}+\cdots+a_{2 k+2} \\ =\left(a_{2 k}+a_{2 k+2}+a_{2 k+4}+a_{2 k+0}\right. \\ \left.+a_{2 k+8}\right)+\left(a_{2 k+1}+a_{2 k+8}+a_{2 k+5}\right. \\ \left.+a_{2 k+1}+a_{2 k+0}\right) \\ =(k+k+1+k+2+k+3+k+4) \\ +[100-k+100-(k+1)+100-(k \\ +2)+100-(k+3)+100-(k+4)] \\ = 500 \\ a_{2 k+1}+a_{2 k+2}+\cdots+a_{2 k+10} \\ =\left(a_{2 k}+a_{2 k+1}\right)+\left(a_{2 k+2}+a_{2 k+8}\right)+\cdots \end{array}
+(a2k+8+a2k+2)+a2k+10a2k=500+k+55=505. \begin{aligned} & +\left(a_{2 k+8}+a_{2 k+2}\right)+a_{2 k+10}-a_{2 k} \\ = & 500+k+5-5 \\ = & 505 . \end{aligned}

Thus, Ax505A \mathrm{x}^{\prime} \leqslant 505.
From (1) and (2), we get A=505A=505.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.