Ponder This Challenge - January 2003 - 4 points with odd integer distances

Ponder This Challenge:

This month's question was supplied by Vinayaka Pandit. Earlier citations will be given with the answer.

Find four points in the plane such that the distance between each pair of points is an odd integer, or show that this is impossible. (The points need not have integer coordinates.)

We are interested in your original solutions, not those that you may have seen elsewhere.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  It is impossible.
  We can suppose that one of the points is at (0,0).
  Let the other three points be (x1,y1), (x2,y2), (x3,y3).
  (The coordinates need not be integers.)
  Arrange these coordinates into a 3x2 matrix M,
  whose ith row is the coordinates of the ith point:

  | x1 y1 |
  | x2 y2 | = M.
  | x3 y3 |

  Multiply 2M by the transpose of M, obtaining a 3x3 matrix P
  whose (i,j) entry is given by 2*(xi*xj+yi*yj).
  Since the rank of M is at most 2, the rank of P is also at most 2.

  Each diagonal entry of P is twice the square of an odd integer,
  so is equivalent to 2 modulo 16.
  Each off-diagonal entry of P is

  2*(xi*xj+yi*yj)
  = (xi2+yi2) + (xj2+yj2) - ((xi-xj)2+(yi-yj)2)
  = +1 +1 -1 (mod 8)
  = 1 mod 8.

  So P is equivalent, modulo 8, to the matrix

  | 2 1 1 |
  | 1 2 1 | = P'.
  | 1 1 2 |

  We compute that the determinant of P' is 4, so that the determinant
  of P is equivalent to 4 modulo 8.
  In particular P is nonsingular, and has rank 3.
  This contradicts the statement above that P has rank at most 2.

  Several readers pointed out to us that this puzzle is Problem B5 of the 1993 Putnam exam.

  References:

  R. L. Graham, B. L. Rothschild, and E. G. Straus : Are there n+2 points
  in En with pairwise odd integral distances? American Math Monthly
  81(1974)

  L. Piepmeyer : The maximum number of odd integral distances between
  points in the plane. Discrete Computational Geometry. 1996.

  Dr. Warren Smith at NEC labs has also extended the results to odd
  squares instance.

  ---

  If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solvers

• Wei Liu (01.06.2003@01:53:50PM EST)
• (01.06.2003@01:53:50PM EST)
• Erick Bryce Wong (01.06.2003@03:01:43PM EST)
• Lizhao Zhang (01.06.2003@02:00:04PM EST)
• Vladimir Sedach (01.07.2003@03:36:33AM EST)
• Ignacio Larrosa Cañestro (01.07.2003@07:29:09AM EST)
• Nick McGrath (01.07.2003@03:13:38PM EST)
• Michael Swart (01.07.2003@03:34:18PM EST)
• Karl D'Souza (01.07.2003@04:04:55PM EST)
• Michael Brand (01.08.2003@01:49:09PM EST)
• Mikhail Korolik (01.08.2003@06:56:00PM EST)
• John G. Fletcher (01.08.2003@09:25:26PM EST)
• Vitaly Stakhovsky (01.09.2003@03:24:17AM EST)
• Michael Malak (01.09.2003@01:58:57PM EST)
• (01.09.2003@01:58:57PM EST)
• Dan Schwarz (01.09.2003@02:18:52PM EST)
• Ajay Reddy Mallepaly (01.10.2003@05:22:50AM EST)
• ly (01.10.2003@05:22:50AM EST)
• Chuck Carroll (01.11.2003@12:14:45AM EST)
• Christof Schmalenbach (01.11.2003@03:43:04PM EST)
• Chu-Wee Lim (01.11.2003@08:59:48PM EST)
• Trevor Graffa (01.12.2003@02:51:26PM EST)
• (01.12.2003@02:51:26PM EST)
• Hagen von Eitzen (01.13.2003@04:06:09AM EST)
• Sriram Rallabhandi (01.14.2003@12:36:07PM EST)
• Amos Guler (01.15.2003@09:55:50AM EST)
• Surendar Nanchary (01.15.2003@01:14:45PM EST)
• L.T. Pebody (01.16.2003@10:41:29AM EST)
• Biju Mohan (01.16.2003@03:48:48PM EST)
• Bengu Li (01.20.2003@06:31:29AM EST)
• Mohan Rajagopalan (01.20.2003@06:31:29AM EST)
• Bob Stewart (01.20.2003@06:36:11AM EST)
• Alex Wagner (01.20.2003@03:45:55PM EST)
• Ilan Algor (01.21.2003@08:45:56AM EST)
• Andreas Knappe (01.23.2003@01:54:44PM EST)
• Thomas Zheng (01.23.2003@11:10:00PM EST)
• Algirdas Rascius (01.24.2003@04:44:55AM EST)
• Brendan Owen (01.25.2003@03:06:50AM EST)
• James Buddenhagen (01.26.2003@07:18:32PM EST)
• Prithu B Tiwa (01.29.2003@12:21:00AM EST)
• ri (01.29.2003@12:21:00AM EST)
• Jose Coelho (01.29.2003@05:26:26PM EST)
• Max (01.30.2003@09:11:47AM EST)
• i (01.30.2003@09:11:47AM EST)
• m G. Smith (01.30.2003@09:11:47AM EST)
• Gyozo Nagy (01.31.2003@02:29:00AM EST)
• Peter Huggins (01.31.2003@03:41:03AM EST)