A handshake problem with two parties

Question

This problem was on a math contest some months ago:

Two countries agreed to resolve a border issue by talk and have sent (each of them) a delegation of $n>2$ diplomats. For each diplomat, strict protocoll regulates the number of delegacy members from the other contry's contingent that he or she needs to shake hands with. This number is 1 for the shortest diplomats of each contingent, 2 for the next ones in tallness and so on; the only exception being both delagations' tallest diplomats, who need to shake hands with $n-1$, rather than with $n$ members of the other delegation. Give an explicit formula for the number of ways the regulations of the protocoll can be met!

I could not get a grip on this problem. But I have calculated it for some small $n$, and my guess is, that the answer is $F_{2n-1}$, where $F_n$ is the $n$th Fibonacci number. I have looked for formulas on OEIS, but I could not use them on this problem.

I would be grateful if you could give me some hints on how to solve this problem.

Answer 1

I have not run through all the details, but I think you can split in 2 cases.

If the top two delegates of your party do not shake with the same set of people, then you can remove your top delegate and one handshake of your second highest delegate, as well as the opposite side's bottom delegate, and thereby reduce it to the $n-1$ case.

If the top two delegates of your party do shake hands with the same set of people, remove them both, as well as two of the bottom three delegates from the other party to reduce it to the $n-2$ case.

[Edit: Note the following is incorrect - see comments]
In the first case there are $n$ arrangements that reduce to the same smaller case, depending on which person the (removed) top delegate did not shake hands with. Similarly, in the second case I think there are always $1$ or $2$ arrangements that reduce to the same smaller case, but I'd have to spend more time to work out how often each occurs. The recurrence relation you then get is $T_n= n T_{n-1} + c T_{n-2}$, where $c$ is some fraction between $1$ and $2$.

Answer 2

Hint

Let us label the people $a_1,a_2,\dots,a_n$ in one delegation, and $b_1,b_2,\dots,b_n$ in the other. Here, $a_i$ must shake hands with $i$ people for $1\le i\le n-1$, while $a_n$ must shake hands with $n-1$ people, and similarly for $b_i$.

Let $T_n$ be the number of ways for everyone to shake hands. You can get a recurrence for $T_n$ by considering who delegate $a_1$ shake hands with. For each possible person $b_i$ that $a_1$ shakes with, there will be a number of forced handshakes. If you then eliminate all people whose handshakes requirements are filled, then you get a smaller version of the same problem remaining, which gives a recurrence. You can then show that $F_{2n-1}$ obeys the same recurrence.

Figuring out the forced handshakes is the fun and tricky part. If above is all the hint you need, then good. Otherwise, I have illustrated the forced handshakes for four of the cases below hidden behind spoiler blocks.

1. If $a_1$ shakes hands with $b_n\dots$

   then $b_{n-1}$ cannot shake hands with $a_1$, so $b_{n-1}$ must shake with everyone else. Now, if you remove people $a_1$ and $b_{n-1}$ and their handshakes, while decreasing the required handshakes for the remaining delegates appropriately, then satisfying the remaining delegates ($a_2,a_3,\dots,a_{n}$ and $b_1,\dots,b_{n-2},b_n$) is exactly the smaller problem with $n-1$ delegates on each side.

2. If $a_1$ shakes hands with $b_{n-1}\dots$

   Same as idea as previous case. We recurse to $T_{n-1}$.

3. If $a_1$ shakes hands with $b_{n-2}\dots$

   Now, both $b_n$ and $b_{n-1}$ shake hands with everyone besides $a_1$. This means $a_1,b_{n-1}$ and $b_n$ are satisfied. Furthermore, $a_2$ is satisfied, since they shook hands with $b_{n-1}$ and $b_n$. Removing $a_1,a_2,b_{n-1}$ and $b_n$ leaves the smaller problem with $n-2$ delegates, counted by $T_{n-2}$.

4. If $a_1$ shakes hands with $b_{n-3}\dots$

   As before, both $b_n$ and $b_{n-1}$ shake hands with everyone besides $a_1$. This means that $a_2$ is satisfied (again). This means that $b_{n-2}$ must shake hands with everyone except $a_1$ and $a_2$, since $b_{n-2}$ needs $n-2$ handshakes. Furthermore, $a_3$ is now satisfied. Removing $a_1,a_2,a_3,b_{n-2},b_{n-1},b_n$ leaves a smaller problem with $n-3$ delegates, counted by $T_{n-3}$.

You can figure out how the pattern continues. The resulting recurrence, again behind a spoiler block since this is practically the answer:

$T_n=2T_{n-1}+T_{n-2}+T_{n-3}+\dots+T_1$