Problem: Let there be 9 points in 3-space with integer coordinates. Show that th

Question

Problem:
Let there be 9 points in 3-space with integer coordinates.
Show that there is a pair of these points whose line
segment contains an interior point whose coordinates are
integers.

Outline of Proof:
Points in 3-space have 3 coordinates, (a,b,c).
Integer coordinates are either odd or even.
There are 8 odd-even patterns of integer coordinates in 3-space.
Since there are 9 points, at least two must have the same pattern
by the Pigeon-Hole Principle.
The midpoint of the line segment joining two points with the
same pattern has integer coordinates.

Some background information:

Pigeon-Hole Principle
The Pigeon-Hole Principle is the formal statement of a
common sense idea that we are all aware of.
If there are 7 pigeons and 6 pigeon holes and all the
pigeons are in a pigeon hole, then some pigeon hole must
have at least 2 pigeons in it!
- or -
If there are 13 pieces of paper all of which are in one of
3 drawers in a desk, then some drawer must have at least 5
pieces of paper.
Pigeon-Hole Principle
Pigeon-Hole Principle : If kn + 1 objects are distributed
amongst n sets, one of the sets must contain at least
k + 1 objects.
Pf: If no set contains at least k+1 objects, then each of the
n sets has at most k objects. Thus, the total number of
objects is at most nk.


I suppose I am confused on how much of this proof I have to fill in.. and I don't know anything about these coordinates or midpoint of the line segment of joining to points. This whole thing is confusing to me all except for the basics of the principle.

Explanation / Answer

If no set contains at least k+1 objects, then each of the n sets has at most k objects. Thus, the total number of objects is at most nk.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.