A relative of mine asked once an optimization problem to our friend. None of us found the solution. Here is a formulation of the problem.

Consider 2×n2\times n board such that the squares of the form (1,i)(1,i) are empty and every square of the form (2,i)(2,i) contains one people per square, for all 1≤i≤n1\leq i\leq n. One says that two squares are adjacent if they have a common side.

If there are two adjacent squares that both has a people, they can shake hands. And if a given square has a people and its adjacent square has no people, he or she can move to the free square. People will move simultaneously so that BB can move to AA’s current position if AA is going to move to another square at the same turn. On every turn, each people can either stay on his or her place, shake hands with one of his or her neighbor if he or she is not shaking hands with another people, or move to the adjacent square.

Is there a (closed form) formula how many turns it takes if all people wants to shake hands with every other people? Or any good upper bound? Or an algorithm that gives the optimal way to shake hands and move between squares?

=================

In a a turn does a person shake with all his adyacent neighbours or just with one?

– Esteban Crespi

2 days ago

Just one. I edited the question.

– Jaakko Seppälä

2 days ago

If I have A,B,CA,B,C adjacent, and AA shakes hands with BB, I gather CC cannot shake hands with BB too in the same turn?

– Daniel Robert-Nicoud

2 days ago

@DanielRobert-Nicoud Yes. Every person should have at most one “action” in every turn.

– Jaakko Seppälä

2 days ago

1

I can foresee erotic applications for the answers in this question.

– Oppa Hilbert Style

2 days ago

=================

2 Answers

2

=================

The answers until now are insufficient in the sense that just rotating the line only lets people meet others that are an odd number of squares away. An alternate solution would be to move the rows alternately and shake hands vertically after every move. For example (I move counter clockwise)

Starting position

12345\begin{array}{|c|c|c|c|c|}

\hline

& & & & \\ \hline

1 & 2 & 3 & 4 & 5\\ \hline

\end{array}

Move lower row

51234\begin{array}{|c|c|c|c|c|}

\hline

& & & & 5 \\ \hline

\enspace & 1 & 2 & 3 & 4\\ \hline

\end{array}

Move upper row

51234\begin{array}{|c|c|c|c|c|}

\hline

& & & 5 & \\ \hline

\enspace & 1 & 2 & 3 & 4\\ \hline

\end{array}

Move lower row

54123\begin{array}{|c|c|c|c|c|}

\hline

& & & 5& 4 \\ \hline

\enspace & \enspace & 1 & 2 & 3\\ \hline

\end{array}

Move upper row

54123\begin{array}{|c|c|c|c|c|}

\hline

& & 5 & 4& \\ \hline

\enspace &\enspace & 1 & 2 & 3\\ \hline

\end{array}

Move lower row

54312\begin{array}{|c|c|c|c|c|}

\hline

& & 5 & 4& 3 \\ \hline

\enspace & \enspace & & 1 & 2\\ \hline

\end{array}

Move upper row

54312\begin{array}{|c|c|c|c|c|}

\hline

& 5 & 4 & 3& \\ \hline

\enspace &\enspace & & 1 & 2\\ \hline

\end{array}

This way everybody meets all the others once vertically. The total number of steps would then be bounded by 2(n−2)2(n-2) position swaps plus 2(n−2)+12(n-2) + 1 handshakes, which gives a total of 4(n−2)+14(n-2) + 1 actions.

Nice solution. I was trying to think of something to join the problems and solve part 1 and 2 with the same algorithm, but this is neat.

– O. Von Seckendorff

2 days ago

Thank you, unfortunately my original comment was incorrect.

– Marc

2 days ago

Good thing you corrected. I’m personally pretty bad with this type of algorithms, so I can appreciate it’s neatness but can’t be sure if it’s good to go.

– O. Von Seckendorff

2 days ago

Can we prove that, up to a constant, 4n4n is optimal? That is, it cannot be done in (4−ϵ)n+k(4 – \epsilon)n + k for any ϵ,k\epsilon,k?

– Mees de Vries

2 days ago

I can imagine one possible algorithm, not knowing if it’s optimal :

at turn 11, (2,1)(2,1) goes to (1,1)(1,1), every (2,i)(2,i) goes to (2,i−1)(2,i-1) for 2≤i≤n2\le i\le n. (1,1)(1,1) shakes hand with (2,1)(2,1).

at turn 22, (1,1)(1,1) goes to (1,2)(1,2), (2,1)(2,1) goes to (1,1)(1,1) and every (2,i)(2,i) goes to (2,i−1)(2,i-1) for 2≤i≤n−12\le i\le n-1. (1,1)(1,1) shakes hand with (2,1)(2,1) and (1,2)(1,2) with (2,2)(2,2).

… repeat the cycle until the (2,1)(2,1) reaches (1,n−1)(1,n-1).

This leads to n−1n-1 turns of handshaking…

edit : I realize now that this doesn’t work : each step makes people encounter someone 2\mathbf2 steps further, not one ! I realized this when I computed the number of effective handshakes : p2p^2 if n=2pn=2p, which is definitely not enough 🙁

I will give this more thoughts during my dentist session 😉

end edit

To compute the minimal theoretical number of moves, you should solve (n/2)k≥n(n−1)/2(n/2)^k\ge n(n-1)/2, but I think this can be tricky with the rule exposed, if I understand it correctly.

I think this is the same solution that Daniel gave.

– O. Von Seckendorff

2 days ago