# How many people are there?

This is a variation of an old puzzle.

The game starts with several people sitting in a circle, everyone facing the back of another person. They are all wearing blind folds, so nobody can see anyone else. In particular, nobody can see how many people are there in total.

One of them is the leader. They win the game if the leader figures out the exact number of people in the circle.

They are only allowed to communicate with each other under the following rules:

• When the game starts, the leader is allowed to touch the person in front of him.
• After that, a person who is touched by another person is allowed to touch the person in front of him.
• Whenever a person touches another person once, he is not allowed to touch anymore, until he himself is touched again.
• Every touch can be either on the left shoulder or on the right shoulder, but should contain no more information than "left or right" (e.g. small gestures/knocks/touch power/which hand touches/etc. are all IRRELEVANT).
• Other than the touch as specified above, no communication is allowed.

As usual, before the game starts they are allowed to agree on a strategy. What strategy can they use to win the game?

This is a logical puzzle and not lateral thinking.

It's also impossible to know the number of people when they discuss the strategy: it could happen that only part of them are selected to participate in the game.

• You probably also want to say people aren't allowed to wait between getting touched and giving on the touch. Otherwise there could be timing-based answers.
– Buge
Commented Oct 7, 2019 at 8:05
• In some sense it's contained in the fourth rule, which says no other information (including time delay) should be transferred. Commented Oct 7, 2019 at 12:22
• "This is a variation of an old puzzle." Do please post the old puzzle as well, if you feel that it would be interesting enough. Commented Jun 13, 2023 at 6:56
• @HemantAgarwal I think it's called "100 Prisoners and a Light Bulb" which can be found e.g. here. Commented Jun 13, 2023 at 7:14

Here's a solution that uses logarithmically many rounds instead of SteveV's linearly many.

The leader touches the left shoulder of the next player on odd rounds (first round is round 1), and the right shoulder on even rounds.

Every other player now always touches the same shoulder he was just touched, except if he has never touched a right shoulder before. In that case, if it's an odd round, he touches the opposite shoulder he was touched, and if it's an even round, he touches the left shoulder.

At the end of odd rounds, the leader writes down a new binary digit in his mind, from right to left, 0 if he was touched on the left shoulder, 1 if he was touched on the right shoulder.

When the leader gets touched on the right shoulder at the end of an even round, the binary number he wrote down denotes the number of other players in the game. The leader calls out one more than that to win the game.

Alternate, more efficient strategy, assuming the leader knows an upper bound on the number of players (maybe from the strategy meeting):

Use the same strategy as before, but skip the even rounds. The leader calls out as soon as he knows he can't write down any more 1s.

• This is indeed a more clever solution to the puzzle! One recognizes the famous algorithm en.m.wikipedia.org/wiki/Exponentiation_by_squaring. However, I think whether the second strategy is more efficient is debatable: while the first only depends on the number of people participating in the game, the second depends on the known upper bound. Commented Oct 6, 2019 at 10:53
• Maybe clarify the second part of the second sentence? Reading "In that case, if it's an odd round, he touches the opposite shoulder, and if it's an even round, he touches the left shoulder.", it seems to mean that "on even rounds, always touch left when touched ("transmit left regardless of signal"), on odd rounds, touch opposite shoulder ("invert the signal")" - is that the meaning? What happens on the first time a player is touched on right (transmit signal or invert on odd/left on even)? Commented Oct 6, 2019 at 10:59
• Yes, your reading is correct. The first time a player is touched on the right side, he hasn't touched a right shoulder before, so he should do the special case (invert on odd, left on even). Commented Oct 6, 2019 at 14:01

They decide that

if they are touched on the right shoulder, they touch the right shoulder of the person in front of them.

and

if they are touched on the left shoulder, they 1) touch the right shoulder of the person in front of them this time but 2) touch the left shoulder of the person in front of them every subsequent time.