Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Mr. and Mrs. Smith, a married couple, invited 9 other married couples to a party. (So the party consisted of 10 couples.) There was a round of handshaking, but no one shook hand with his or her spouse. Afterwards, Mrs. Smith asked everyone except herself, “how many persons have you shaken hands with?” All 19 answers were different.

Unfortunately, when I try to simulate a smaller problem with 3 couples, I am getting that each couple is shaking 4 hands. Here is the diagram:

As you can see both a1 and a2 have 4 blue lines each that are "attached" (ie they shake hands) to the other couples. Both b1 and b2 have 2 red lines and 2 blue lines. Do we count the blue lines again adding it to the 2 red lines giving us that b1 and b2 have 4 lines attached or do we just ignore the blue lines connecting to b1 and b2 and say that both b1 and b2 shake 2 hands each?

Both c1 and c2 also have 2 blue and 2 red lines. I meant to have blue lines designated for a1 and a2, and the red lines for b1 and b2. Does that mean that c1 and c2 have shaken 0 hands each? Or do I try another few lines attaching the c's to the a's and b's?

Another problem with the approach above is that each couple has the same number of handshakes even though that is not possible according to the question. I would appreciate any clarification on the question and what exactly am I doing wrong.

Thanks.

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

Here is a solution for two couples, $m_1,w_1$ and $m_2,w_2$. The edges are $(m_1,w_2),(w_1,w_2)$. The degrees are $1,1,0,2$ (in the order $m_1,w_1,m_2,w_2$).

Here is a solution for three couples, $m_1,w_1,m_2,w_2,m_3,w_3$. The edges are $(m_1,w_2),(w_1,w_2),(m_1,w_3),(w_1,w_3),(m_2,w_3),(w_2,w_3)$. The degrees are $2,2,1,3,0,4$.

Hopefully you can generalize this construction to an arbitrary number of couples. If not, you can always try running the Havel–Hakimi algorithm, trying to avoid connecting a husband to his wife.

share|improve this answer
    
Why don't w1 and m2 shake hands? According to the question, the only restriction is that a person cannot shake hands with his or her spouse. According to that rule, w1 and m2 should be allowed to shake hands. –  user2635911 Jun 8 at 19:25
3  
@user2635911 They are allowed to shake hands, but they don't have to. The question is formulated in a confusing way. What it really asks is for an undirected graph on $2n$ vertices, divided into $n$ groups of two vertices, in which two vertices forming a group are not connected, and for each $d \in \{0,\ldots,2n-2\}$, there is some vertex of degree $d$. –  Yuval Filmus Jun 8 at 19:48
    
Ahh I think I understand the question now. The restrictions are that each person cannot shake their spouse's hand and that all the answers Mrs.Smith got from everyone else is different. In this case there are 10 couples (20 people). The maximum number of hands shaken is 18 and the sum of the number of handshakes by each couple must be equal (in this case it is 18). So Mr and Mrs. Smith have both shaken 9 hands each. –  user2635911 Jun 8 at 23:18
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.