If there are 21 people sitting at a round table, what is lowest number of seating arrangements it would take for every person to shake hands with every other person if you could only shake hands with the person sitting on your left and right?

Mountainmage

now, I am not 100% sure about this, but I am going to go ahead and use the formula for permutations and use 21 for n, and 18 for r (since you can't shake hands with yourself, and you are shaking hands with two people). 51090942171709440000/6 which = 8515157028618240000. Remember, I am not totally sure about this. Dec 13 06, 4:39 PM

TheuntouchablE

Nope. the answer i slesst than 50. Good attempt though. Dec 13 06, 5:20 PM

zbeckabee

20? Dec 13 06, 6:15 PM

zbeckabee

No. I take that back. 21. Dec 13 06, 6:16 PM

wendypj

Ten. 21 -1 (you don't shake hands with yourself)= 20 20/2 = 10 (you shake hands with 2 people each time the seating changes). Dec 13 06, 6:22 PM

zbeckabee

Now THIS is exactly why I need someone to balance my checkbook!!! Dec 13 06, 6:24 PM

J.D.	9-10. I messed up and didnt feel like recounting so its somewhere between there I think. Dec 13 06, 6:27 PM

kevinatilusa

wendypj explained why you always need at least 10 arrangements, but left unanswered why 10 arrangements are in fact enough to get all the handshakes done. I'm know the correct answer is 10, but don't know an easy proof off the top of my head. If you're comfortable with mathematical notation and have access to a math library, I'd suggest taking a look at the book "Graph Theory" by Frank Harary. In it, he proves the following result (paraphrased): Every complete graph on 2n+1 vertices can be partitioned into n disjoint Hamiltonian cycles. In English, this is saying that if you have an odd number of people ("2n+1 vertices), then you can come up with n seating arrangements (the n "cycles") so that every pair of people (the "complete graph") sit next to each other exactly once. If you set n equal to 10, you get your result. There may be a simple argument for your case (all you'd have to do is come up with 10 different tables so that each pair sits next to each other once), but I unfortunately don't know it. Dec 14 06, 12:17 AM

zbeckabee

All you need to do is mentally take the 21 people...remove yourself. Then place yourself between the first set of two people. Shake. Move on to the second set of two people. Shake. Move on to the third set of two people. Shake. etc. Once you have done this ten time...you have gone full circle. Dec 14 06, 2:15 PM