3. In the Cartesian coordinate system, there are 16 lattice points $(i, j)$, where $0 \leqslant i \leqslant 3,0 \leqslant j \leqslant 3$. If $n$ points are chosen from these 16 points, there will always be 4 points among these $n$ points that form the vertices of a square. Find the minimum value of $n$.

In the Cartesian coordinate system, there are 16 lattice points $(i, j)$, where $0 \leqslant i \leqslant 3,0 \leqslant j \leqslant 3$. If $n$ points are chosen from these 16 points, there will always be 4 points among these $n$ points that form the vertices of a square. Find the minimum value of $n$.
Answer:
In the 10 points given in the figure, no 4 points form a square.
The following proves that the minimum value of $n$ is 11, i.e., after removing any 5 points, the remaining 11 points must contain 4 points that form a square.
Lemma 1: In the 9 grid points $(i, j), 0 \leqslant i \leqslant 2, 0 \leqslant j \leqslant 2$, if 7 points are taken, these 7 points always contain 4 points that are the vertices of a square.
If not, since $(0,0), (2,0), (2,2), (0,2)$ form a square, at least one of these 4 points must be removed, let's assume it is $(2,2)$. At this point, consider the center point $(1,1)$, which is associated with the most squares, and it should also be removed. Then, among the remaining 7 points, $(1,0), (2,1), (1,2), (0,1)$ form a square, leading to a contradiction.
Lemma 2: In the 12 grid points $(i, j), 0 \leqslant i \leqslant 3, 0 \leqslant j \leqslant 2$, if 9 points are taken, these 9 points always contain 4 points that are the vertices of a square.
If at least one of the 3 removed points is in the 1st column or the 4th column, by Lemma 1, the conclusion holds; if the 3 removed points are in the same column, the conclusion is obviously true; thus, the 3 removed points can only be in the 2nd and 3rd columns. Suppose 1 point is removed from the 2nd column and 2 points are removed from the 3rd column, then the 2nd column can only remove $(1,1)$. At this point, no matter how the points are removed from the 3rd column, $(1,0), (3,0), (3,2), (1,2)$ form a square.
Now, let's prove the conclusion of this problem: If 2 points are removed from one side of the large square, by Lemma 2, the conclusion holds; since $(0,0), (3,0), (3,3), (0,3)$ form a square, at least one of these 4 points must be removed, let's assume it is $(3,3)$. Consider $(1,0), (3,1), (2,3), (0,2)$ and $(2,0), (3,2), (1,3), (0,1)$, each forming a square, and the removed points are on different sides from $(3,3)$, which can only be $(0,1), (1,0)$ or $(0,2), (2,0)$.
If $(0,1), (1,0)$ are removed, at this point, consider the center points $(1,2), (2,1)$, which are associated with the most squares, and they should also be removed. Then, among the remaining 11 points, $(0,2), (1,3), (2,2), (1,1)$ form a square;
Similarly, the case of removing $(0,2), (2,0)$ can be proven. In summary, the minimum value of $n$ is 11.