Spring 2016, problem 15
Comments
Not sure about this. The problem as stated defined a centroid specifically for 4 points.
This solution introduces the idea of a centroid for 2 points which I don't think is valid. I guess the terminology for 2 points would be the centre of the line joining them.
@ philboyd
dbrown uses the expression "centroid of two points" exactly the way you just defined it. If that constitutes a slight misuse of terminology, well... So what. It would be fair to say, that pretty much all posts on this board are guilty in this respect. Note also, that when $C(a,b ,c, ...)$ denotes the centroid of $ a, b, c,... $, then:
$C(a,b ,c, d)=C(C(a, b), C( c, d)) $
This is used by dbrown implicitly, when he says:
Finally, apply it one more time, to the set of lattice-point centroids of these 5 pairs. This gives us a pair of pairs, whose 4 points have a lattice-point centroid, as desired.
I think dbrown's argument is entirely sound. And very elegant on top!
@philboyd
I think the term "centroid" is pretty standard for any number of points, but you're right that I was sloppy not to define my terms. Sorry about that. I was using the term to mean the average of a set of points, in the sense that each coordinate of the centroid is given by the average of that coordinate over all the points in the set. This agrees with the definition given in the problem.
I think the term is standard even for solid shapes, where you use a ratio of integrals instead of a finite average.
By iterating dbrown's argument you can show that if $n$ is a power of two, then:
In every set of $4n - 3$ integer points you can find a subset of $n$ points with integer centroid.
Questions:
- Is this true for general $n$?
- Is $4n - 3$ minimal?
I was wondering the same thing.
- I was able to prove the $4n-3$ result for $n = 3$, in an ad hoc way, just considering cases; I don't remember the details now. It follows that the $4n-3$ result holds for any $n$ which is a power of 2 times a power of 3. (I didn't get anywhere for $n = 5$ though.)
- $4n-3$ is minimal for every $n$, using a very similar example to the 12-point example for $n = 4$. Just take $n-1$ points in each of the classes $(0,0)$, $(0,1)$, $(1,0)$, $(1,1)$ modulo $n$, to get a set of $4n-4$ points no $n$ of which have a lattice-point centroid.
Why have we had no submissions?
Is it because, like me, no one understands it?
It's fairly obvious that we only need to consider the set of points [0..3, 0..3] since if the problem is satisfied with x1=z, say, then we can replace z with z MOD 4, and so on for all 16 points.
Are we saying that it is possible to select any set of 12 points from the 16 and that all selections of 4 points from the 12 has the property that the centroid is not is a lattice point?
I think not.
I have written a program to test this and it seems that with 8 points it is possible to select 4 where SOME of the selections do not have a centroid which is a lattice point, but certainly not all.
As soon as we select 9 points (or more) it is always possible to find a set of 4 which does have a centroid which is a lattice point.
It is possible to choose 12 of those 16 points such that the selection of any 4 have the property that the centroid is not a lattice point, so long as you don't require that the 12 points are distinct mod 4. Since we are working mod 4, in your setup, it is entirely possible that we have identified points that were originally distinct before working mod 4. In fact it is easy to find a collection of 12 non-distinct points mod 4 that satisfy the requisite property, giving a lower bound of 12 on n.
Could you list such a set of 12 points please? I have rechecked my code and it still seems that it is possible to select 8 points which satisfy the requirement, but 9 points does not. e.g. for 8 points we can have (0,0) (0,0) (0,0) (0,0) (0,0) (1,1) (1,2) (1,3) where the various (0,0) points would be (4,8) (20, 32) and the like.
We couldn't have 4 points with $(0,0)$ mod 4 in such a set since their sum would then have both coefficients divisible mod 4. A collection satisfying the requirement would be something like 3 copies each of points with mod 4 representatives given by $(0,0)$, $(0,1)$, $(1,0)$, and $(1,1)$. You can check that the sum of any choice of 4 of these points will have a centroid which is not equivalent to $(0,0)$ mod 4.
Whoops !
Yes, program has confirmed result for 12 points exactly as you said.
As expected it is unable to find a selection of 13 which satisfy the same condition.
However, I see that we still don't actually have a proof that 12 is the largest value for n.
To prove that any set of 13 lattice points contains a 4-point subset with a lattice-point centroid, first we prove that any set of at least 5 lattice points contains a 2-point subset with a lattice-point centroid: Apply the pigeonhole principle to the four classes of lattice points (even,odd), (odd,even), (even,even), (odd,odd) to find a class which contains two of the 5 points. (For example, we might find that there are two points each of which have first coordinate even and second coordinate odd.) The sum of these two points is (even,even) so their centroid is a lattice point, as desired.
Next consider an arbitrary set $A$ of 13 lattice points. Apply the above result to find a pair in $A$ with a lattice-point centroid. Apply it again to the remaining 11 points of $A$, then to the remaining 9, and yet twice more, so that we find a total of 5 such pairs in $A$. Finally, apply it one more time, to the set of lattice-point centroids of these 5 pairs. This gives us a pair of pairs, whose 4 points have a lattice-point centroid, as desired.
Now we exhibit a set of 12 lattice points, no 4 of which have a lattice-point centroid: Take $B$ such that three of its points are $(0,0)$ modulo 4 (in each coordinate), three are $(0,1)$, three are $(1,0)$, and three are $(1,1)$. Suppose that $S$ is a 4-point subset of $B$ whose centroid is a lattice point. Then the sum of the points of $S$ is $(0,0)$ modulo 4. Thus all 4 points of $S$ must have the same first coordinate (modulo 4): otherwise we are summing a number of $1$'s which lies strictly between 0 and 4. Similarly all 4 points of $S$ share the same second coordinate (modulo 4). But this calls for four points of $B$ which are the same modulo 4, whereas $B$ was chosen to have no more than three such.