Problem: For every ordered pair of integers $(i,j)$, not necessarily positive,
we wish to select a point $P_{i,j}$ in the Cartesian plane
whose coordinates lie inside the unit square defined by
\[ i < x < i+1, \qquad j < y < j+1. \]
Find all real numbers $c > 0$ for which it's possible to choose these points
such that for all integers $i$ and $j$,
the (possibly concave or degenerate) quadrilateral
$P_{i,j} P_{i+1,j} P_{i+1,j+1} P_{i,j+1}$
has perimeter strictly less than $c$.

Solution: \paragraph{Answer.} $c\geq 4$.

\paragraph{Proof $c < 4$ is not possible.}
Let $n$ be an arbitrary positive integer. We take an $n\times n$ subgrid of unit
squares (i.e. $P_{i, j}$ for $1\leq i, j\leq n$), and compute a lower bound on
the average of all possible quadrilaterals from this subgrid.

Consider the average length of the ``top side'' of all possible quadrilaterals
in this grid. Note that this is equal to:
\[
  \frac{1}{(n-1)^2}\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}P_{i,j}P_{i+1,j}
  \geq \frac{1}{(n-1)^2}\sum_{j=1}^{n-1}P_{1,j}P_{n,j}
  > \frac{n-2}{n-1}.
\]
We can apply this bound to all four sides of the quadrilateral
(the left, right, bottom, and top sides)
to find that the average perimeter of all possible quadrilaterals is greater than
\[ \frac{4(n-2)}{n-1}=4-\frac{4}{n-1}. \]
This means we can always find a quadrilateral whose perimeter is at least $4-\frac{4}{n-1}$.
By taking sufficiently large $n$, this lower bound will exceed $c$.

\paragraph{Proof $c = 4$ is possible.}
We'll place point $P_{i, j}$ at the coordinates $(f(i), f(j))$
for some function $f\colon \ZZ \to \RR$.
The perimeter of $P_{i, j}P_{i+1, j}P_{i+1,j+1}P_{i, j+1}$ is then
\[ 2\big(|f(i+1)-f(i)| + |f(j+1)-f(j)|\big). \]
Therefore we have a valid construction for $c = 4$
if $f$ satisfies $n < f(n) < n+1$ and $|f(n+1)-f(n)| < 1$ for all $n$.
This is achieved by
\[
  f(n) = n + 0.5 + \begin{cases}
    -\sum_{i=1}^{n} \frac{1}{10^i} & \text{if } n \geq 0, \\
    \sum_{i=1}^{-n} \frac{1}{10^i} & \text{if } n < 0. \\
  \end{cases}
\]
Let's check the conditions.
The sum is bounded by $\sum_{i=1}^{\infty}\frac{1}{10^i}=\frac{1}{9}$ in magnitude,
so $n < f(n) < n+1$.
Furthermore, we can verify that
\[
  f(n+1)-f(n) = 1 - \begin{cases}
    \frac{1}{10^{n+1}} & \text{if } n \geq 0, \\
    \frac{1}{10^{-n}} & \text{if } n < 0
  \end{cases}
  < 1.
\]