有一天聚會，你與陳、李、張、王、何見面，

即是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

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

### Like this:

Like Loading...

*Related*