Author Topic: 通电话  (Read 7112 times)

PuraVidaQQSH

  • Newbie
  • *
  • Posts: 7
    • Email
通电话
« on: 六月 28, 2012, 11:53:12 am »
某班学生有下列特点:任何四个人中,都有一个人与另外三个人
通过电话。证明:全班之中的任意四个人中,可以找到一个人,
这个人与全班所有人都通过电话。

Comment: I saw this problem somewhere. Judging from
its audience, it is not a difficult problem. But I do not think
the answer provided in the book is complete, but the answer
I could think of is convoluted. Request a simple and strict
answer.

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: 通电话
« Reply #1 on: 六月 28, 2012, 01:03:05 pm »
欢迎新会员。谢谢出题。

我已经想到答案了,不算很麻烦。先等一下让别人做,如果三天没有人做,我再给答案。

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: 通电话
« Reply #2 on: 七月 03, 2012, 09:43:33 am »
这个论坛现在没有以前热闹了。最热闹的时候这个题目过不了夜。

我说好三天以后没人给答案我就贴我的答案,现在已经过了三天。

任意找四人A,B,C,D。按假设,其中必有一人与另外三人通过电话,假定这人
是A。如果问题的结论不成立,则对应于A,B,C,D中的每个人都可以找到另外
一个人没有与他们通过电话。假设对应的人是a,b,c,d。现在考虑A,B,a,
b 这四人。他们中不存在任何一个人与其余三人都通过电话,与假设矛盾。唯一的
可能是a与b是同一个人(而且这个人不能是A或B,因为A与B通过话)。同样道理,
我们可以考虑A,C,a,c 这四人。我们可以得出a与c为A,C以外同一个人。好了,
现在考虑A,B, C,a这四人。a没有与A,B,C中任何一人通过话,就是说这四人
中没有任何人与其余三人通过电话,与假设矛盾。所以,a,b,c,d不可能都存在。
也就是说A,B,C,D中必有一人与所有人都通过电话。

« Last Edit: 七月 03, 2012, 08:28:54 pm by 万精油 »

PuraVidaQQSH

  • Newbie
  • *
  • Posts: 7
    • Email
Re: 通电话
« Reply #3 on: 七月 03, 2012, 11:31:12 am »
Lao Wan,

I believe I have found a bug in your logic. To prove that your conclusion
"A has called everyone" is incorrect, I only need to find an exception which
is as follows:

For the same 4 persons in your answer A, B, C, D, A has called B, C, D.
You did not make any assumptions among B, C, and D, but let us assume
B, C, D have called each other. I can find another person a outside this
group of A, B, C, D, person a has called B, C, D but not A.

Could you explain this exception?

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: 通电话
« Reply #4 on: 七月 03, 2012, 12:29:13 pm »
Quote
For the same 4 persons in your answer A, B, C, D, A has called B, C, D.
You did not make any assumptions among B, C, and D, but let us assume
B, C, D have called each other. I can find another person a outside this
group of A, B, C, D, person a has called B, C, D but not A.

说这个a不存在是在前面那些 b, c 都与a重合的条件下。如果这个a与B,C,D都通过电话的话,
那么我证明中提到的b就不可能是a,那么A,B,a,b 四人已经与假设矛盾,不需要继续
证明了。

PuraVidaQQSH

  • Newbie
  • *
  • Posts: 7
    • Email
Re: 通电话
« Reply #5 on: 七月 03, 2012, 02:47:21 pm »
... A与所有人都通过电话。

Prof Wan,

Why do you say that "A与所有人都通过电话"? You could not logically come to the
conclusion (see my exception case), and you do not need to.

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: 通电话
« Reply #6 on: 七月 03, 2012, 08:33:57 pm »
Quote
Why do you say that "A与所有人都通过电话"? You could not logically come to the
conclusion (see my exception case), and you do not need to.

其实想说的是A,B,C,D中必有一人与所有人都通过电话,偷懒想省几个字,现在还是改回去。:)

PuraVidaQQSH

  • Newbie
  • *
  • Posts: 7
    • Email
Re: 通电话
« Reply #7 on: 七月 08, 2012, 11:52:18 pm »
任意找四人A,B,C,D。按假设,其中必有一人与另外三人通过电话,假定这人
是A。如果问题的结论不成立,则对应于A,B,C,D中的每个人都可以找到另外
一个人没有与他们通过电话。假设对应的人是a,b,c,d。


Thank you, Professor Wan for the solution. I would like to post some comments and
an alternative solution.

With an assumption, the professor suddenly came up with additional 4 people, a, b, c, d, which
brought the problem to life. With 8 people, the professor has more pieces to play with.

The other good point of this solution is the professor made no assumption what happened
among B, C, D - they could called each, and none at all, or things in between.

But what is difficult for me to understand, which is not the professor's fault, is that based on the
his assumption, the professor first has to prove positively that a, b, c, d are the
same person, and then negatively that even this single person does not exist, and
therefore the assumption can not be true. There are some logical jump back and forth.

Here is my alternative solution:

"任意找四人A,B,C,D。按假设,其中必有一人与另外三人通过电话,假定这人是A。"
Now I begin to deviate from the professor. What happened with B, C, and D?

There are two possibilities: (1) At least one pair did not communicate with each
other; (2) They all communicated with each other.

Interestingly, case (2) is hard to handle (I do not know why).

Now let us deal with case (1). For simplicity of explanation and without losing generality,
let us assume C and D did not take to each other. Now let us choose any person a
from the class besides A, B, C, D, and consider a, A, C, D. Since C and D did not take to each other, then
a and A must have talked to each other. Problem solved under the case (1): A talked to anybody
in the class.

Now let us look at case (2). We try to find person b besides A, B, C, D who did not talk to
at least one of A, B, C, D.

The result of this trial has two possibilities: (2A) failed, we can not find such person. This means
any of the A, B, C, D has talked to anyone of the class. The problem is solved under this case.
The other possibility (2B) is we found this person: assume b and D did not talk.

Under the condition (2B), there two possibilities: (2B1) b has talked with at least one of A, B, C;
and (2B2) b did not talk to any of the A, B, C. The possibility (2B2) does not exist.

Now consider (2B1), assume b has talked to B. Consider B, C, b, D. This is the same as case (1) which
has been proved. Therefore under all possible conditions, the problem is proved.

I realized my solution is like writing a computer program which consider all possibilities, and is not elegant,
but I hope at least the proof is correct. What do you think, Professor Wan?

Thanks for everyone who reached this line :-).




万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: 通电话
« Reply #8 on: 七月 09, 2012, 11:27:23 pm »
这个问题其实可以推广到更一般的情况,我的那个证明也同样有效。

任意N个人的集合。如果其中任意K人中都存在一人与其他K-1人
通过电话,那么,对于任意K人,都存在一人与其他所有人通过电话。