Erdos Szekeres solves this problem, right?

manh.ii wrote: Erdos Szekeres solves this problem, right? No, you would need $4N^2 + O(N)$ people to apply Erdos Szekeres.

Sketch of my solution: Divide the players into $N$ sets consisting of $N+1$ consecutive players. We shall prove that we can choose two students from each sets satisfying the condition. Choose the set whose second smallest player is the smallest. Let $A,B$ be the smallest and the second smallest player form the set. Erase the set and erase all players smaller than $B$. Note that in each other set, at most 1 player is erased by the minimality of $B$. Therefore, induction hypothesis plus $A,B$ finishes the problem

jaydoubleuel wrote: Sketch of my solution: Divide the players into $N$ sets consisting of $N+1$ consecutive players. We shall prove that we can choose two students from each sets satisfying the condition. Choose the set whose second smallest player is the smallest. Let $A,B$ be the smallest and the second smallest player form the set. Erase the set and erase all players smaller than $B$. Note that in each other set, at most 1 player is erased by the minimality of $B$. Therefore, we can use induction on the rest of the sets. Could you elaborate? Exactly what do you mean by erasing the players? Are you keeping $A,B$ as two players in the final $2N$ players?

The @jaydoubleuel's solution can be reformulated as follows: partition our players into $N$ blocks of $N+1$ consecutive players with heights $h_{1,1},h_{1,2},\ldots,h_{1,n+1},h_{2,1},h_{2,2},\ldots,h_{2,n+1},\ldots,h_{n,1},h_{n,2},\ldots,h_{n,n+1}.$ Now, let $h_{i,\sigma(i)}$ be the second smallest player in $i$-th block, that's it, if $h_{i,\pi_i(1)}<h_{i,\pi_i(2)}<\ldots<h_{i,\pi_i(n)},$ then $\sigma(i)=\pi_i(2).$ Now, choose $i$ such that $h_{i,\sigma(i)}$ is the smallest and remove $h_{j,\pi_j(1)}$ for all $j\ne i.$ Also, remove $h_{i,\pi_i(3)},\ldots,h_{i,\pi_i(n)}.$ We are now left with $N-1$ block of $N$ consecutive players and two more players who are smallest of all remaining. Now we can use the same procedure again.

The problem can be rekt with an algorithm. First divide the heights into in groups in order. Note that we are ordering the heights, not the players in the row. The algortihm: Alex resets. Then he starts removing players from the left until he has removed two people from some group. Then he removes the $N-1$ from that group, marks those two red and puts them in to the left, and removes one person at random from each group he hasn´t removed from since the reset. Finally we will have a marked pair and $N(N-1)$ players left with $N-1$ groups of $N$ standing. Repeat from the start. When the process terminates, we will have $N$ marked pairs, one from each group. So they satisfy our conditions, and we are done! (My excitement at solving this is clearly leaking through. I thought it seemed pretty easy like 2016/2, but initial reports suggest otherwise. Cutoffs might be very strange this IMO).

@above, Sir Alex. (Sounds like Captain Jack Sparrow, doesn't it?)

Got sniped by zawadx decided to leave writing the solution Was it me only or I found day 2 be much easier than day 1 especially problem 2 compared to 5 and problem 3( which I couldn't get any approach) to problem 6( on which I made substantial headaway.

vjdjmathaddict wrote: Was it me only or I found day 2 be much easier than day 1 especially problem 2 compared to 5 and problem 3( which I couldn't get any approach) to problem 6( on which I made substantial headaway. The jury has no idea about problem difficulty and just follows the numbers in the shortlist. if problem 3 was C6 on shortlist and problem 6 was N8 then jury believes that C6 is easier than N8, if problem 2 was A3 on shortlist and problem 5 was C4 then jury believes that A3 is easier than C4

Split the soccer players into $N$ groups of $N+1$ consecutive people. Give the players a bandanna one by one, starting with the tallest player, then the second tallest, etc. Take the first moment when we have two players in the same group with a bandanna. Make them the first pair, and delete their group and also everyone who got a bandanna so far. We are left with $N-1$ groups of at least $N$ people. Repeat. Done.

It seems everyone has the same algorithmic solution.

See below for a better-written solution

I think that the formulation of the problem was not good. It was not clear whether "stands between" means "stands directly between".

EDIT: Wrong solution, thanks @abeker for pointing it out.

The above is actually false, consider the following permutation as a counterexample: 9, 10, 5, 1, 11,12, 6, 2, 3, 4, 7, 8.

calvin9403 wrote: The following solution is by CSJL and myself. We will use strong induction on this problem: The case $N=1$ is trivial. Now we consider the case $N=2$ and choose the 3 tallest players: Case I : There are 2 of them adjacent, then choose them and let the other tall player leave the row. There will then be 3 players left. By the pigeonhole principle, there will be two players standing at the same side of the 2 chosen players, just choose them and remove the other. Case II : They are at the 1st, 3rd, 5th position in the row, then choosing the 1st, 3rd, 4th, 6th positions satisfy all the conditions. Case III : They are at the 1st, 3rd, 6th position in the row, then choosing the 1st, 3rd, 4th, 5th positions satisfy all the conditions. Now suppose that if we have more than or equal to $(M-1)M$ players, then we can pick $2M-2$ players that satisfy the original condition, and we want to prove that we can pick $2M$ players out of $M(M+1)$ players that satisfy the original condition: Choose the $M+1$ tallest players and call them tall players, then there will be $M^2-1$ players left. By the pigeonhole principle, there exist 2 tall player that have at most $M-1$ players between them. Remove those $M-1$ players as well as the other tall players, then we removed $2M-2$ players and selected 2 tall players that are taller than any other players left. Now assume there are $L$ players on the left of those 2 selected tall player and $R$ players on the right of those 2 selected tall players. By the induction hypothesis, we can select $2A$ players from the left and $2B$ players from the right, where $$A(A+1)\le L\le (A+1)(A+2)-1$$and $$B^2+B\le R\le (B+1)(B+2)-1$$we only need to prove that $A+B\ge M-1$. Add the inequalities up and we have $$L+R=M^2-M\le A^2+B^2+3(A+B)+2$$If $A+B\le M-2$, then $$M^2-M\le A^2+B^2+3M-4\le (M-2)^2+3M-4=M^2-M$$However, the last inequality only holds when $A=0$ or $B=0$, and It is easy to see that they can’t be both 0. WLOG $A=0$, then that means $L=0$ or $L=1$. If $L=0$, then $B$ is actually $M-1$ so we have a contradiction. If $L=1$, then that means when we choose the $M+1$ tallest players, there will be at most $M^2-2$ players left between the left most tall player and the right most tall player, hence there will be 2 intervals with $M-1$ players, choose the interval that won’t make $L=1$ or $R=1$ then we are done. If one interval makes $L=1$ and the other makes $R=1$, then there will be at most $M^2-3$ players left between the left most tall player and the right most tall player, hence there will be 3 intervals with $M-1$ players, choose the interval that is in the middle and we are done. Unless I have misintepreted the problem, won't there be a problem if the $3$rd and $4$th tallest in the final $2N$ are seperated by the two tallest people picked initially?

61plus wrote: calvin9403 wrote: The following solution is by CSJL and myself. We will use strong induction on this problem: The case $N=1$ is trivial. Now we consider the case $N=2$ and choose the 3 tallest players: Case I : There are 2 of them adjacent, then choose them and let the other tall player leave the row. There will then be 3 players left. By the pigeonhole principle, there will be two players standing at the same side of the 2 chosen players, just choose them and remove the other. Case II : They are at the 1st, 3rd, 5th position in the row, then choosing the 1st, 3rd, 4th, 6th positions satisfy all the conditions. Case III : They are at the 1st, 3rd, 6th position in the row, then choosing the 1st, 3rd, 4th, 5th positions satisfy all the conditions. Now suppose that if we have more than or equal to $(M-1)M$ players, then we can pick $2M-2$ players that satisfy the original condition, and we want to prove that we can pick $2M$ players out of $M(M+1)$ players that satisfy the original condition: Choose the $M+1$ tallest players and call them tall players, then there will be $M^2-1$ players left. By the pigeonhole principle, there exist 2 tall player that have at most $M-1$ players between them. Remove those $M-1$ players as well as the other tall players, then we removed $2M-2$ players and selected 2 tall players that are taller than any other players left. Now assume there are $L$ players on the left of those 2 selected tall player and $R$ players on the right of those 2 selected tall players. By the induction hypothesis, we can select $2A$ players from the left and $2B$ players from the right, where $$A(A+1)\le L\le (A+1)(A+2)-1$$and $$B^2+B\le R\le (B+1)(B+2)-1$$we only need to prove that $A+B\ge M-1$. Add the inequalities up and we have $$L+R=M^2-M\le A^2+B^2+3(A+B)+2$$If $A+B\le M-2$, then $$M^2-M\le A^2+B^2+3M-4\le (M-2)^2+3M-4=M^2-M$$However, the last inequality only holds when $A=0$ or $B=0$, and It is easy to see that they can’t be both 0. WLOG $A=0$, then that means $L=0$ or $L=1$. If $L=0$, then $B$ is actually $M-1$ so we have a contradiction. If $L=1$, then that means when we choose the $M+1$ tallest players, there will be at most $M^2-2$ players left between the left most tall player and the right most tall player, hence there will be 2 intervals with $M-1$ players, choose the interval that won’t make $L=1$ or $R=1$ then we are done. If one interval makes $L=1$ and the other makes $R=1$, then there will be at most $M^2-3$ players left between the left most tall player and the right most tall player, hence there will be 3 intervals with $M-1$ players, choose the interval that is in the middle and we are done. Unless I have misintepreted the problem, won't there be a problem if the $3$rd and $4$th tallest in the final $2N$ are seperated by the two tallest people picked initially? I agree, though the hole is even bigger than this. calvin's use of the induction hypothesis on the left and right group separately is a fatal error, as there is no guarantee that the union of two working sets works. Your induction hypothesis needs to be stronger, along the lines of randomusername's proof.

I guess the problem provider is a fan of Manchester United and Alex Ferguson 'soccer team' & 'Sir Alex'

Alex can solve using this algorithm: 1. Split the row into $N$ rows, each containing $N+1$ players. 2. From each row find two persons using induction: 2a. Assume $R$ rows left with $R+1$ persons each. 2b. Give $R+1$ tallest players shirt of color $R$. 2c. Process each row: 2c0: If row has 0 shirts of that color, remove random person. 2c1: If row has 1 shirts of that color, remove that person. 2c2: For the remaining $k$ rows, pick 2 (random) persons of that color. Remove everybody else. Now these rows are solved. Note that $k \geq 1$ because of pigeonhole principle. 2d. Solve the remaining $R-k$ rows iteratively.

Amir Hossein wrote: An integer $N \ge 2$ is given. A collection of $N(N + 1)$ soccer players, no two of whom are of the same height, stand in a row. Sir Alex wants to remove $N(N - 1)$ players from this row leaving a new row of $2N$ players in which the following $N$ conditions hold: ($1$) no one stands between the two tallest players, ($2$) no one stands between the third and fourth tallest players, $\;\;\vdots$ ($N$) no one stands between the two shortest players. Show that this is always possible. Proposed by Grigory Chelnokov, Russia

I hope this isn't a fakesolve. Induct on $N$. The case $N=1$ is trivial. Now, we suppose the problem holds for $N=k$ and show it holds for $N=k+1$. WLOG the soccer players have heights $1,2,\dots N(N+1)$ feet. Let the $i$-th soccer player in the row have height $\sigma(i)$ for some permutation $\sigma$ of $\{1,\dots , N(N+1)\}$. Look at the last $N+1$ soccer players. They have $N+1$ distinct heights $\sigma(N^2), \sigma (N^2+1),\dots \sigma(N^2+N)$. It is clear that there exist some soccer players $i,j$ such that \[|\sigma(i)-\sigma(j)| \le \frac{(N(N+1)-1}{(N+1)-1} = N+1 - \frac{1}{N};\]otherwise we would have \[\max_{i\in \{N^2,\dots , N^2+N\}} \sigma(i) - \min_{i\in \{N^2,\dots , N^2+N\}} \sigma(i) > \left(N+1-\frac{1}{N}\right)(N+1-1) = N(N+1)-1,\]absurd because $1\le \sigma(i)\le N^2+N$ for all $i$. Hence, there exists some soccer players $i,j$ such that $|\sigma(i)-\sigma(j)| \le N$ (because any $\sigma(i)$ is an integer). WLOG, $\sigma(i)<\sigma(j)$. Now, delete all soccer players $k$ with $\sigma(k) \in [\sigma(i),\sigma(j)]$ and all soccer players $k$ with $k\in [N^2,N^2+N]$. This deletes at most $N+N+1-2$ soccer players, leaving us with at least $N^2-N+1$ soccer players. We can delete some arbitrary set of the remaining soccer players to reduce the number of remaining soccer players to $N^2-N$. Now, apply the induction hypothesis to see we could delete some number of soccer players ($(N-1)(N-2)$) to leave $2N-2$ soccer players satisfying the $N-1$ conditions. Adding back in soccer players $i,j$ at the end will make the desired $N$ conditions hold, hence we are done.

Very nice! We partition the $N(N + 1)$ players into $N$ groups, $G_1, G_2, \ldots, G_n$, so that the $i$'th person in the line is in $G_{\left\lceil \frac{i}{N + 1} \right \rceil}$. We claim that repeating the following procedure $N$ times solves the problem: Suppose we are in the $i$'th iteration of the algorithm. In each group, let the two tallest players be $x_i < y_i$. Consider the group with largest $x_i$. From this group, remove everyone other than the two with heights $x_i, y_i$, and call these remaining two the \textit{representatives} of this group. For the remainder of the procedure, ignore this group. Remove from the line anybody with height larger than $x_i$. We first show that, for all $j$, $|G_j| \geq 2$ always. Suppose not, and let $k$ be the earliest step, after which $|G_j| < 2$. Hence, before $k$, we have $|G_j| > 2$, meaning that at least $2$ people were removed from $S$ during the $k$'th step. Let two of these removed people have heights $a$ and $b$. Then, we have $a, b > x_k$; hence, prior to completing step $k$, the second-largest element of $G_j$ is larger than $x_k$, contradicting the fact that $x_k$ is the maximal second-largest element across all groups prior to completing step $k$. Thus, at each step, the algorithm decides on the representatives for one of the groups. This means that, upon completing the full procedure, a set of representatives has been chosen for each group. Now, note that the two representatives for each group stand next to each other in the final line, and that, by hypothesis, $y_1 > x_1 > y_2 > x_2 > \cdots > y_n > x_n$. Hence, this resulting line satisfies the desired, and we are done. $\Box$

Consider a lineup of $n$ soccer players that are ordered from shortest to tallest $M = \{a_1, \dots, a_{(N^2+N)}\}$ and a permutation $G = \{\sigma(a_1), \sigma(a_2), \dots, \sigma(a_{(N^2+N)})\}.$ Split $G$ into $N$ groups $g_1, \dots, g_{(N^2+N)}$ respectively (of $N+1$ players). By pigeonhole, there is at least 1 pair of soccer players in each of the $N$ intervals $[a_1, a_{N+1}], [a_{N+2}, \dots, a_{2N+2}], \dots, [a_{N^2}, a_{N^2+N}]$ who are in the same group in $G.$ Then, the following algorithm finishes: Keep taking soccer players tallest -> shortest from $M$ until you arrive at two players that are in the same group $g_i$ Delete all soccer players in $g_i$ other than those two players and then go back to the first step. The algorithm eventually terminates so we are done! $\boxtimes$

We will prove this by inducktion on $N$, and we prove a stronger statement: WLOG, let the heights be from $1$ to $N(N+1)$. If we split the soccer players into $N$ groups, such that the first $N+1$ people are in the first group, the next $N+1$ people are in the second group, and so on, we can choose two players in each group that satifies the problem conditions. Our base case is $N = 1$, in which we have the permutation $1,2$ or $2,1$. Just choosing these two players satisfies the conditions. For our inducktive step, assume it is true for $N-1$, then we will prove it for $N$. Let the person with height $i$ be called person $i$. For each group, consider the second tallest player, and consider the maximal over all groups. I claim this is at least $N(N+1) - N$. This is because, consider the $N+1$ tallest players. Since there are $N$ groups, two of the tallest $N+1$ players are in the same group, so the maximal 2nd tallest person has to have a height of at least $N(N+1)$. Now, let $R$ be the maximal 2nd tallest person, and let $G$ be the group it's in (number the groups from $1$ to $N$, in order). Since $r$ is the maximal 2nd tallest person, in each group other than $G$, there is at most one person that is taller than $R$. Now, remove everyone in group $G$ and everyone taller than $R$. This will remove $N$ people from group $G$, $N(N-1)-R$ people taller than $R$, and we counted the tallest person in group $G$ twice so we have to add $1$ more person, so we really removed $N + N(N-1)-R - 1$ people. Since we can remove at most one person from each group other than $G$, we've removed at most $G-1$ people left of $G$ and at most $N-G$ people right of $G$. If there is less than $G-1$ people left of $G$ removed, then remove random people from each group with no one removed until there are $G-1$ people removed. Similarly, if there is less than $N-G$ people to the right of $G$ removed, keep removing random people. Now, we will remove $N-1$ people outside of $G$, and $N+1$ people inside of $G$, so there are $N(N+1) - 2N = N(N-1)$ people left. There are $(G-1)(N+1) - (G-1) = (G-1)N$ people left of (what used to be) $G$, and $(N-G)N$ people right of (what used to be) $G$. By our inducktive hypothesis, we divide these $N(N-1)$ people into $N$ groups, so there are $G-1$ groups left of $G$ and $N-G$ groups right of $G$, and we pick two people from each group that satisfies it. Since each of these people have height less than $R$, and the group that $R$ was in is between two of these new groups (so $R$ and the tallest person won't be between the $2k+1, 2k+2$ tallest people), this means by inserting $R$ and the tallest person, we will satisfy the problem conditions. Furthermore, each of the groups in $N(N-1)$ is still in a distinct group in $N(N+1)$ since we've removed one person from each group, so we just add that back. We have proven the inducktive hypothesis, so we conclude that the problem statemnt is true.

For all $k \in \mathbb{N}$, let $G_k$ the group of students that were at the $(k-1)(N+1)+i$-th postitions, $1 \leq i \leq N+1$ in the row. Say that $(a_i,b_i) \succ (a_j,b_j) \iff min(a_i,b_i) > max(a_j,b_j)$. For each $1 \leq k \leq N$, let $G_k=\{a_{k,N+1}>a_{k,N}>...>a_{k,2}>a_{k,1}\}$ the ordering of the students in $G_k$, according to their heights. Now, we perform the following algorithm: $1)$ Choose $1 \leq i_1 \leq N$ such that $a_{i_1,N}$ is maximum, and then choose $a_{i_1,N+1}$ $2)$ Now, forget $G_{i_1}$ and choose $1 \leq i_2 \leq N, i_2 \neq i_1$, such that $a_{i_2,N-1}$ is maximum, and then choose $a_{i_2,N}$ $$...$$$k)$ Forget $G_{i_1},G_{i_2},...,G_{i_{k-1}}$ and choose $1 \leq i_k \leq N, i_k \neq i_1,i_2,...,i_{k-1}$, such that $a_{i_k,N-(k-1)}$ is maximum, and then choose $a_{i_k,N-(k-2)}$ $\implies$ due to construction, $(a_{i_1,N},a_{i_1,N+1}) \succ (a_{i_2,N-1},a_{i_2,N}) \succ ... \succ (a_{i_N,1},a_{i_N,2})$, then $(a_{i_k,N-(k-1)},a_{i_k,N-(k-2)})$ are respectively the $2k-1$-th and $2k$-th tallest players $\implies$ since each pair belongs to different groups, we are done. $\blacksquare$

Lemma. Given a sequence, with each terms belonging to the set $\{1,2,...,N\}$ and each element in this set has at least $N+1$ appearences in the sequence. Then we can delete some terms in the sequence such that $2N$ terms left, and that the $(2i-1)^{th}$ term and the $(2i)^{th}$ term are equal, and each element in $\{1,2,...,N\}$ appears exactly twice. Proof. Induct on $N$ with $N=1$ being trivial. Now we move on to the inductive step. Let the sequence be $a_1,...$, let $j$ be the smallest integer such that $a_j=a_i$ for some $i<j$. By pigeonhole principle we have $j\leq N+1$. We delete $a_1,...,a_j$ and all terms equal to $a_j$. Then notice that each element in $\{1,2,...,N\}\setminus\{a_j\}$ has at least $N$ appearences in the sequence. So by inductive hypothesis we can delete some terms in the sequence such that $2(N-1)$ terms left, combine them with $a_i,a_j$ we are done. $\blacksquare$ Now suppose the players height are $h_1<h_2<...<h_{N(N+1)}$, we colour a player with height $h_i$ colour $k$ if $(N+1)(k-1)+1\leq i\leq (N+1)k$. By the lemma we can delet some terms in the sequence such that $2N$ people left and the $(2i-1)^{th}$ term and the $(2i)^{th}$ term has the same colour, so we are done.

We will create this algorithm inductively. The main heuristic we will follow is that if two people of similar heights are near each other on the line and are close to one of the ends, then we should be able to pair them up without too much risk. WLOG let the heights be $(1, 2, \cdots, N(N + 1))$. We create $N$ groups of $N + 1$ people each such that the first group consists of all the people that are amongst the $N + 1$ shortest, etc. Now, within each group, sort the heights from rightmost along the line to leftmost. Call the player within each group that's second closest to the right the \textit{coach}. We pick the coach that's furthest to the right, and we call him Joe. Let the unique player to the right of Joe that's in his group be called Messi. The key observation from here is that for any given group, there can't be more than two players in that group to the right of Joe. For Joe's group, this follows immediately because we sorted it. For any other group, this follows because otherwise we would have a coach that's closer to the right than Joe. Now we induct down. We pair up Joe and Messi and delete everyone in Joe's group, and we also delete everyone to the right of Joe. Doing this removes at most one person in each non-Joe group, so we essentially reduce to the case where we have $N - 1$ groups of $N$ people. Applying the inductive hypothesis from here finishes, with the base case of $N = 1$ being trivial.

Very nice problem. Divide the players into $N$ groups of $N+1$ people by height. Start from player $1$ (by location), and move right until we have two people of the same group. Draw a line after this, ignore everyone else of this group and repeat the same thing. Suppose we have less than $N$ pairs and get stuck, then say there are $k$ lines so far. Each of the partitions earlier can only have had one player of this group, so there are at least $N+1-k \ge (N+1)- (N-1) = 2$ people of this group, so we can indeed make another pair. Once we have $N$ pairs, see that we have chosen $2$ players from each group and so the problem condition is satisfied. $\blacksquare$

vjdjmathaddict wrote: Got sniped by zawadx decided to leave writing the solution Was it me only or I found day 2 be much easier than day 1 especially problem 2 compared to 5 and problem 3( which I couldn't get any approach) to problem 6( on which I made substantial headaway.

We induct on $N$. For the sake of induction, allow $N=1$ to be the base case, which is trivial. Now let $N \ge 2$. Split the row of players into $N$ segments, each with $N+1$ people. Consider the $N+1$ tallest people, at least two of them will be in one of the segments by Pigeonhole, WLOG let it be the first one. Call these two people Joe and James. Then we can delete all the other players in the first segment (apart from Joe and James), which gives $N-1$ players deleted. Furthermore we delete the rest of the $N+1$ tallest players (again, excluding Joe and James), which gives at most another $N-1$ players deleted. Hence, at most $2(N-1)$ players deleted and we still have at least $N(N-1)$ people left (excluding Joe and James), so we can apply the induction hypothesis to get $2(N-1)$ players satisfying the conditions. Lastly, since Joe and James will now be taller than these $2(N-1)$ players (and they will be next to each other), we can add them in and all the conditions still hold. This completes the induction.

This can always be done by using the greedy algorithm. Start by placing the two tallest players in the first and last positions in the new row. Then place the next two tallest players in the second and second-last positions in the new row, and so on, until the two shortest players are placed in the $(N-1)$th and $N$th positions in the new row. In each step of this algorithm, the players being placed in the new row are guaranteed to not have anyone standing between them, because they are taller (or shorter, in the case of the shortest players) than all the players who have already been placed in the new row. And since no two players are of the same height, the order in which the players are placed in the new row will not affect the result. Therefore, the algorithm will always produce a row of $2N$ players that satisfies the $N$ conditions, as desired.

Group all the players into groups of $N+1$, and find the group whose second shortest player is shortest. Now, delete all but the two shortest in this group, and delete the shortest in every other group. Now, excluding the two shortest we have picked, we are left with $N-1$ groups of $N$ players, all of those taller than the two we just picked, which means that we can apply this again and again until we are left with two really tall players and we are done.

Don't look at it, this is wrong. keep the solution with the $n$ teams! Amir Hossein wrote: An integer $N \ge 2$ is given. A collection of $N(N + 1)$ soccer players, no two of whom are of the same height, stand in a row. Sir Alex wants to remove $N(N - 1)$ players from this row leaving a new row of $2N$ players in which the following $N$ conditions hold: ($1$) no one stands between the two tallest players, ($2$) no one stands between the third and fourth tallest players, $\;\;\vdots$ ($N$) no one stands between the two shortest players. Show that this is always possible. Proposed by Grigory Chelnokov, Russia corresponds to each person the number of the position they are in when they stand in the row initially, for example the first has the number $1$ the second the nymber $2$,...,the last the number $n^2+n$ Let now $A$ be the family of the subject $B$ such that $|B|=2n$ and $B\subseteq (1,2,3...,n^2+n)$ Let also:$X_B\left\{\begin{matrix} 1 & if,they ,satisfy, the ,condition \\ 0 & otherwise \end{matrix}\right.$ $\mathbb{P}(X_B=1)=\frac{2^n*n!}{(2n)!}$ $E[\sum _{B\varepsilon A}X_B]=[\sum _{B\varepsilon A}X_B*\mathbb{P}(X_B=1)=\binom{n(n+1)}{2n}\frac{2^n*n!}{(2n)!}=C$ It is enoyght to prove that $C\geqslant 1$. For $n=2$ it is true. For $n\geqslant 3$ we want to prove that: $(n^2+n)(n^2+n-1)*...*(n^2-n+1)*2^n*n!\geqslant (2n!)^2$ This is true for $n\geqslant 6$ because: $LHS>(n^2+n)(n^2+n-1)*...*(n^2-n+1)*2^n=\prod_{i=1}^{n}(n^2+i)(n^2-i+1)*2=\prod_{i=1}^{n}2(n^4-i^2+n^2+i)>\prod_{i=1}^{n}2*n^4> \prod_{i=1}^{n} (n+1)^4=(n+1)^{4n}=[(n+1)^2*...*(n+1)^2]^2>[(2n*1)*[(2n-1)2]*...*(n(n+1))]^2=(2n!)^2=RHS$ we use $n\geqslant 6$ in $2*n^4>(n+1)^4$ For $n=3,4,5$ we dont need this because $3^6>6!,4^8>8!,5^{10}>10!$

mfw the solution is NOT INDUCTION Divide the players into $N$ groups, each with $N+1$ players whose heights are consecutive. Consider the following algorithm: Sir Alex starts on the left and moves rightwards, writing down the players he sees and their groups. When he first repeats some group, he stops to remove all the players he wrote down, except for the two who share a group. He also removes all the other players in that group. He then sets the two players he found who share a group "aside" and advances leftwards, repeating this process. It is clear that if Sir Alex can do this, then he has produced a valid arrangement of $2N$ players satisfying the conditions. We consider the number of players that possibly could have been removed after Sir Alex set aside the $k$-th pair, where $k<N$. The removed players who share a group with a pair contribute exactly $k(N-1)$. Furthermore, if we consider the original arrangement and take two consecutive pairs of players we set aside, it is clear that after the more-right person in the first pair and before the more-right person in the second pair, each of the $N-k$ groups that haven't been removed yet can appear at most once, otherwise we find a pair of players that we would've set aside sooner than the second pair. Therefore these players contribute at most $k(N-k)$. If Sir Alex is unable to run the algorithm anymore at this point, then among the remaining players (who fall into one of $N-k$ groups), each group must be represented at most once. Therefore, accounting for removed players, set-aside pairs, and the number of remaining players, we find that there are at most $$k(N-1)+k(N-k)+2k+(N-k)=-k^2+2kN+N=N+k(2N-k)$$players total, both removed and unremoved. But for $k<N$ this quantity is less than $N(N+1)$: contradiction. Therefore Sir Alex can run this algorithm until he finds $N$ pairs, which finishes the problem. $\blacksquare$