Circular Hand-holding

There are 6 people who are holding hands, such that each person is holding hands with exactly 2 other people. How many ways are there for them to do that?

Details and assumptions

Reflections count as distinct ways. Rotations count as the same way.

Each left hand grabs hold of a right hand.

A, B, C, D, E, F are arranged clockwise in a circle (with A at the 'top'), with A's left hand is holding on to B, so on and so forth. A reflection of this will be A, F, E, D, C, B are arranged clockwise in a circle (with A at the 'top'), with A's left hand holding on to F, so on and so forth. A rotation (of the first scenario) would be if C, D, E, F, A, B are arranged clockwise in a circle (with C at the 'top'), with C's left hand holding on to D, so on and so forth.


The answer is 160.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

9 solutions

Vincent Zhuang
May 20, 2014

We have two cases: Case 1. A complete cycle. We have ( 6 1 ) ! = 5 ! (6-1)!=5! ways here.

Case 2. Several cycles. Then we have at least two cycles of at least 3 people. Since there are only 6, we must have 2 cycles of 3 people each. To construct these, we can choose ( 6 3 ) \binom{6}{3} for the first group, then divide by 2 because we don't care about order [of the groups]. We multiply by (2^2) because that's how many ways we can order each group. Summing, we get our answer 120 + 40 = 160 120+40=160 .

This question had the most number of clarifications about why answer X is wrong. Students who gave 120 120 forgot to consider Case 2, and students who gave 200 200 forgot to consider Case 2 properly.

Calvin Lin Staff - 7 years ago
Bryan Tran
May 20, 2014

You can either have two groups of 3 holding hands, or a group of 6. For the groups of 3, you have 6 choose 3, to choose a group of 3, but you have to divide by 2, since the groups are indistinguishable. There are 2 ways to order each group, so it is 6 choose 3 divided by 2 times 2 times 2= 20/2 2 2=40. For the ways to arrange them in a group of 6, it is 6! divided by 6, as there are 6! ways to arrange the people, and you have to divide by 6 since there are 6 rotations. 6!/6=120. You add up the cases , 120+40=160 to arrive at the final answer.

Zara Lim
May 20, 2014

There are two ways for this to be possibe. The first is that everyone is holding hands in a circle, and the second is that there are 2 groups of three holding hands. In the first case, there are (6-1)! = 5! = 120 ways to do this. For the second case, there are {6 \choose 3}/2 = 10 ways to divide the people in two groups, and (3-1)! = 2! = 2 ways for each group to be arranged, so there are 10 \times 2 \times 2 = 40 ways for the second case. In total, there are 120+40=160 ways for 6 people to hald hands with exactly two other people.

Career Launcher
May 20, 2014

6 people holding each others hands in a large circle (6-1)! = 5! = 120

5 not possible as 1 is left put 4 not possible as 2 left out and the condition "2 other people" not satisfied

2 sets of 3 holding in 2 triangles 6C3 2 2/2 = 40

Therefore total = 120 + 40 = 160

Daniel Chiu
Nov 24, 2013

There are two possible cases, either all 6 people are in a single group holding hands, or they are in two groups of 3 people holding hands.

If all 6 are in a single group, we can treat them as sitting around a table. Once we seat the first person, there are 5 5 ways to choose the person to the left, and 4 4 ways to choose the person to the left of that person, and so on. In general, there are ( n 1 ) ! (n-1)! ways to seat n n people around a table, in particular, there are 5 ! = 120 5!=120 ways to seat 6 people.

If the 6 are split into two groups of 3, we first find there are ( 6 3 ) = 20 \dbinom{6}{3}=20 ways to choose a group of 3, and therefore two groups of 3. However, it doesn't matter which group we choose first, so there are 10 10 ways to split the 6 into two groups of 3. Now, we seat each group of 3 around a table, each with 2 ! = 2 2!=2 ways. The number of possibilities here is 10 2 2 = 40 10\cdot 2\cdot 2=40 .

The answer is 120 + 40 = 160 120+40=\boxed{160} .

Huehehehe, at first I thought that they were only on one group so I did the circular (n-1)! thing, but since it didn't work, I though the link was broken or something so I spammed it with 120. Then it came to me: It shouldn't have been THAT easy if it's in level 4. xD

Daryl Yara - 7 years, 6 months ago

In other words, I thought I broke the submit button. But nice solution, btw. :D

Daryl Yara - 7 years, 6 months ago

:-( Did not read EXACTLY TWO PEOPLE!!! Nice solution, though.

Russell FEW - 7 years, 6 months ago

Log in to reply

You are not alone. I did the same mistake :)

Lokesh Sharma - 7 years, 6 months ago

Can you explain what " it doesn't matter which group we choose first" means?

A Former Brilliant Member - 7 years, 6 months ago

Log in to reply

Choosing the first group first is the same as choosing the second group first, i.e. when you choose the first group the second group is already determined.

Sean Gee - 7 years, 6 months ago

Wait, wait, wait... I thought the same thing... but now a problem came to my mind.

Two hexagons linked in the same way rotated Two hexagons linked in the same way rotated

https://i.imgur.com/tGEPquc.png

These configurations are the same one rotated. Are we counting them only once? I don't think so!

Ariel Lanza - 7 years, 6 months ago

Log in to reply

If all 6 people are in one group, then we can treat them as around a table, and the actual spacial locations of each person is not important. The people aren't necessarily in a regular hexagon. Could you explain more why you think my solution overcounts?

Daniel Chiu - 7 years, 6 months ago

Log in to reply

Wait, what do you mean? The actual space locations are important since: "Reflections count as distinct ways. Rotations count as the same way." It should be clear what a rotation is... anyway I can rewrite it. Let's say that there are A, B, C, D, E and F arranged clockwise in a circle (with A at the 'top'). A's left hand holding on to C, C's left hand holding on to B, B's left hand holding on to D, D's left hand holding on to E, E's left hand holding on to F, F's left hand holding on to A. Then there is this other situation: A's left hand holding on to B, B's left hand holding on to D, D's left hand holding on to C, C's left hand holding on to E, E's left hand holding on to F, F's left hand holding on to A. We are just rotating clockwise, are we not? It is the same as if A changes to B, B to C and so on!

Ariel Lanza - 7 years, 6 months ago

Log in to reply

@Ariel Lanza Ok, I got what you are saying. We have different interpretations of "rotation". And you have to agree that the given example was quite misleading! It was sufficient to say that it does not matter who is sitting at the top of the table.

Ariel Lanza - 7 years, 6 months ago
Lego Haryanto
Nov 29, 2013

A cluster of 6 people (A, B, C, D, E, F), each holding two other people's hands can be pictured as permutation of these people's ids (just like the one discussed in the last paragraph of the problem statement), thus it has 6! ways of doing that. However, those configs include rotations. Since there are 6 people, then 1 configuration has 6 rotated configurations. Eliminating rotations from the 6! is as simple as dividing the result by 6, ... that is 5! = 120 ways.

The tricky part of this problem is that there are possibilities of arrangements with 2 clusters (2 group of 3 people, each holding hands with one another). An example of such is: ABC and DEF, A holding hands with B and C, B with A and C, C with A and B ... similarly for DEF.

The number of ways to have those 2-cluster configurations is C(6, 3) / 2, ... We choose 3 from 6 people and since half of them are complements of the others (i.e., ABC and DEF is the same as DEF and ABC), we divide by 2. C(6, 3) / 2 = 20 / 2 = 10.

For each of those 10 configs, each cluster of 3 people can have 2 variations: itself and its reflection. Since there are 2 clusters, each of the 10 configs can have 2 x 2 = 4 variations. This totals to 10 x 4 = 40 ways.

The answer is the number of ways for 1-cluster and 2-cluster configs: 120 + 40 = 160 .

Cluster part has been written very nicely.. :)

Snehal Shekatkar - 7 years, 6 months ago
Hungry Cap
Mar 22, 2014

We can either have a circle of 6 people or two circles of 3 people. The former gives 5!=120 combinations and the latter gives 6C3*2=40 combinations. Thus the answer is 120+40=160.

Marek Bernat
Nov 25, 2013

There are two cases. Either all the people are in one big circle or else they are in multiple circles. In the second case, each small circle must have at least three people in it (because each person holds exactly two other people). So in that case there are two small circles of three people each.

For the big circle, we have 6 ! 6! ways of how to arrange the people and there are 6 6 possible rotations that give us 5 ! 5! choices in total. Equivalently, we can put person A on top as in the example and we are free to permute the remaining people any way we will.

For the case of two small circles, note that there are ( 6 3 ) = 20 {6 \choose 3} = 20 ways of selecting people into the first circle. But actually, only 10 10 of these are different because we cannot distinguish the circles. Now for each small circle of three people, we can argue as in the second paragraph to find that there are 3 ! / 3 = 2 3! / 3 = 2 distinct arrangements.

Putting it all together, we have 5 ! + 10 2 2 = 120 + 40 = 160 5! + 10 \cdot 2 \cdot 2 = 120 + 40 = {\bf 160} ways in total.

Ashish Pathak
Nov 30, 2013

we can group either in 6 or 3 and 3 each...and not 5 ,1 or 4,2 as given in question each one holds the hands of other two persons exactly... for 6 we have 120 ways and for 3 case we have (6C3 2 2)\2=40 hence answer would be 120+40=160 ways..

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...