Author Topic: Re 灵机一动十一月(2012)-- 数字推理  (Read 2692 times)

润润

  • Newbie
  • *
  • Posts: 4
Re 灵机一动十一月(2012)-- 数字推理
« on: 八月 15, 2013, 08:19:32 pm »
万教授 的题目:

教授在N个学生每人的身后贴了一个正整数,同时在黑板上写了N个正整数,其中有一个为N人
背后数字之和。每个人都可以看到黑板上的数字和别人身后的数字,但看不到自己身后的数字。
每过1分钟,教授问是否有人知道自己头上的数字,若有人推出自己的数字,游戏结束。假设
这些学生都绝顶聪明,能做完全信息下的所有逻辑判断。问他们能否在有限时间内结束游戏。


Since  已经至少有 120 天没人回复了, 我就新开一个主题。

I reach a "solution" for this question. But I don't feel good
with an "ASSUMTION". Is it a "solution"?

First of all, let
  N_1,...,N_n (with ascendent order) be the numbers in the board,
  a_1,...,a_n (with ascendent order) be the numbers for the students (or refer to
the student himself).
  s_i = the SUM of a_j for j != i; i=1,...,n.

Then a_i + s_i = N0 which is one of N_i's.

Step 1. If some a_i found that s_i >= N_(n-1), hence a_i + s_i = N0 > N_(n-1),
        then a_i should know N_n must be the sum N0.

Step 2. Suppose that s_1 < N_(n-1).
       Then we can reduce the number of the students as follows:
    Case A. a_1 <= N_n - N_(n-1)  (The fact that everyone knows it except a_1)
        Since a_1 + s_1 < (N_n - N_(n-1)) + N_(n-1) = N_n,  N_n is not the sum N0.
        Then consider the new game with n-1 students (remove a_1) :
           a'_i = a_(i+1), N'_i = N_i - a_1 ,     i = 1, ..., (n-1)
    Case B. a_1 > N_n - N_(n-1) denoted by p
       Consider the new game (with smaller a_1):
          a'_i = a_i - p, N'_i = N_i - n*p ,     i = 1, ..., n
       Apply Step 1 and 2 to this new game, eventually, we should get a reduced
            new game with less students.

ASSUMPTION: every a_i will follow the above reduction RULE!
       (They should know it since are wise enough!)

After finite steps, we got an one-student game. He should know his number.

Note:  For the new game, some N_i may be negative. But it does not matter,
           All the a_i's are still positive.

润润

  • Newbie
  • *
  • Posts: 4
几点说明:
« Reply #1 on: 八月 24, 2013, 12:06:42 am »
几点说明:

1. s_1 >= s_2 >= ... >= s_n (因a_i是升的)。 每个s_i只能由对应的a_i来计算。
   因Step 1意味着有人能说出他的数字(a_i = N0 - s_i = N_n - s_i), 所以新游
   戏开始第一分钟后如无人出声,即表示所有s_i < N_(n-1),这就有了Step 2的假设:
   Suppose 。。。

2. Step 2的假设   s_1 < N_(n-1)是人人都知道的,虽然他们不知道s_1是多小。

3. Case A中的新游戏是去掉a_1和N_n,而其它N_i则减去a_1.这是做的到的因为a_1是
   所有人(除去a_1)所看到的最小者(a_1看到的最小者是a_2!),在以后游戏里他们
   将不理会a_1及N_n而自成新游戏。

4. Case B中的新游戏没有减少人数,但a_1都严格下降而N'_n - N'_(n-1) =
   (N_n - n*p) - (N_(n-1) - n*p) = N_n - N_(n-1)却是不变。重复有限次(Step 1
   和Step 2)后Case A就会出现(如果没有人说出他的数字的话)。也就可以减少人数了。

5. 如新游戏中有人说出他的数字,他也能说出他在原游戏里的数字,因为它们只差一个
   已知数。

6. N0的大小在新游戏中有变化,但它所在(从小到大的N_i中的)位置不变。

7. 此“solution"似乎没有用到整数的性质,故也应适合非整数情形。