9
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Buge
    Commented Oct 7, 2019 at 8:05
  • $\begingroup$ In some sense it's contained in the fourth rule, which says no other information (including time delay) should be transferred. $\endgroup$
    – WhatsUp
    Commented Oct 7, 2019 at 12:22
  • $\begingroup$ "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. $\endgroup$
    – Hemant Agarwal
    Commented Jun 13, 2023 at 6:56
  • 1
    $\begingroup$ @HemantAgarwal I think it's called "100 Prisoners and a Light Bulb" which can be found e.g. here. $\endgroup$
    – WhatsUp
    Commented Jun 13, 2023 at 7:14

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – WhatsUp
    Commented Oct 6, 2019 at 10:53
  • $\begingroup$ 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)? $\endgroup$
    – G0BLiN
    Commented Oct 6, 2019 at 10:59
  • $\begingroup$ 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). $\endgroup$
    – Magma
    Commented Oct 6, 2019 at 14:01
8
$\begingroup$

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.

the leader

starts out by touching the left shoulder of the person in front of him and each time thereafter when his right shoulder is touched. He keeps count of the number of times it comes back to him.

When

The leader's left shoulder is touched, he takes the total number of times he was touched (left or right) and that is the total number of people, including himself.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Congratulations! $\endgroup$
    – WhatsUp
    Commented Oct 6, 2019 at 1:01
  • $\begingroup$ I'm sorry Steve, that I took the green check back from you, but Magma has posted a better solution! $\endgroup$
    – WhatsUp
    Commented Oct 6, 2019 at 10:57
  • $\begingroup$ @WhatsUp ah well. you didn't specify you wanted to optimize the solution so I didn't look any further :) $\endgroup$
    – SteveV
    Commented Oct 6, 2019 at 12:38

Not the answer you're looking for? Browse other questions tagged or ask your own question.