The answer is $c \geq 4$.

This forms a grid of rectangles, and it can be verified that each rectangle has a perimeter strictly less than $4$. To prove that $c \geq 4$ is necessary, choose an integer $n$ and consider an $n \times n$ grid of grid squares within the plane. Here's an example with $n = 5$: [asy][asy] int n = 5; for(int i = 0; i <= n; ++i) { draw((i,0)--(i,n), mediumgray); draw((0,i)--(n,i), mediumgray); } pair points[][] = {{(0.9, 0.3), (0.1,0.5), (0.2, 0.8), (0.3,0.6), (0.4,0.5)}, {(0.6, 0.2), (0.3, 0.4), (0.3, 0.7), (0.1, 0.9), (0.5, 0.5)}, {(0.5, 0.5), (0.3, 0.7), (0.4,0.6), (0.2,0.8), (0.3, 0.3)}, {(0.7, 0.7), (0.2, 0.7), (0.5, 0.3), (0.4, 0.5), (0.6, 0.2)}, {(0.4, 0.3), (0.5, 0.1), (0.5, 0.5), (0.1, 0.9), (0.8, 0.2)}}; for(int i =0; i<n; ++i) { for(int j = 0; j < n-1; ++j) { draw((i,j)+points[i][j]--(i,j+1)+points[i][j+1], red+linewidth(1.5)); } } for(int i =0; i<n-1; ++i) { for(int j = 0; j < n; ++j) { draw((i,j)+points[i][j]--(i+1,j)+points[i+1][j], royalblue+linewidth(1.5)); } } for(int i = 0; i< n; ++i ) { for(int j = 0; j<n; ++j ) { dot((i,j)+points[i][j], black+4); } } [/asy][/asy] Due to the triangle inequality, each of the $n-1$ red "worms" has length greater than $n-2$, and similarly, each of the $n-1$ blue worms has length greater than $n-2$. Since each quadrilateral consists of two red segments and two blue segments, the sum of the perimeters of the $(n-1)^2$ quadrilaterals is greater than $2 \cdot (2n-2)(n-2)$. So, the average perimeter of these $(n-1)^2$ quadrilaterals is greater than \[ \frac{2(2n-2)(n-2)}{(n-1)^2} = 4 \cdot \frac{n-2}{n-1}.\]As $n$ grows arbitrarily large, this average grows arbitrarily close to $4$; since there must exist some quadrilateral with a perimeter of at least the average, we can always find a quadrilateral with perimeter greater than $c$ if $c < 4$.

Answer: $c\geq 4$ Construction: Take $P_{i,j}$ to be $(i+\tfrac{1}{2},j+\tfrac{\epsilon}{1+2^j})$. Bound: Consider the $n^2$ quadrilaterals formed by $P_{i,j}$ for $0\leq i,j,\leq n$. Then notice that the length of a zig-zag $P_{i,0}P_{i,1}\dots P_{i,n}$ or $P_{0,j}P_{1,j}\dots P_{n,j}$ is at least $n-1$. Thus two times the sum of the length of each edge in our figure is at least $4(n-1)(n+1)$. But summing over all the quadrilaterals perimeters gives $$cn^2\geq 4(n-1)(n+1)$$Clearly as $n\rightarrow \infty$ we must have $c\geq 4$.

i am illiterate it seems

YaoAOPS wrote: Wouldn't the answer be $c > 4$ because the $P_{i,j} = (i + \frac{1}{2}, j + \frac{1}{2})$ can't have a perimeter strictly less than $4$. c=4 construction exists (but you are correct in that the construction you mentioned fails for c=4)

We claim the answer is $c \ge 4$. For the construction, simply take $P_{i,j} = (f(x), f(y))$ where $f(x) = \begin{cases} x + 1 - \left(\frac 12\right)^{j+1} & x>0 \\ x + \frac 12 & x= 0\\ x + \left(\frac 12\right)^{-j + 1} & x < 0 \end{cases}$. Assume $c = 4 + 4\varepsilon$ for contradiction. Now by Bretschneider's formula, we have that a quadrilateral of perimeter $c$ is maximized when it is cyclic and in this case it has area $$\sqrt[4]{(s-a)(s-b)(s-c)(s-d)} \le \frac{a + b + c + d}{4} = \frac{c}{4} = 1 + \varepsilon$$by AM-GM. Now consider a grid of $n+1 \times n+1$ grid of points, this has area at most $(n+1)^2 \ge n^2(1 + \varepsilon)$ which is false by taking large $n$.

The answer is $c \geq 4$. To construct take, \begin{align*} P_{i, j} = \begin{cases} \left(i + \frac{1}{2}, j + \frac{1}{2^{j+1}}\right) & j \geq 0\\ \left(i + \frac{1}{2}, j + 1 - \frac{1}{2^{-j+1}} \right) & j < 0 \end{cases} \end{align*} For proof of bound defined $Q_{i, j}$ to be the quadrilateral with vertices $P_{i, j}$, $P_{i, j + 1}$, $P_{i + 1, j}$ and $P_{i + 1, j + 1}$.Then consider the $n^2$ quadrilaterals $Q_{x, y}$ with $x, y \in \{0, 1, 2, \dots, n - 1\}$. It is clear that counting one way the sum of the perimeters of these quadrilaterals (overcounting overlapping edges) is $cn^2$. On the other hand, consider quantities of the form, \begin{align*} P_{x, 0}P_{x, 1} + P_{x, 1}P_{x, 2} + \dots + P_{x, n - 2}P_{x, n - 1} \geq n - 2 \end{align*}Writing a similar sum varying $y$ we find, \begin{align*} P_{0, y}P_{1, y} + P_{1, y}P_{2, y} + \dots + P_{y, n - 2}P_{y, n - 1} \geq n - 2 \end{align*}However accounting for double counted edges we find, \begin{align*} cn^2 &> 4(n-2)^2 + 4(n - 2)\\ \iff cn^2 &> 4n^2 - 12n + 8\\ \iff c &> 4 - \frac{12}{n} \end{align*}As $n$ maps to infinity our approximation for $c$ grows better so it becomes clear that $c \geq 4$. Remark: I think this idea is the same as approximating our set of $n^2$ quadrilaterals as $(n - 2)^2$ unit squares.

tapir1729 wrote: 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$. Karthik Vedula Easy to make a constraction for $c=4$ Now we are going to prove that no $c<4$ works. Consider a board $n*n$ then there exist $(n-1)^2$ quadrilateral of the form $P_{i,j} P_{i+1,j} P_{i+1,j+1} P_{i,j+1}$ so the total perimeter is $<(n-1)^2*c$.Consider the $(n-2)^2$ central square and take one of them it makes four edges with each edge belongs to two square the sum of the four edgew inside this squeare is at least $2$ so the total perimeter is at least $(n-2)^2*2*2$ so we have that: $(n-1)^2c>4(n-2)^2\Rightarrow c> 4+\frac{12-8n}{(n-1)^2}\Rightarrow c\geqslant 4+\lim_{n\rightarrow +\infty }\frac{12-8n}{(n-1)^2}=4$ and we are done

Clearly, such a $c$ exists. WLOG, take a $n \times n$ unit square grid $Q_{n, n}$ with the bottom left corner being $P_{1, 1}$. Then notice that $\sum_{i=1}^{n-1} P_{i, k}P_{i+1, k} > n - 2$ for some fixed $k$. So then adding up all of the rows and double counting rows $P_{2, k}$, $P_{3, k}, \dots, P_{n-1, k}$ and $P_{k, 2}$, $P_{k, 3}$, $\dots$, $P_{k, n-1}$ while varying $k$(since each of these edges are edges of two quadrilateral) we get $c(n-1)^2 \geq 4(n-1)(n-2) + 4(n-2) = 4(n-2)(n)$, so $c \geq \frac{4(n-2)(n)}{(n-1)^2}$, however as $n$ approaches infinity we have $\frac{4(n-2)(n)}{(n-1)^2}$ approaching $4$, so $c \geq 4$. We can then show that $c = 4$ with the following recursive construction. Let $P_{0, 0} = (0.5, 0.5)$. Then if $P_{i, j} = (0.5, j)$ define $P_{i, j+1} = (0.5, j + 1 - \frac{1}{1434^j})$. Now for the rest of the grid, reflect the points with positive $i, j$ over lines $x = 0.5$ and $y = 0.5$ to get a complete construction.

The answer is $c\ge 4$, with the construction being $P_{i,j} = \left(i + \frac{1}{2}, j + \frac{1}{2} - \frac{2}{\pi}\arctan(j)\right)$. This works because the perimeter of $P_{i,j} P_{i+1,j} P_{i+1,j+1} P_{i,j+1}$ is \[4 + 2\cdot \frac{2}{\pi}\cdot (\arctan(j) - \arctan(j+1)) < 4,\]and furthermore each $P_{i,j}$ is in its designated unit square. We will now show that $c < 4$ fails. For some $n\ge 3$, consider the $n\times n$ lattice $\{P_{i,j}: 1\le i,j\le n\}$. Note that there are $(n-1)^2$ quadrilaterals here. The sum of the perimeters of these quadrilaterals is \[\sum\text{boundary segments} + 2\times \sum\text{interior segments}\]\[L(P_{1,1}\to\cdots \to P_{1,n}) + 2\sum_{i = 2}^{n-1}L(P_{i,1}\to\cdots \to P_{i,n}) + L(P_{n,1}\to\cdots \to P_{n,n})\]\[+L(P_{1,1}\to\cdots \to P_{n,1}) + 2\sum_{j = 2}^{n-1}L(P_{1,j}\to\cdots \to P_{n,j}) + L(P_{1, n}\to\cdots \to P_{n,n}),\]where $L(\text{path})$ is the length of "$\text{path}$". Note that \[L(P_{1,1}\to \cdots P_{1,n})\ge L(P_{1,1}\to P_{1,n}) \ge n-2,\]and similarly for the other $L$s. Hence the sum of the perimeters is at least \[(n-2) + 2(n-2)(n-2)+ (n-2) + (n-2) + 2(n-2)(n-2) + (n-2) = 4(n-2)(n-1).\]Hence, there exists a quadrilateral with perimeter at least \[\frac{4(n-2)(n-1)}{(n-1)^2} = \frac{4(n-2)}{n-1}.\]This gets arbitrarily close to $4$ as $n$ gets large, so $c < 4$ will clearly not work.

The answer is $c\geq 4$. Define $f(i)=i+\frac12-\frac1{3275}\tan^{-1}(i)$ which lies in the interval $(i,i+1)$, and choose $P_{i,j}$ to have coordinates $(f(i),f(j))$. The distance between $P_{i,j}$ and $P_{i,j+1}$ is $f(j+1)-f(j)=1-\frac1{3275}\left(\tan^{-1}(j+1)-\tan^{-1}(j)\right)<1$ as $\tan^{-1}$ is an increasing function. This shows that each edge is strictly less than $1$ so the perimeter is strictly less than $4\leq c$. Now we show that $c<4$ doesn't work. Consider the $n^2$ quadrilaterals with $(i,j)\in[n]^2$ and calculate their total perimeter. Counting by quadrilaterals, the perimeter is $<cn^2$. Counting by edges, we can telescope the sum $P_{i,1}P_{i,2}+P_{i,2}P_{i,3}+\dots+P_{i,n}P_{i,n+1}\geq P_{i,1}P_{i,n+1}\geq n-1$ by the triangle inequality. $P_{i,1}P_{i,n+1}$ is counted once for $i=1,n+1$ and twice for the rest giving the sum of these lengths being at least $2n(n-1)$. Similarly do this for $P_{1,j}P_{n+1,j}$, so the total perimeter is at least $4n(n-1)$. However, $4n(n-1)<cn^2$ for sufficiently large $n$, resulting in a contradiction in the case where $c<4$.

The answer is $c \ge 4$, where the construction is $P_{i, j} = (i + f(i), j + f(j))$ and $f: \mathbb{Z} \rightarrow (0,1)$ is a strictly decreasing function. Take an $n \times n$ grid such that there are $n^2$ points in the grid and connect any consecutive points. Let the perimeters of the $(n-1)^2$ such quadrilaterals contained in this grid be $\epsilon_1, \epsilon_2, \dots, \epsilon_{(n-1)^2}$ respectively. Furthermore, let $P$ be the outer perimeter of the points in the grid, and $p$ be the sum of the lengths of all other segments (the inner segments). By a global sum, we have $$\mathbb{E}[\epsilon_i] = \frac{1}{(n-1)^2} \cdot \sum_{i} \epsilon_{i} = \frac{P+2p}{(n-1)^2} \ge \frac{4(n-2)+4(n-2)^2}{(n-1)^2} = \frac{4(n-2)}{n-1}$$implying the existence of a quadrilateral with perimeter greater than the RHS. The bound comes from the trivial fact that each inner segment must be at least $0.5$ in length. For all $c < 4$, taking $n$ to be sufficiently large gives the desired contradiction.