I am not sure about my answer for the upper bound so I will post my solution for the lower bound. In general, we will prove that if Bert choose a nice set of $m \ge 6$ points in the coordinate plane then $m-1 \le f(B)$. We call the points that Bert, Ernie selected as good, bad points. We will rephrase the problem for convenience: Assume that those $m$ points have $x-$coordinates $x_1<x_2< \cdots <x_m$. Without loss of generality, assume that $x_{i+1}-x_i=x_{j+1}-x_j=1$ unit for all $1 \le i,j \le m-1$. Similar to $y$- coordinates. With each point in Bert's nice set, we draw two line passing through that point and parallel to $x$-axis, $y$-axis. This will create a $(m-1) \times (m-1)$ grid that has $(m-1)^2$ cells $1 \times 1$. Each point of Bert's nice set lies on a vertex of a cell so that no two point lie on a same line. For example, here is a way that Bert can pick a nice set with $m=5$. [asy][asy] size(2.5cm); for (int i=0; i<=4; ++i) { draw((0,i)--(4,i)^^(i,0)--(i,4)); } dot((0,1),linewidth(4)); dot((2,2),linewidth(4)); dot((3,0),linewidth(4)); dot((4,4),linewidth(4)); dot((1,3),linewidth(4)); [/asy][/asy] Now, Ernie need to pick a nice set of $n$ points to put so that there does not exist a standard rectangle that contains at least two points in $B$ and no points in $E$ in its interior. In order to reach a minimum $n$, it not hard to see that these $n$ points must be inside the grid $(m-1) \times (m-1)$ and its must be inside the cell $1 \times 1$ in order to get nice set with exactly $m+n$ points. Furthermore, the condition also implies that for each standard rectangle which has $2$ points in Bert's nice set as vertices, we must need at least one bad point inside this rectangle (since we need minimal $n$ so one point is enough). We call this type of rectangle as complex rectangle. For example, here is a way to put a minimal bad points on a grid above: [asy][asy] size(2.5cm); for (int i=0; i<=4; ++i) { draw((0,i)--(4,i)^^(i,0)--(i,4)); } dot((0,1),linewidth(4)); dot((2,2),linewidth(4)); dot((3,0),linewidth(4)); dot((4,4),linewidth(4)); dot((1,3),linewidth(4)); dot((0.5,1.5),linewidth(4)); dot((2.5,0.5),linewidth(4)); dot((1.5,2.5),linewidth(4)); dot((3.5,3.5),linewidth(4)); [/asy][/asy] Hence, for a given $(m-1)\times(m-1)$ gird with given placing of $m$ good points, we need to find the minimal placing of bad points in order to satisfy the condition above. _______________________________ We will prove that $m-1 \le f(B)$. Indeed, consider grid $(m-1) \times (m-1)$ with $m$ good points. Consider each row of the grid. Since any two good points are in different lines so in each row, there will be a complex rectangle that lie in that row. For example, these are four complex rectangles that lie in each row for the grid above. [asy][asy] size(2.5cm); fill((1,3)--(4,3)--(4,4)--(1,4)--cycle,lightgray); fill((1,2)--(2,2)--(2,3)--(1,3)--cycle,lightblue); fill((0,1)--(2,1)--(2,2)--(0,2)--cycle,lightyellow); fill((0,0)--(3,0)--(3,1)--(0,1)--cycle,lightred); for (int i=0; i<=4; ++i) { draw((0,i)--(4,i)^^(i,0)--(i,4)); } dot((0,1),linewidth(4)); dot((2,2),linewidth(4)); dot((3,0),linewidth(4)); dot((4,4),linewidth(4)); dot((1,3),linewidth(4)); [/asy][/asy] Each of these complex rectangles need at least one bad points so there are at least $m-1$ bad points that Ernie can put in. Therefore, $f(B) \ge m-1$. Here is an example of way to put $m$ good points to get $m-1$ bad points minimal: [asy][asy] size(3cm); for (int i=0; i<=5; ++i) { draw((0,i)--(5,i)^^(i,0)--(i,5)); } dot((0,0),linewidth(4)); dot((2,2),linewidth(4)); dot((1,1),linewidth(4)); dot((4,4),linewidth(4)); dot((3,3),linewidth(4)); dot((5,5),linewidth(4)); dot((0.5,0.5),linewidth(4)); dot((1.5,1.5),linewidth(4)); dot((2.5,2.5),linewidth(4)); dot((3.5,3.5),linewidth(4)); dot((4.5,4.5),linewidth(4)); [/asy][/asy] For $m=2016$, we get $f(B) \ge 2015$.

Yeah i too got the construction(that too after heavy efforts) but saw no way to prove it... Eagerly waiting for the official solution.

Well, I just constructed 3942...

Well, that is not at all useful

ABCDE wrote: To mess with Bert, Ernie then chooses a set $E$ of $n$ points in the coordinate plane such that $B\cup E$ is a nice set with $2016+n$ points. ... define $f(B)$ as the smallest positive integer $n$ such that Ernie can find a nice set $E$ of size $n$ with the aforementioned properties. Yannick Yao sorry! I want to ask if Ernie should choose a nice set or not?The first paragraph doesn't say but the second paragragh say it?

ltf0501 wrote: sorry! I want to ask if Ernie should choose a nice set or not?The first paragraph doesn't say but the second paragragh say it? The first paragraph implies that Ernie must choose a nice set in order to get a nice set with $2016+n$ points.

My solution Alas,I didn't manage to vig the whole problem,but I can prove the minimum value of $f(B)$ is $2015$ Proof:Let's consider point $i$'s coordinate as $(x_{i},y_{i})$ where $i=1,2,\ldots,2016$(Bert's of course). And it is easy to know that there doesn't exists a pair of $(i,j)$ where $1 \le i,j \le 2016$ satisfies that $(x_{i}-x_{j})(y_{i}-y_{j})=0$,or it's against the problem.WLOG $x_{1}<x_{2}<\ldots<x_{2016}$. As the problem itself says:there does not exist a standard rectangle that contains at least two points in B and no points in E in its interior,which means for every $i=1,2,\ldots,2015$,there are at least one point inside the rectangle $[(x_{i},y_{i}),(x_{i+1},y_{i}),(x_{i},y_{i+1}),(x_{i+1},y_{i+1})]$'s interior. It's obvious that for each rectangle it doesn't overlapping other rectangles,as $i=1,2,\ldots,2015$,so $f(b)$ must be at least $2015$.And if we let Bert's $2016$ points be $(2,2),(4,4)\ldots(2k,2k)\ldots(4032,4032)$ and let Ernie's points be $(3,3),(5,5),(7,7),\ldots,(2s+1,2s+1),\ldots,(4031,4031)$ where $k=1,2,\ldots,2016;s=1,2,\ldots,2015$ then we see the minimum possible value of $f(B)$ can be $2015$ P.S. I guess the maximum value of $f(B)$ is $4032$ Your sincerely CeuAzul

CeuAzul wrote: My solution Alas,I didn't manage to vig the whole problem,but I can prove the minimum value of $f(B)$ is $2015$ Proof:Let's consider point $i$'s coordinate as $(x_{i},y_{i})$ where $i=1,2,\ldots,2016$(Bert's of course). And it is easy to know that there doesn't exists a pair of $(i,j)$ where $1 \le i,j \le 2016$ satisfies that $(x_{i}-x_{j})(y_{i}-y_{j})=0$.WLOG $x_{1}<x_{2}<\ldots<x_{2016}$ As the problem itself says:there does not exist a standard rectangle that contains at least two points in B and no points in E in its interior,which means for every $i=1,2,\ldots,2015$,there are at least one point inside the rectangle $[(x_{i},y_{i}),(x_{i+1},y_{i}),(x_{i},y_{i+1}),(x_{i+1},y_{i+1})]$'s interior. It's obvious that for each rectangle it doesn't overlapping other rectangles,as $i=1,2,\ldots,2015$,so $f(b)$ must be at least $2015$.And if we let Bert's $2016$ points be $(2,2),(4,4)\ldots(2k,2k)\ldots(4032,4032)$ and let Ernie's points be $(3,3),(5,5),(7,7),\ldots,(2s+1,2s+1),\ldots,(4031,4031)$ where $k=1,2,\ldots,2016;s=1,2,\ldots,2015$ then we see the minimum possible value of $f(B)$ can be $2015$ P.S. I guess the maximum value of $f(B)$ is $4032$ Your sincerely CeuAzul That is a pity... but ABCDE has given the correct answer on #3

Jettofaiyafukushireikan wrote: CeuAzul wrote: My solution Alas,I didn't manage to vig the whole problem,but I can prove the minimum value of $f(B)$ is $2015$ Proof:Let's consider point $i$'s coordinate as $(x_{i},y_{i})$ where $i=1,2,\ldots,2016$(Bert's of course). And it is easy to know that there doesn't exists a pair of $(i,j)$ where $1 \le i,j \le 2016$ satisfies that $(x_{i}-x_{j})(y_{i}-y_{j})=0$.WLOG $x_{1}<x_{2}<\ldots<x_{2016}$ As the problem itself says:there does not exist a standard rectangle that contains at least two points in B and no points in E in its interior,which means for every $i=1,2,\ldots,2015$,there are at least one point inside the rectangle $[(x_{i},y_{i}),(x_{i+1},y_{i}),(x_{i},y_{i+1}),(x_{i+1},y_{i+1})]$'s interior. It's obvious that for each rectangle it doesn't overlapping other rectangles,as $i=1,2,\ldots,2015$,so $f(b)$ must be at least $2015$.And if we let Bert's $2016$ points be $(2,2),(4,4)\ldots(2k,2k)\ldots(4032,4032)$ and let Ernie's points be $(3,3),(5,5),(7,7),\ldots,(2s+1,2s+1),\ldots,(4031,4031)$ where $k=1,2,\ldots,2016;s=1,2,\ldots,2015$ then we see the minimum possible value of $f(B)$ can be $2015$ P.S. I guess the maximum value of $f(B)$ is $4032$ Your sincerely CeuAzul That is a pity... but ABCDE has given the correct answer on #3 Yep,,,,,,only 17 on day 1 mum will kill me Being a Chinese student is really difficult

, and my construction works for this general case. Anyway I still can't prove that there doesn't exist a construction with $f(B)$ greater than the value in post #3. Could anybody provide an hint? PS: I don't know how MOP works as I'm not from USA, did USA Contestants for IMO 2016 take the test? Didn't they give a full solution?

A brief sketch for the upper bound (I'll prove the general case, $\lfloor2n-2\sqrt{n}\rfloor$ Intuitively the bound should be no more than $2n $, since we may 'cover' each point in $B $ (henceforth referred to as points) by two points in $E $ ('marks') immediately to its southeast and southwest. Thus, any rectangle bounded by two points in its opposite corners (it's not hard to see why considering just these is sufficient) will contain one of the marks corresponding to its upper corner. The concern, therefore, is to find some way to eliminate $2\sqrt{2} $ marks from this construction (or a similar one). The Erdos-Szekeres problem (which proof I will assume here) gives us that among $(a-1)(b-1)+1$ nice points, we have either a string of $a $ points whose pairwise gradients are all positive, or $b $ points whose gradients are pairwise negative. Directly, this guarantees the existence of one of these (WLOG positive) containing $\lfloor\sqrt{n-1}\rfloor+1$ points. We can do better. Now consider $a= \lfloor\sqrt{n-1}\rfloor+2$, $b= \lfloor\sqrt{n-1}\rfloor$. This is within the bound. By continuing to iterate in this manner, we will find that we have a sequence of 'increasing' points and 'decreasing' points whose total length is at least $2 \lfloor\sqrt{n-1}\rfloor+1$. Ok, this is where things get a little messy. We need to fudge this bound a little because $2 \lfloor\sqrt{n-1}\rfloor+1=\lceil 2\sqrt {n}\rceil$ isn't always true. Why this is important will be apparent later. Through a bit of algebra, we find the equality is true iff $n <\lfloor n-1\rfloor^2+\lfloor n-1\rfloor+1$. For $n \ge \lfloor n-1\rfloor^2+\lfloor n-1\rfloor+1$, (note $n <\lfloor n-1\rfloor^2+3\lfloor n-1\rfloor+2$ always) $\lfloor\sqrt {n-1}\rfloor+2=\lceil 2\sqrt {n}\rceil $. Furthermore, in this case, we can do the argument in the previous paragraph but with $a+b=2\lfloor\sqrt {n-1}\rfloor+2$ instead, as $n \ge (\lfloor\sqrt {n-1}\rfloor+1)\lfloor\sqrt {n-1}\rfloor$. Much algebra truncated. All in all, we get that the total length of the two sequences is $\lceil 2\sqrt {n}\rceil $. Now consider the longest of both such sequences, and how these sequences are arranged. For the increasing sequence, nothing can be southwest of the first point, northeast of the last, or within the rectangle bounded by consecutive points. The decreasing sequence has similar behavior. Furthermore, they must intersect in a way such that the interiors of one of these rectangles of each sequence intersects (this is better communicated via illustration but I don't have one). These 'restricted areas' partition the plane into 4 sections, in each cardinal direction from the intersecting rectangles. For any point in these sections (WLOG north), we mark immediately southeast and southwest of the points (rotated for the other directions). Any point in the two sequences will be marked based on their direction from the intersecting rectangles, e.g. a point northeast from them will be marked immediately southeast. EDIT: It's possible that the two sequences intersect. In this case, we'll mark everything as before, except the intersection point which will be unmarked. The number of marks remains the same. Rigorously proving this construction is left as an exercise to the reader. It does guarantee that any $n $ points can be covered by $2n-\lfloor2n-2\sqrt{n}\rfloor $ marks (counting the marks used is a simple exercise).

However for the rest of the problem my solution was based off the fact that the coordinates were integers (what I somehow misread) and it was nonsense so $1$ yippee

Here is my solution in the general case with $k$ instead of $2016$. First of all let's schematise the problem. Let's number the points of $B$ with numbers $1, 2,..., k$ respecting the order from left to right on the plane, and let's represent them in a first ordered string $$1\ \ 2\ \ ...\ \ k$$Then let's write in a second string a permutation of $\left\{1, 2,..., k\right\}$ in such a way that the order of points in this string corresponds to the order of points on the plane from bottom to top. For example if we have the situation in the picture below [asy][asy] size(2.5cm); for (int i=0; i<=4; ++i) { draw((0,i)--(4,i)^^(i,0)--(i,4)); } dot((0,0),linewidth(4)); dot((4,1),linewidth(4)); dot((1,2),linewidth(4)); dot((3,3),linewidth(4)); dot((2,4),linewidth(4)); [/asy][/asy] we will match it to the two strings $$1\ \ 2\ \ 3\ \ 4\ \ 5$$$$1\ \ 5\ \ 2\ \ 4\ \ 3$$A point of $E$ can be schematised as a line which connects a space of the first string with a space in the second. We can say that $E$ has the desired property iff for every couple of points in $B$ there is a line which connect the space between them in the first string with the space between them in the second string. So $\left\vert E\right\vert\ge k-1$ since each space between two near numbers in the first string has at least one line which starts from it. On the other hand it's evident that $\left\vert E\right\vert$ can be exactly $k-1$ if points of $B$ are placed like in the picture below. [asy][asy] size(2.5cm); for (int i=0; i<=4; ++i) { draw((0,i)--(4,i)^^(i,0)--(i,4)); } dot((0,0),linewidth(4)); dot((1,1),linewidth(4)); dot((2,2),linewidth(4)); dot((3,3),linewidth(4)); dot((4,4),linewidth(4)); [/asy][/asy] Hence we found that $$\min\left(f\left(B\right)\right)=k-1$$Now let's find the maximum. In this step we'll show that $$\max\left(f\left(B\right)\right)\ge \left\lfloor 2k-2\sqrt{k}\right\rfloor$$ To prove this lower bound on the maximum it would be enough to find a set $B$ such that there is a set $C$ of $\left\lfloor 2k-2\sqrt{k}\right\rfloor$ not ordered couples of points in $B$ such that for every $2$ couples in $C$ the space between the two numbers of the first couple is disjoint from the space between the numbers of the second couple either in the first or in the second string. Infact in this way the $standard$ rectangles which have a couple in $C$ as opposite vertices are two by two disjoint (eventually except for the perimeter, but it's not a problem since $B\cup E$ it's $nice$) and so there must be a distinct point of $E$ in each one. But how to do that? Let's define the second string as follows: let's imagine we have infinitly many blocks where we can put the numbers. Let's imagine that an immaginary line divides the set of blocks into left blocks and right blocks.. So we can number the blocks as if they were integers on a number line where the $0$ is represented by the immaginary line which separates the left blocks from the right blocks. Hence for example the block at the immediate left of $0$ will be the block $\overline{-1}$, and the one at the immediate right will be the block $\overline{1}$ (I use the overline not to confuse this numbers and the numbers wich represent the points of $B$). Then let's start to put numbers $1, 2, 3,..., k$ in these blocks respectively: $$\overline{-1},\ \overline{1},\ \overline{-2},\ \overline{-1},\ \overline{2},\ \overline{1},\ \overline{-3},\ \overline{-2},\ \overline{-1},\ \overline{3},\ \overline{2},\ \overline{1},\ \overline{-4},...$$Besides numbers in each block will be disposed in increasing order from left to right in left blocks and in increasing order from right to left in right blocks. To clear the situation this is an example of how the second string should be for $k=20$: $$\underbrace{13}_{\text{block $\overline{-4}$}}\ \ \ \underbrace{7\ 14}_{\text{block $\overline{-3}$}}\ \ \ \underbrace{3\ 8\ 15}_{\text{block $\overline{-2}$}}\ \ \ \underbrace{1\ 4\ 9\ 16}_{\text{block $\overline{-1}$}}\ \ \ \underbrace{20\ 12\ 6\ 2}_{\text{block $\overline{1}$}}\ \ \ \underbrace{19\ 11\ 5}_{\text{block $\overline{2}$}}\ \ \ \underbrace{18\ 10}_{\text{block $\overline{3}$}}\ \ \ \underbrace{17}_{\text{block $\overline{4}$}}$$Now we have just to choose the couples of $C$. A couple of points (i.e. numbers) of $B$ belongs to $C$ iff the following properties are respected: -the two numbers of the couple belong to consecutive blocks in the second string; -either the two numbers are consecutive numbers or they are in the same position (in the increasing order) in respective blocks or they are in the blocks $\overline{-1}$ and $\overline{1}$ and the position of the one in the block $\overline{-1}$ is the position of the one in the block $\overline{1}$ increased by $1$. How many couples satisfy this two conditions? We easily note that each number which isn't in the first position in his block is the greater number of a couple in $C$ exactly twice. Instead every number which is in the first position in his block is the greater number of a couple in $C$ exactly once evidently except for the number $1$. If we look again at the construction of the second string, described before, it's also easy to demonstrate that there are exactly $\left\lceil 2\sqrt{k}\right\rceil-1$ non empty blocks. Hence we get that there are $\left\lceil 2\sqrt{k}\right\rceil-2$ numbers which are the greater number of a couple in $C$ exactly once and there are $k-\left\lceil 2\sqrt{k}\right\rceil+1$ numbers which are the greater number of a couple in $C$ exactly twice. Hence $$\left\vert C\right\vert=2\left(k-\left\lceil 2\sqrt{k}+1\right\rceil\right)+\left\lceil 2\sqrt{k}\right\rceil-2=2k-\left\lceil 2\sqrt{k}\right\rceil=\left\lfloor2k-2\sqrt{k}\right\rfloor$$The last thing to prove the lower bound is to show that this set $C$ has the property said when it was defined, but it's a mere case work that I won't write (however it's not long to do that, but it's boring to write it down). Now the final part of the proof, the upper bound: $\max\left(f\left(B\right)\right)\le\left\lfloor2k-2\sqrt{k}\right\rfloor$. The following is a LEMMA whose proof will imply the upper bound: I have the initial ordered string $1\ \ 0$. The allowed moves are the following: a) put a number $1$ at the immediate left of a $0$ or putting a $0$ at the immediate right of a number $1$; b) if in the string there are $s$ digits $0$ (with $s\in\left\{0,1\right\}$) followed by a sequence with $j$ digits $1$ followed by a sequence of $h$ digits $0$ followed by $t$ digits $1$ (with $t\in\left\{0,1\right\}$) (for example $0\ 1\ 1\ 1\ 0\ 0$, in this case $s=1,\ j=3,\ h=2,\ t=0$) I can substitute it with a sequence of $j+1$ numbers $1$s followed by a sequence of $h+1$ numbers $0$s (the example done before would become $1\ 1\ 1\ 0\ 0\ 0$). Note that $s,t,j,h$ can be $0$, also all $0$ at the same time. Note also that the move a) it's a particular case of the move b) but I prefered defining it separately. The thesis is that after $k-1$ moves there will be at least $\left\lceil2\sqrt{k}\right\rceil$ digits in the string. The first thing to be noted is that it's useless to use the move b) with $j\vee h\neq 0$. Infact each move b) with $j\vee h\neq0$ can be done by a composition (in particular cases maybe this composition could be composed by just one move) of moves b) with $s=1,\ j=0,\ h=0,\ t=1$ and moves a) (for example if I have $1\ 1\ 1\ 0\ 0\ 1$ I can do the sequence $1\ 1\ 1\ 0\ 0\ 1\stackrel{\text{move b)}}{\longrightarrow}1\ 1\ 1\ 0\ 1\ 0\stackrel{\text{move b)}}{\longrightarrow}1\ 1\ 1\ 1\ 0\ 0\stackrel{\text{move a)}}{\longrightarrow}1\ 0\ 1\ 1\ 1\ 0\ 0\stackrel{\text{move b)}}{\longrightarrow}1\ 1\ 0\ 1\ 1\ 0\ 0\stackrel{\text{move b)}}{\longrightarrow}1\ 1\ 1\ 0\ 1\ 0\ 0\stackrel{\text{move b)}}{\longrightarrow}1\ 1\ 1\ 1\ 0\ 0\ 0$ instead of applying just one move b) with $s=0,\ j=3,\ h=2,\ t=1$ obtaining directly $1\ 1\ 1\ 0\ 0\ 1\rightarrow1\ 1\ 1\ 1\ 0\ 0\ 0$), and this second alternative is better because we have to "waste" moves in order to have the final string as shorter as possible. Hence the move b) become a simple operation which allows us to pass from $0\ 1$ to $ 1\ 0$. Now the clue of the proof of the LEMMA: if in the final string I have $c$ digits $1$ and $d$ digits $0$, the maximum number of moves b) that I've done is $\left(c-1\right)\left(b-1\right)$. Infact I can do the move b) on each couple composed by one $1$ and one $0$ at maximum once. Besides when I do a move a) putting a $1$ before a $0$ or putting a $0$ after a $1$, I will never be able to do the move b) on the couple composed by this $1$ and this $0$. Besides I can't do the move b) on the couple that I have in the beginning string. Hence since I've done the move a) exaclty $c+d-2$ times, I can do the move b) at maximum $$cd-\left(c+d-2\right)-1=\left(c-1\right)\left(d-1\right)$$times. But for $AM-GM$ this is less or equal to $\left(\frac{x}{2}\right)^2$ where $x$ is $c+d-2$, so it's the number of moves a). This inequality easily gives us an upper bound for the number of moves b) which is $k-2\sqrt{k}+1$ (or better $k-\left\lceil2\sqrt{k}\right\rceil+1$, so a lower bound for the number of moves a) which is $2\sqrt{k}-2$ (or better $\left\lceil2\sqrt{k}\right\rceil-2$), so there will be at least $2\sqrt{k}$ digits. The last thing is to traduce the problem into the LEMMA. Here there is a sketch on how to do that. Let's go back to the notation we introduced at the beginning (the two strings of numbers matched to the set $B$, the elements of $E$ represented with lines...). Let's suggest Enrie to adopt this strategy: underline the number $1$ in the second string. Then underline the other numbers, in increasing order, but before underlining the generic number $w$, do the following operation: if there is a non empty set $S_l$ which includes each underlined number at the left of $w$ (in the second string) such that the space at his immediate right has no lines and such that it has never been the $chosenone$ of $S_l$ before (the meaning of this expression is here below), called $y$ the element of $S_l$ the nearest to $w$ (i.e. the space between $y$ and $w$ in the second string is the shortest) (we'll call $y$ the $chosenone$ of $S_l$), draw a line that starts between $w-1$ and $w$ in the first string and ends between $y$ and the number at its immediate right in the second string. Do the specular (in particular the word "left" becomes "right" and viceversa and the set is $S_r$ instead of $S_l$) operation for numbers at the right of $w$ in the second string. Then you can underline the number $w$ and so on. It's easily verifiable that this algoritm works. Now let's schematise the situation: while Ernie is doing the algoritm, in every moment each underlined number (just underlined numbers!) corresponds to a $0$ if it has never been the $chosenone$ of $S_l$ until now but it has been the $chosenone$ of $S_r$; corresponds to a $1$ if it has never been the $chosenone$ of $S_l$ until now but it has been the $chosenone$ of $S_r$; corresponds to $1\ 0$ if it has never been the $chosenone$ neither of $S_l$ nor of $S_r$ until now; corresponds to nothing if it has already been the $chosenone$ both of $S_l$ and of $S_r$. Finally it's verifiable that when Enrie do the algoritm suggested and then underlines a generic number $w$, these two operations together are schematizable as a move a) or a move b). The last thing to be noted is that every move b) increases by $2$ the cardinality of $E$ and every move a) increases it by $1$. Hence, thanks to the LEMMA, we can say that$$\left\vert E\right\vert\le 2\left(k-\left\lceil2\sqrt{k}\right\rceil+1\right)+\left\lceil2\sqrt{k}\right\rceil-2=2k-\left\lceil2\sqrt{k}\right\rceil=\left\lfloor 2k-2\sqrt{k}\right\rfloor$$ p.s. When I thought this solution I didn't expect it to be so long to write, but evidently the long part was to formalize the schematisations.

Sketch of upper bound without ES: Induction on $n$. As #12 has pointed out,one can cover each point in $B$ by two points in $E$ immediately to its southeast and southwest. To make it better,note that in our previous construction some points are wasted. One can see that if we waste $k$ points,we can bound $f(n)$ by $f(n-k)+2k-2$(i.e,northeast and southeast for each of them,but northeast is not needed for the uppermost one,southeast is not needed for the downmost one). Apply induction hy. to see that $f(n)\le \min(2n-k,f(n-k)+2k-2)\le 2n-2\sqrt{n}$.