Puzzle: N person sitting at the round table. There are no handshakes without crossing any other handshakes.

Question

We have Russian people sitting at the round table. Anyone can shake hands with any other person. How can these Russian people make handshakes so that no two handshakes cross each other.

I found this puzzle in the technical interview forum, but did not answer. One way that I could think of is to find all the permutations of the handshakes, and then check each permutation whether it satisfies or not.

Someone can suggest any other solution that is more efficient.

@edit: Clarification from comments: N will be even.

Answer 1

I would try a split and win solution. if person 1 shakes hands with person x, he divides the remaining people into two groups, which can be considered as sitting at two round tables.

Answer 2

The solution is pretty easy to set up as a Python function (Python 3.3+):

@lru_cache(maxsize=None) # memoize def num_handshakes(n): if n % 2 == 1: return 0 elif n == 0: return 1 res = 0 for i in range(0, n, 2): res += num_handshakes(i) * num_handshakes(n-2-i) return res 

Example:

 >>> num_handshakes(8) 14 

This basically implements @Buhb's approach for separation and subjugation. Another solution, as soon as we find out the answer, is related to Catalan numbers :

 from math import factorial as fac def catalan(n): return fac(2*n) // fac(n+1) // fac(n) def num_handshakes(n): if n % 2 == 1: return 0 return catalan(n//2) 

Answer 3

I would try a split and win solution. if person 1 shakes hands with person x, he divides the remaining people into two groups, which can be considered as sitting at two round tables.

@Buhb is right. This is a recurrence relation

 f(n) = sum( f(i-2) + f(ni) for i in range(2, n)) 

Or in code

 def f(n): if n == 0: # zero people can handshake return 1 if n == 1: # it takes two to tango return 0 ways = 0 # what if person 1 shakes with person i ? for i in range(2, n+1): # splits table into independent sets 2 .. i-1 and i+1 .. n ways += f(i-2) * f(ni) return ways 

An odd number of people cannot fry, but the first few even values ​​of f are 1, 2, 5, 14, 42

Search in the encyclopedia of integer sequences, it looks like the famous Catalan numbers http://oeis.org/A000108

Are the sequences the same or do they just start the same way? They are identical. Confirmed my math book - our recurrence relation, which also defines f for Catalan numbers https://en.wikipedia.org/wiki/Catalan_number#Properties

Answer 4

What is going back?

• Start with one handshake and find more possible handshakes. if no more non crossing handshakes are possible, backtrack. Continue until no branches of your search tree are expanded using non crossing handshakes.
• All the vertices of the resulting search tree are non crossing handshakes.

Since your table is round (symmetry), you can optimize the problem by assuming that person 0 always part of the largest handshake.

Answer 5

I think this may be a solution even for n=2m.

Point people around the circle from 1 to 2 m.

In round j, 1≤j≤m, person j shakes hands with person j+1 , and all other handshakes are "parallel" to this (therefore j-1 with j + 2, j-2 with j + 3, etc. - everywhere, these labels are interpreted modulo n, if necessary) . At the end of these rounds everyone shook hands with all the odd number of people.

In the round m + j, 1≤j≤m, j trembles with j + 2, and all other handshakes are parallel (therefore j-1 with j + 3, j-2 with j + 4, etc.). This processes all pairs with an even number of people. Thus, the total amount is 2 m.

As noted in the statement of the problem, 2m-1 rounds are impossible, so the answer is 2m.

The odd case is even simpler. In round j, man j sits, and j-1 greets j + 1, j-2 greets j + 2, etc., Using n rounds again.

Answer 6

Here Result corresponds to the Catalan number series. here is my code in c ++

 #include <bits/stdc++.h> using namespace std; long c[17] ; void sieve(){ c[0] = 1; c[1] = 1; for(int i =2;i<=15;i++){ for(int j =0;j<i;j++){ c[i] += c[j]*c[ij-1]; } } } int main(void){ sieve(); int t; scanf("%d",&t); while(t--){ int n ; scanf("%d",&n); if(n%2!=0){ cout<<"0"<<endl; } else{ n = n>>1; cout<<c[n]<<endl; } } return 0; } 

Answer 7

people can do handshakes with (n-1)+(n-2)+.....+1 ways This is for linear

n ways for a round table