Can two groups of N people find each other around a circle? [closed]

Question

This is an algorithmic problem and I'm not sure it has a solution. I think it's a specific case of a more generic computer science problem that has no solution but I'd rather not disclose which one to avoid planting biases. It came up from a real life situation in which mobile phones were out of credit and thus, we didn't have long range communications.

Two groups of people, each with 2 people (but it might be true for N people) arranged to meet at the center of a park but at the time of meeting, the park is closed. Now, they'll have to meet somewhere else around the park. Is there an algorithm each and every single individual could follow to converge all in one point?

For example, if each group splits in two and goes around and when they find another person keep on going with that person, they would all converge on the other side of the park. But if the other group does the same, then, they wouldn't be able to take the found members of the other group with them. This is not a possible solution.

I'm not sure if I explained well enough. I can try to draw a diagram.

Answer 1

Deterministic Solution for N > 1, K > 1

For N groups of K people each.

Since the problem is based on people whose mobile phones are out of credit, let's assume that each person in each group has their own phone. If that's not acceptable, then substitute the phone with a credit card, social security, driver's license, or any other item with numerical identification that is guaranteed to be unique.

In each group, each person must remember the highest number among that group, and the person with the highest number (labeled leader) must travel clockwise around the perimeter while the rest of the group stays put.

After the leader of each group meets the next group, they compare their number with the group's previous leader number.

If the leader's number is higher than the group's previous leader's number, then the leader and the group all continue along the perimeter of the park. If the group's previous leader's number is higher, then they all stay put.

Eventually the leader with the highest number will continue around the entire perimeter exactly 1 rotation, collecting the entire group.

Deterministic solution for N > 1, K = 1 (with one reasonable assumption of knowledge ahead-of-time)

In this case, each group only contains one person. Let's assume that the number used is a phone number, because it is then reasonable to also assume that at least one pair of people will know each other's numbers and so one of them will stay put.

For N = 2, this becomes trivially reduced to one person staying put and the other person going around clockwise.

For other cases, the fact that at least two people will initially know each other's numbers will effectively increase the maximum K to at least 2 (because the person or people who stay put will continue to stay put if the person they know has a higher number than the leader who shows up to meet them), but we still have to introduce one more step to the algorithm to make sure it will terminate.

The extra step is that if a leader has continued around the perimeter for exactly one rotation without adding anyone to the group, then the leader must leave their group behind and start over for one more rotation around the perimeter. This means that a leader with no group will continue indefinitely until they find someone else, which is good.

With this extra step, it is easy to see why we have to assume that at least one pair of people need to know each other's phone numbers ahead of time, because then we can guarantee that the person who stays put will eventually accumulate the entire group.

Feel free to leave comments or suggestions to improve the algorithm I've laid out or challenge me if you think I missed an edge case. If not, then I hope you liked my answer.

Update

For fun, I decided to write a visual demo of my solutions to the problem using d3. Feel free to play around with the parameters and restart the simulation with any initial state. Here's the link:

https://jsfiddle.net/patrob10114/c3d478ty/show/

Key

• black - leader
• white - follower
• when clicked
  • blue - selected person
  • green - known by selected person
  • red - unknown by selected person

Note that collaboration occurs at the start of every step, so if two groups just combined in the current step, most people won't know the people from the opposite group until after the next step is invoked.

Answer 2

They should move towards the northernmost point of the park.

Answer 3

I'd send both groups in a random direction. If they went a half circle without meeting the other group, rerandomize the directions. This will make them meet in a few rounds most of the time, however there is an infinitely small chance that they still never meet.

Answer 4

It is not possible with a deterministic algorithm if

• • we have to meet at some point on the perimeter,
• • we are unable to distinguish points on the perimeter (or the algorithm is not allowed to use such a distinction),
• • we are unable to distinguish individuals in the groups (or the algorithm is not allowed to use such a distinction),
• • the perimeter is circular (see below for a more general case),
• • we all follow the same algorithm, and
• • the initial points may be anywhere on the perimeter.

Proof: With a deterministic algorithm we can deduce the final positions from the initial positions, but the groups could start evenly spaced around the perimeter, in which case the problem has rotational symmetry and so the solution will be unchanged by a 1/n rotation, which however has no fixed point on the perimeter.

Status of assumptions Dropping various assumptions leads, as others have observed to various solutions:

• Non-deterministic: As others have observed, various non-deterministic algorithms do provide a solution whose probability of termination tends to certainty as time tends to infinity; I suspect almost any random walk would do. (Many answers)
• Points indistinguishable: Agree on a fixed point at which to meet if needed: flyx’s answer.
• Individuals indistinguishable: If there is a perfect hash algorithm, choose those with the lowest hash to collect others: Patrick Roberts’s solution.
• Same algorithm: Choose one in advance to collect the others (adapting Patrick Roberts’s solution).

Other assumptions can be weakened:

• Non-circular perimeter: The condition that the perimeter be circular is rather artificial, but if the perimeter is topologically equivalent to a circle, this equivalence can be used to convert any solution to a solution to the circle problem.
• Unrestricted initial points: Even if the initial points cannot be evenly spaced, as long as some points are distinct, a topological equivalence (as for a non-circular perimeter) reduces a solution to a solution to the circular case, showing that no solution can exist.

I think this question really belongs on Computer Science Stack Exchange.