3. In a Cartesian coordinate plane, call a rectangle standard if all of its sides are parallel to the $x$ - and $y$-axes, and call a set of points nice if no two of them have the same $x$ - or $y$-coordinates. First, Bert chooses a nice set $B$ of 2016 points in the coordinate plane. 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. Bert returns and then miraculously notices that there does not exist a standard rectangle that contains at least two points in $B$ and no points in $E$ in its interior. For a given nice set $B$ that Bert chooses, 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. Help Bert determine the minimum and maximum possible values of $f(B)$.
Proposed by Yannick Yao.
Solution 1. The minimum is 2015 , since there needs to be a point in $J$ whose $x$ coordinate is between each two consecutive points in $A$ when sorted by $x$-coordinate. The minimum is achieved when $A=\{(t, t) \mid t=0,1, \cdots, 2015\}$.
For general $|A|=c$ (instead of 2016) the maximum is $2 c-2 \sqrt{c}$
To keep things clean, I will let $c=k^{2}$ where $k$ is a positive integer. The construction, as mentioned above is to take a $k$ by $k$ square and rotate it slightly.
Now to show that $2 c-2 k$ suffices, consider the set of points in $A$ as a poset where for points $p, q, p>q$ if $p$ is up and right of $q$.
Take the longest antichain and say it has $s$ elements. This antichain is actually an up left chain of points. Partition the remaining points into two sets, those that are $>$ than some element in the antichain and those that are $<$ some element in the antichain. For the first set, Ernie draws points slightly below and left of each point and Ernie draws points slightly above and right of each point in the second set.

In total Ernie has drawn $k^{2}-s$ points. (We have eliminated all possible rectangles where the two points in A form an up right vector since these two points cannot both be in the antichain)

Now we can do the same for up left rectangles. To finish the problem it suffices to note Dilworth's theorem and use AM-GM.

This first solution was suggested by Allen Liu.
Solution 2. Here is an alternative way to show the maximum. As above, the number of points needed for $J$ is equal to
- Twice the number of points,
- minus the length of the maximal down-right chain, and
- minus the length of the maximal up-right chain.

If we order the points by their $x$-coordinate and consider a sequence being their $y$-coordinates, the two things we are subtracting becomes the length of maximal decreasing subsequence and the length of maximal increasing subsequence respectively. Notice that if the two lengths are $m$ and $n$ respectively, then the number of points is at most $m n$, because of the famous result that a sequence of $m n+1$ distinct real numbers must either contain an increasing subsequence of length $m+1$ or a decreasing subsequence of length $n+1$.
Therefore, in the context of this particular case, we have $m n \geq 2016$ and we need to maximize $2 \cdot 2016-m-n$, and this is easy by AM-GM, and the maximized result is $2 \cdot 2016-\lceil 2 \sqrt{2016}\rceil=3942$.
This maximum is achieved by having a slightly tilted $42 \times 48$ lattice grid for $A$.