8
$\begingroup$

I have found this puzzle on internet. 40 persons sit in a round table . All of them are either sane or crazy. When you ask a person "is the person sitting to your right sane or crazy?" a sane person will always answer correctly and a crazy preson will answer randomly.

The only thing we know is that the number of crazy persons is less than 40. What is the maximum possible number of crazy persons such that after hearing all the answers you will be able to trace at least one sane person?

Its a tough one, i know. Haven't been able to solve it.

Improve this question
$\endgroup$
10
  • 3
    $\begingroup$ You should try to provide proper attribution for your puzzle. Can you be more specific about the source rather than "on internet"? $\endgroup$
    – hexomino
    Jun 12, 2020 at 9:56
  • 1
    $\begingroup$ I have seen it in a site with riddles and logical puzzles about a month ago but i don't remember which one. $\endgroup$
    – Craftsman
    Jun 12, 2020 at 10:05
  • $\begingroup$ Also i have put "logical deduction" as a tag although i am not sure which would fit better. $\endgroup$
    – Craftsman
    Jun 12, 2020 at 10:29
  • $\begingroup$ How many questions are we allowed to do? Once per person? Infinite per person? $\endgroup$
    – George Menoutis
    Jun 12, 2020 at 10:37
  • 1
    $\begingroup$ I'm almost sure I've seen a version of this puzzle here before, but all my searches have come up empty. $\endgroup$
    – Jaap Scherphuis
    Jun 12, 2020 at 11:35

1 Answer 1

Reset to default
8
$\begingroup$

Edit: I've removed the first part because, as pointed out in the comments, it is superfluous if the maximum is specified.

The maximum possible number of crazy people such that after hearing all the answers you will be able to trace at least one sane person is

$10$

Proof of upper bound

Suppose we have $11$ crazy people and we divide the people into consecutive groups of five with the ordering in seven of the groups being "sane, sane, sane, sane, crazy" and the eighth group being "crazy, crazy, crazy, crazy, sane" (in left-to-right order). Then it is logically consistent for the quintet in each group to respond "sane, sane, sane, crazy, sane" in that order.
However, given these responses, we would not know which quintet is where. Therefore we cannot pin down a single sane person because we might pick out the deviant quintet.
This method can be easily generalised to higher numbers.
Hence, the maximum is less than $11$.

Proof of lower bound

If there are, at most, $10$ crazy people then we are guaranteed a string of people with the pattern "sane, sane, sane, crazy" (in left-to-right order) somewhere in the circle and so we are guaranteed that there is at least a row of three people saying "sane, sane, crazy" in response to the question. Consider the consecutive group of people with the longest string of "sane" responses followed by a "crazy" response. Suppose this represents a string of $k$ people (where we know $2<k$).
I claim that the person who says "crazy" at the end of this group is sane.

To prove this, suppose that this person is crazy. Then, inductively we see that the other $k-1$ people preceding this are also crazy. This means that, in the remaining group of $40-k$, there are at most $10-k$ people who are crazy.
However, this means that there must be a string of size longer than $k$ sane people in a row somewhere in the remaining group. This assertion is not immediate but can be verified by checking through the different possible values of $k$.
This means that there is a string of responses of the form "sane, sane, sane,..., sane, crazy" of length greater than $k$, which is a contradiction.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I think "anticlockwise" is misleading. Are you looking from top or from the bottom? Do people sit faces to centre or backs to centre? It's probably better to operate in terms of the OP and say "person to the right" and "person to the left" $\endgroup$
    – Andrew Savinykh
    Jun 12, 2020 at 20:54
  • $\begingroup$ "This would make the maximum zero". How does it? You can filter out one of the two solutions you are comparing even with the maximum of 38 (because you stipulate that all but one will be crazy, which makes in 39, so with maximum of 38 it would not represent a valid solution). $\endgroup$
    – Andrew Savinykh
    Jun 12, 2020 at 21:08
  • $\begingroup$ @AndrewSavinykh Ah yes, you make a good point, if just the maximum is specified then we can use the same strategy. This bypasses the first part altogether. Will change the language appropriately. $\endgroup$
    – hexomino
    Jun 12, 2020 at 23:21
  • $\begingroup$ Cool proof, as always, hexomino. $\endgroup$
    – justhalf
    Jun 14, 2020 at 3:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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