Ponder This Challenge - November 2007 - Revealing sets of lights

Ponder This Challenge:

K light-emitting points are placed on a three-dimensional integer lattice (N*N*N cube). Three spectators observe these lights from three different perspectives. Each of them watches a projection on two of three coordinates: XY; YZ; and ZX. For example, the first observer sees the point (2,7,3) as (2,7); the second sees it as (7,3); and the third as (3,2).

A set of light points is defined as revealing if given any point (u,v) in the N*N square, there is an observer who sees a light at that point in his projection and one can uniquely reveal both the exact source of light and the identity of the observer: each point of light (u,v) is seen by exactly one spectator and he or she sees it exactly once (no light hides behind another light).

For which N is there a revealing set? Show how to construct such a set for all feasible N and prove the nonexistence of them for all other N.

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

  Ponder This Solution:

  We need to uniquely find the point from each one of its three projections, so 3*K = N*N. Therefore, no revealing set exists for any N that is not divisible by 3.

  Now to prove the existence of a revealing set for all N=3m, let the grid be in the range (0,0,0) to (N-1,N-1,N-1). Let A be an integer parameter running in the range of [0,N) and B be an integer parameter running in the range of [0,m). We will pick the points that can be described as (X,Y,Z) = ( A,A+3B,2A+3B+1-(A mod 3) ) (mod N) for some such A and B. As the quantity of these points is correct, suffice that we show that there is no overlap.

  First, there is no overlap between the various observers because
  Y-X = 0 (mod 3)
  Z-Y = 1 (mod 3)
  X-Z = 2 (mod 3)

  Second, there is no overlap for any single observer:

  1. This is clear for the XY and ZX observers, because both A and B must obviously coincide.
  2. For the YZ observer, A+3B must coincide, so therefore (A mod 3) must also coincide, as must A and hence B.

  Thanks to Michael Brand for the above solution. The September 2007 riddle on his monthly riddle site discusses a more generalized version of this problem. If you liked this riddle, you may enjoy tackling that problem as well.

  ---

  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

• Balakrishnan V (11.01.2007 @05:05:01 PM EDT)
• Dan Dima (11.01.2007 @05:10:31 PM EDT)
• Mirco Pötter (11.01.2007 @06:15:44 PM EDT)
• Luke Pebody (11.01.2007 @07:02:28 PM EDT)
• Andreas Eisele (11.02.2007 @04:13:05 AM EDT)
• Alan O'Donnell (11.02.2007 @10:37:05 AM EDT)
• Alan Murray (11.02.2007 @01:03:52 PM EDT)
• Christian Blatter (11.04.2007 @01:57:24 PM EDT)
• José H. Nieto (11.04.2007 @08:49:02 PM EDT)
• Frank Yang (11.05.2007 @11:55:27 AM EDT)
• John T. Robinson (11.05.2007 @02:29:28 PM EDT)
• Udi Aharoni (11.06.2007 @10:09:08 AM EDT)
• Jiri Navratil (11.06.2007 @12:50:40 AM EDT)
• Michael Quist (11.06.2007 @09:45:22 PM EDT)
• Qurqirish Dragon (11.06.2007 @12:44:47 PM EDT)
• Daniel Bitin (11.08.2007 @05:30:53 AM EDT)
• Benedikt Engels (11.08.2007 @06:38:13 AM EDT)
• Alan McLoughlin (11.08.2007 @11:31:43 AM EDT)
• John Ritson (11.09.2007 @04:46:52 PM EDT)
• Kevin Williamson (11.11.2007 @08:01:31 AM EDT)
• gmgerken (11.11.2007 @12:05:54 AM EDT)
• Andrea Andenna (11.11.2007 @04:31:25 PM EDT)
• John G. Fletcher (11.12.2007 @12:07:37 AM EDT)
• Maxim G. Smith (11.15.2007 @02:45:55 PM EDT)
• Ole Martin (11.16.2007 @02:57:56 AM EDT)
• Andrew Buchanan (11.16.2007 @07:28:33 AM EDT)
• Hongcheng Zhu (11.18.2007 @03:51:28 AM EDT)
• Huicheng Guo (11.18.2007 @11:44:39 PM EDT)
• David McQuillan (11.20.2007 @05:33:21 AM EDT)
• Wu Hao (11.23.2007 @06:12:02 AM EDT)
• Wolfgang Kais (11.24.2007 @05:30:20 AM EDT)
• Gale Greenlee (11.24.2007 @04:35:33 PM EDT)
• David Friedman (11.26.2007 @05:59:18 PM EDT)
• Dion Harmon (11.27.2007 @12:24:59 PM EDT)
• Phil Muhm (11.27.2007 @05:57:45 PM EDT)
• Reiner Martin (11.30.2007 @07:24:47 PM EDT)
• Shmuel Menachem Spiegel (12.01.2007 @07:03:01 PM EDT)