4
$\begingroup$

My question is this:

Writing $n(4)$ to be the minimum number of integer lattice points in the plane so that some four of them must determine an integer lattice point centroid, show that $n(4)=13$.

I have shown in a previous exercise by using the pigeonhole principle that among any five distinct integer lattice points the midpoint of some two of them will also be an integer lattice point. This fact is needed to solve the above problem.

Can someone help please?

Update: From the comments below I have succeeded in showing that $n(4)\le 13$. To complete the proof it remains to show that $n(4)>12$. In other words, a set of 12 integer lattice points is needed which avoid having any 4-subset which yields a integer lattice point centroid.

$\endgroup$
  • 1
    $\begingroup$ Hint: Choose two of the 13 points so the midpoint of those two is a lattice point. Choose two of the 11 remaining points likewise. Continue. $\endgroup$ – Steve Kass Mar 4 '13 at 13:15
  • $\begingroup$ So I have 5 pairs of points where each pair has a mid-point a integer lattice point. Why will at least two pairs have coincident mid-point? $\endgroup$ – Shahab Mar 4 '13 at 13:30
  • 1
    $\begingroup$ @Shahab: Now apply your previous result, to get two pairs whose midpoints have the same parity in resp. coordinates. $\endgroup$ – hardmath Mar 4 '13 at 13:54
  • $\begingroup$ I'm afraid I don't follow how that helps me. All I can say is that the line joining the mid points of such pairs will have an integer mid point M. I can't see why M will be the centroid. $\endgroup$ – Shahab Mar 4 '13 at 14:03
  • $\begingroup$ Now you have pointpairs $(1,2),(3,4),(5,6),(7,8),(9,10)$ each having lattice point midpoint. So as hardmath suggests, pick from these 5 midpoints two of them whose midpoint is a lattice point. Say you now have m1 = midpoint of 1,2 and also m2 = midpoint of 3,4. Then midpoint of m1,m2 is the centroid of points 1,2,3,4. Follws from $(a+b+c+d)/4=(1/2)([a+b]/2+[c+d]/2)$. $\endgroup$ – coffeemath Mar 4 '13 at 14:10
3
$\begingroup$

The fact that 13 points is enough to guarantee somed set of four with lattice point centroid has been shown in the comments, thanks to Steve Kass. This answer is hopefully an example of 12 points that don't work, as suggested by hardmath.

EDIT: as hardmath notes in a comment, a previous attempt did not work. This is one that I have checked on maple.

For twelve points which have no subset of 4 with centroid at a lattice point, consider the lattice points:

$$(0,0),\ (0,4),\ (0,8),$$ $$(1,2),\ (1,6),\ (1,10),$$ $$(2,1),\ (2,5),\ (2,9),$$ $$(3,3),\ (3,7),\ (3,11).$$ Note that there are three in each group which are congruent mod $(Z_4)^2$. So another way to look at a computation is to consider three each of the first terms in the four lists, and look at the sums mod $4$.

I did a check of all sets of 4 of the above vertices on maple, to verify that none of the sums have both coordinates $0 \mod 4$, and so none of the centroids are lattice points.

Here is a sketch of how the example can be checked "by hand". Suppose one has the multiset $A=\{ 0,0,0,1,1,1,2,2,2,3,3,3 \}$ of residues mod 4. (three of each residue). There are then only the following six ways to make a sum of $0$ mod $4$ from $A$, and next to each in brackets is the value mod 4 of that sum after interchanging the residues $1$ and $2$:

$0+0+2+2$ : [$2=0+0+1+1$]

$1+1+3+3$ : [$2=2+2+3+3$]

$0+0+1+3$ : [$1=0+0+2+3$]

$1+1+2+0$ : [$2=2+2+2+0$]

$2+2+3+1$ : [$3=1+1+3+2$]

$3+3+0+2$ : [$3=3+3+0+1$]

A look at the four "generating" lattice points $(0,0),(1,2),(2,1),(3,3)$ shows how the generating set was obtained using each residue class mod 4 as first coordinate, and using the first coordinate with 1 and 2 permuted as the second coordinate. Then each of the generating pairs was simply increased mod 4 on the second coordinates to obtain 12 distinct lattice points.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is a natural guess, but unfortunately (0,3)+(0,1)+(1,0)+(3,0) = (4,4), and so gives centroid (1,1). $\endgroup$ – hardmath Mar 4 '13 at 22:37
  • $\begingroup$ @hardmath : Please check this (totally revised) set of 12 points. I used a different idea to generate, rather than a geometric one. $\endgroup$ – coffeemath Mar 5 '13 at 16:04
  • $\begingroup$ It amounts to taking the four points, first in each row of 3, and allowing up to three repeats when choosing a multiset of size 4 from {(0,0),(1,2),(2,1),(3,3)}. $\endgroup$ – hardmath Mar 5 '13 at 16:20
  • $\begingroup$ Actually I found a problem with my Answer, a missing configuration to avoid, so I like yours, which I have confirmed by hand. $\endgroup$ – hardmath Mar 5 '13 at 16:36
3
$\begingroup$

Initially coffeemath and I sought twelve point subsets of a 4x4 grid, such as the following (which turns out to be a "bad example"):

x  x  x  o
x  x  o  x
x  x  o  x
x  x  x  o

This is a natural approach because coordinates of points may be reduced modulo 4 without affecting the integer centroid property. However in doing so, distinct points may be sent to a common image, thus giving fewer than 12 points in the 4x4 grid. coffeemath's example illustrates this, since there are only 4 distinct images when reduced mod 4.

I decided to investigate whether there exists a twelve point subset of these 16 points, free of integer centroid 4-subsets. Although $\binom{16}{12} = 1820$ possibilities exist, with some help from Dan Shved about combining symmetries of the 4x4 grid, these may be reduced to just 33 representative cases. These I could then check by hand: all include 4-point subsets with integer centroids.

Then I investigated the maximum number of points that can be taken from the 4x4 grid without getting such an integer centroid 4-subset. It turns out one can take at most 8 points. Up to the symmetries discussed in the link above, there are only three ways to reach that limit. Below x denotes points included in the subset, however each solution turns out to be symmetric with its complement:

x  x  o  o  |  o  x  x  o  |  o  x  o  x  
x  x  o  o  |  o  o  x  x  |  o  x  o  x  
x  x  o  o  |  x  o  o  x  |  x  o  x  o  
x  x  o  o  |  x  x  o  o  |  x  o  x  o  

The most compact and symmetric 12 point arrangement I found is in a 6x6 grid:

o  x  o  o  x  o
x  x  o  o  x  x
o  o  o  o  o  o
o  o  o  o  o  o
x  x  o  o  x  x
o  x  o  o  x  o

None of the 8 point arrangements in a 4x4 grid shown above extends to a 12 point subset of a 5x5 grid, which suggests that there are no feasible 12 point subsets of a 5x5 grid.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ What do you mean by coffeemath's 12-point arrangement? $\endgroup$ – Shahab Mar 5 '13 at 11:45
  • $\begingroup$ @coffeemath suggested the 12 points on the boundary of the grid. $\endgroup$ – hardmath Mar 5 '13 at 13:30
  • $\begingroup$ Maybe your program could look at 5 by 5 grids, etc. to get the most compact "square-ish" pattern of 12 points with no 4 having lattice point centroid. (My example is severely oblong; doesn't look nice when plotted.) +1. $\endgroup$ – coffeemath Mar 10 '13 at 15:58
  • $\begingroup$ @coffeemath: Just like your example but based on triplication of a unit square's vertices. $\endgroup$ – hardmath Mar 14 '13 at 3:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.