document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=1205940>Question 1205940</A>: <I><SPAN STYLE=\"word-break: break-all;\"> A lattice point is a point with integer coordinates.<BR>\n" );
document.write( "Find, with proof, the smallest 𝑁 such that, given any set of 𝑁 lattice<BR>\n" );
document.write( "points, you can find a pair of them whose midpoint is also a lattice point. </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #843052 by </B><A HREF=/tutors/aboutme.mpl?userid=math_tutor2020><B>math_tutor2020(3817)</B></A><img src=\"/images/stars/stars-13.gif\" alt=\"\" >&nbsp;<A HREF=/tutors/aboutme.mpl?userid=math_tutor2020><IMG SRC=http://www.algebra.com/images/aboutme-small.gif BORDER=0 alt=\"About Me\" VALIGN=MIDDLE></A>&nbsp;<IMG SRC=http://www.algebra.com/images/nopicture.jpg><BR>You can <A HREF=\"/cgi-bin/embed-solution.mpl?show=1&solution=843052\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> <font color=black size=3><BR>\n" );
document.write( "odd + odd = even<BR>\n" );
document.write( "even + even = even<BR>\n" );
document.write( "even + odd = odd<BR>\n" );
document.write( "Adding two numbers of the same parity leads to an even result.<BR>\n" );
document.write( "Any even number when divided by 2 will result in some integer.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "If a and c have the same parity then (a+c)/2 is an integer.<BR>\n" );
document.write( "If b and d have the same parity then (b+d)/2 is an integer.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "If a and c differ in parity (one is odd, the other even) then (a+c)/2 isn't an integer.<BR>\n" );
document.write( "A similar situation happens with (b+d)/2 as well.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Since we have 2 choices for parity and 2 coordinate slots, there are 2*2 = 4 different types of ordered pairs:<BR>\n" );
document.write( "(even, even)<BR>\n" );
document.write( "(even, odd)<BR>\n" );
document.write( "(odd, even)<BR>\n" );
document.write( "(odd, odd)<BR>\n" );
document.write( "Let's say that we picked 4 random points and let's say we picked 1 of each form shown above. Clearly we don't have a parity match if we have this bad of luck. But the 5th point will guarantee to land on one of the parities mentioned due to the Pigeon-Hole Principle. <BR>\n" );
document.write( "Therefore, we'll have a guaranteed parity match by the 5th point if there wasn't a match already.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "In other words, having <font color=red>5</font> random lattice points guarantees at least two of those points form a midpoint that's also a lattice point.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Answer: <font color=red size=4>N = 5</font><BR>\n" );
document.write( "</font> </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );