握手的問題

有一天聚會,你與陳、李、張、王、何見面,
即是6個人的聚會。

聚會中,你與其他5人都握過手,至於他們:

陳 與4人握過手。
李 與4人握過手。
張 與3人握過手。
王 與3人握過手,其中1人是張。
何 與3人握過手。

問題:何 與哪3人握過手?


denote 你,陳,李,張,王,何 as A,B,C,D,E,F

according to the description, we can draw a table
where is symmetry, 0 diagonal and each entry can only be 0 or 1,
0 means no handshake, 1 means has handshake

and a to i are variables

  | A | B | C | D | E | F | total | 
--+---+---+---+---+---+---+-------+
A | 0 | 1 | 1 | 1 | 1 | 1 |   5   | 
--+---+---+---+---+---+---+-------+
B | 1 | 0 | a | b | c | d |   4   | 
--+---+---+---+---+---+---+-------+
C | 1 | a | 0 | e | f | g |   4   |
--+---+---+---+---+---+---+-------+
D | 1 | b | e | 0 | 1 | h |   3   |
--+---+---+---+---+---+---+-------+
E | 1 | c | f | 1 | 0 | i |   3   |
--+---+---+---+---+---+---+-------+
F | 1 | d | g | h | i | 0 |   3   |
--+---+---+---+---+---+---+-------+

rewrite into equations

a+b+c+d = 3
a+e+f+g = 3
b+e+h = 1
c+f+i = 1
d+g+h+i = 2

and rewrite our question as

“Among d,g,h,i, which two are one?”

Generally, there is no algorithm can solve diophantine equations. (I am not sure if this one is in special form). But anyway, instead of brute force approach, rearrange the above variables into the following compact form

  abcd <- one 0 in each of these two rows
  aefg <- 
   hi 
   ^^
 one 1 in each of in these two column

it is not hard to see that

  bc = 01 or 10
  ef   10    01

and so h = i = 0 and d = g = 1

and d correspond to B-F
and g correspond to C-F

所以,何 和 我,陳,李 握過手

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s