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.
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.
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.
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.
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
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 ways to choose the person to the left, and 4 ways to choose the person to the left of that person, and so on. In general, there are ( n − 1 ) ! ways to seat n people around a table, in particular, there are 5 ! = 1 2 0 ways to seat 6 people.
If the 6 are split into two groups of 3, we first find there are ( 3 6 ) = 2 0 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 1 0 ways to split the 6 into two groups of 3. Now, we seat each group of 3 around a table, each with 2 ! = 2 ways. The number of possibilities here is 1 0 ⋅ 2 ⋅ 2 = 4 0 .
The answer is 1 2 0 + 4 0 = 1 6 0 .
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
In other words, I thought I broke the submit button. But nice solution, btw. :D
:-( Did not read EXACTLY TWO PEOPLE!!! Nice solution, though.
Can you explain what " it doesn't matter which group we choose first" means?
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.
Wait, wait, wait... I thought the same thing... but now a problem came to my mind.
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!
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?
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!
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.
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.. :)
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.
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 ! ways of how to arrange the people and there are 6 possible rotations that give us 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 ( 3 6 ) = 2 0 ways of selecting people into the first circle. But actually, only 1 0 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 distinct arrangements.
Putting it all together, we have 5 ! + 1 0 ⋅ 2 ⋅ 2 = 1 2 0 + 4 0 = 1 6 0 ways in total.
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..
Problem Loading...
Note Loading...
Set Loading...
We have two cases: Case 1. A complete cycle. We have ( 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 ( 3 6 ) 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 1 2 0 + 4 0 = 1 6 0 .