IBM 11月解答

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.

这题的意思是在NxNxN的网格立方体中选K个点，使得这K个点在三个坐标平面上的3K个投影各不相同，并且恰好盖满NxN的正方形。对什么样的N这样的K个点存在？

显然要有 3K = N^2，即N必须是3的倍数。下面证明这也是充分条件。

先设N是奇数。及格子点的坐标是从0到N-1。令点集 S = {(i, (i+3j) mod N, (i+6j+1) mod N) | i = 0,...,N-1, j = 0, ..., N/3-1}。可以验证S满足要求。（另外注意N是偶数时不行。）

N是偶数时用归纳法。设 S 对 N/2满足要求。则 S，S1 = {(i,j+N/2,k+N/2)|(i,j,k) in S}, S2 = {(i+N/2,j,k+N/2)|(i,j,k) in S}, S3 = {(i+N/2,j+N/2,k)|(i,j,k) in S} 的并集对N满足要求。

所有跟帖： 

• 师傅，又是您第一个做出来得？：）佩服啊！！！ -idiot94- ♂ (0 bytes) () 11/13/2007 postreply 16:47:27

• 不是。太忙，过了好几天才寄去 -康MM- ♀ (0 bytes) () 11/14/2007 postreply 07:32:05