Let(xi,yi),i = 1,2,3,4,5, be a set of five distinct points with integer coordinates in the xy plane. Show that the midpoint of the line joining at least one pair of these points has integer coordinates.

The midpoint of the line joining the points (a,b) and (c,d) is ((a+c)/2,(b+d)/2).

The coefficient for this midpoint will have integer coefficients if and only if both a and c, and b and d have the same parity. In other words, they are both odd, or both even.

Notice that the sum of two odd numbers is always even, and the sum of two even numbers is always even. And, when you divide an even number by 2, you always get as result an integer.

How many pairs of the form (parity, parity) are there, where parity can be even or odd? We can choose the first parity in two ways (odd or even), and for each of them, we can choose the second parity in 2 more ways. Therefore, by the product rule, we have 4 possible ways to have the parity of the two coordinates.

Let’s these 4 possible ways, be our four boxes.

Notice that the meaning of a box with parity (odd, even) is that a and c are odd, and b and d are even.

So, each box warrantee us that the a and c, and b and d have the same parity.

We have 5 distinct points as per the exercise description. If we put the 5 points in the 4 boxes, by the pigeonhole principle we have one box with at least two points.

THE PIGEONHOLE PRINCIPLE: “If k is a positive integer and k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects.” Discrete Mathematics and its applications by Rosen.

Related exercises:

• Show that if f is a function from S to T, where S and T are finite sets with |S| > |T |, then there are elements s1 and s2 in S such that f(s1)=f(s2), or in other words, f is not one-to-one
• Let d be a positive integer. Show that among any group of d + 1 (not necessarily consecutive) integers there are two with exactly the same remainder when they are divided by d
• A bowl contains 10 red balls and 10 blue balls. A woman selects balls at random without looking at them
• Let n be a positive integer. Show that in any set of n consecutive integers there is exactly one divisible by n.
• A drawer contains a dozen brown socks and a dozen black socks, all unmatched. A man takes socks out at random in the dark.