Avoid lattice midpoints
You select a set of N specific points in the 2D plane with integer coordinates such that, for every pair of the N points, the midpoint of the segment connecting them does not have integer coordinates.
What is the greatest possible value of N ?
Below is an invalid selection of 3 points (in red), since the midpoint of B C has integer coordinates.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
3 solutions
This problem is not explained correctly. The problem asks us to consider the MIDPOINT OF THE SEGMENT
Clear explanation!
Every coordinate is either even or odd. The average of two even numbers or of two odd numbers is an integer but if the parity is different, the average is a half-integer. A lattice point has two integer coordinates. So for the midpoint of a segment to be a lattice point, the endpoints cannot both have the same parity. You can pick up to four points if they are:
(E,E) (E,O) (O,E) (O,O)
but you cannot choose a fifth without replicating one of these.
The question is not very clear. I can select (0,0) and (0,1) whose midpoint is not a lattice point, or (0,0) and (1,2) whose midpoint is not a lattice point.
Log in to reply
The examples you give match what is given in the answer; they shouldn't give lattice points.
(0,0) = (E,E); (0,1) = (E,O) --> don't have the same parity
(0,0) = (E,E); (1,2) = (O,E) --> don't have the same parity
Same parity would be if they were both (E,O), say.
(0,1) (4,5) midpoint is (2,3) and is a lattice point.
Log in to reply
Right, and I can select dozens other such points. The question doesn't ask about how many types of points, but how many points.
Log in to reply
@A Former Brilliant Member – It want you to pick
a set of points so that, for every pair of points, the midpoint is not a lattice point
So you produce a list of points, then check every pair. You seem to be wanting to produce a list of pairs.
Log in to reply
@Jason Dyer – Ok. I understand the wording now. It does make sense, and the wording is correct, but I didn't understand it the first several times reading it, so I think there should be a better way to word it.
Log in to reply
@A Former Brilliant Member – I didn't understand the wording on this either and I think I came to the same conclusion that there are infinitely many points that satisfy this criteria. I still think that the question is a bit goofy.
Who told you that we are drawing a four sided figure?
The way I read the question is that it is asking whether or not you can choose N lattice points such that drawing all N(N-1)/2 possible edges between all possible pairs of those points results in no edge intersecting an additional lattice point.
This question is very poorly phrased and therefore ambiguous.
Log in to reply
The original wording was technically correct, but I've updated it to hopefully be less confusing.
There's no way I would have guessed what this question was actually asking.
Log in to reply
The original wording was technically correct, but I've updated it to hopefully be less confusing.
The question is not clear if its for given diagram or in general.
Log in to reply
The original wording was technically correct, but I've updated it to hopefully be less confusing.
The question stated to solve says: "Suppose you select a set of lattice points so that, for every pair of points, the midpoint is not a lattice point. What is the greatest number of points you can select?", to which I can already see a set comprised of an infinite number of pairs of lattice points that satisfy the necessary conditions for their segment's midpoint to not be a lattice point.
If the author of the problem expected people to come up with the answer he provided, he either framed the question terribly wrong or he missed detailing more the boundary conditions of the problem (e.g., infinite plane or finite, whether he wanted respondents to provide unique characteristics of the endpoints -parity, or other).
Brilliant should do a better job at vetting and curating questions to make sure they are clear and the problem descriptions are complete.
No so much fault to the author as we are all humans and make mistakes. That said, it reflects poorly on Brilliant who should do a better job going forward if it wants to position itself as a trustworthy source. My two cents.
Log in to reply
The original wording was technically correct, but I've updated it to hopefully be less confusing.
The wording seem perfectly correct to me. You should not select a set of pairs of points, but a set of points, and then you should check every pairs in this set.
@Santiago Trevino absolutely.
cant I just choose all points and when i connect them, the points in between is not a predetermined lattice point. I choose No limit as it was the closest to my answer
It is not clear in the question statement that the lattice is bounded or that the points need to form any particular shape. I could select an infinite set of points starting with (0,0), and then all points on the line (x, 1) where x is an integer. For all pairs of points in this set, it is true that the midpoint of the segment connecting them is not a lattice point, and since this set is infinite, the answer therefore is that there is no limit.
Log in to reply
Actually not. You are just considering the pairs [(0,0), (x,1)], but there are also pairs of points such as [(x,1),(x',1)]. So if the distance between any pair of points [(x,1),(x',1)] is even (meaning |x-x'| = 0(mod 2) ), then the midpoint is a lattice point.
I think this solution is close to the truth, however you have to consider the diagonals between the points, so for a set of 4 points there are six segments, and some of these will be between points of the same parity.
@Jeremy Galvagni Another not so optimally stated problem.
As a mathematician, I read this and go straight to the most general situation, taking the image to be a mere example. The question is very poorly put: it should have asked: What is the largest set of points that a sub-lattice of THIS lattice can have, whilst exhibiting the desired properties?
Otherwise, like I took it to mean, consider L 1 : = { ( 0 , 2 n − 1 ) ∣ n ∈ N } ⊆ Z × Z This is an infinite lattice with the desired properties. This answer is correct under the general interpretation (construct a lattice such that…), but who cares. Just please clearly define the scope of your problems!
Furthermore your solution of 4 is not correct. Consider:
L 2 : = { ( 0 , 2 n − 1 ) , ( 2 n − 1 , 0 ) ∣ n ∈ N } ∩ { 0 , 1 , 2 , 3 , 4 , 5 } × { 0 , 1 , 2 , 3 , 4 , 5 }
This is a sublattice with the desired properties, and ∣ L 2 ∣ = 5 . In fact, mirroring this set along the diagonal and joining it to L 2 yields a sublatice with 10 elements and the desired property.
Log in to reply
Hi Ralf -- I've updated the question to be more specific, and less colloquial about "lattice points".
Log in to reply
You select a set of specific points in the 2D plane with integer coordinates
Okay … could you not just write ‘What is the largest cardinality of L ⊆ Z 2 , such that for all p , q ∈ L it holds that 2 1 ( p + q ) ∈ / Z 2 ?’ or the same with Z replaced by { 0 , 1 , 2 , 3 , 4 , 5 } ?
Writing mathematics in the language of mathematics is a lot easier to read and less ambiguous.
Wow I completely misinterpreted that one! I thought it was asking 'how many triangles can be made in the grid where no midpoints are integer?'. I'm not really sure why I thought that. Oh well, great explanation!
Two points P , Q have an integer-coordinate midpoint iff x P ≡ x Q and y P ≡ y Q mod 2.
Therefore, a set N is a solution iff all its points have different coordinates mod 2.
The greatest possible set N will therefore contain all elements of { 0 , 1 } 2 mod 2, i.e. 2 × 2 = 4 different points.
I don't understand how you can square a set {1,0}^2 ?, why are you taking that set?
Log in to reply
{ 0 , 1 } 2 is a shorthand for the Cartesian product { 0 , 1 } × { 0 , 1 } = { ( 0 , 0 ) ; ( 0 , 1 ) ; ( 1 , 0 ) ; ( 1 , 1 ) } .
Modulo 2, "0" and "1" stand for even and odd. Thus, the set could have also been written { E , O } 2 = { ( E , E ) ; ( E , O ) ; ( O , E ) ; ( O , O ) } .
i made an exagon which has only partial integer coordinates (only Y) like your CA and AB middle points. This problem is not explained correctly.
Log in to reply
A(1,0) B(4,0) C(5,2) D(4,5) E(1,5) F(0,2)
Log in to reply
The diagonal B F has midpoint ( 2 , 1 ) . The diagonal A C has midpoint ( 3 , 1 ) .
Consider that every integer x - or y - coordinate will have some parity -- even or odd.
Also consider that the midpoint of two points ( x 1 , y 1 ) and ( x 2 , y 2 ) is ( 2 x 1 + x 2 , 2 y 1 + y 2 ) .
If x 1 and x 2 have different parity, then the midpoint x -coordinate will not be an integer. Likewise with y 1 and y 2 .
For every pair of points, we require at least one of the midpoint values to be a non-integer. This can be accomplished by obtaining every possible combination of parities:
( E , E ) , ( E , O ) , ( O , E ) , ( O , O )
If we select any more points, then we will duplicate one of these parity combinations, and the resulting midpoint will have integer coordinates. Thus, the maximum number of points you can select is 4 .