15
$\begingroup$

A group of 30 knights and jokers are seated around a table. The knights always tell the truth while the jokers sometimes tell the truth and sometimes lie. They all answer to the question “what is the person sitting on your right? A knight or a joker?”. We know beforehand that the number of jokers does not exceed a specific number.

What is the maximum possible value of this number, so that, knowing every answer of the 30 people, we can be in a position to identify at least one knight?

I really don't know how to start. I understand it must be solved by using the pigeonhole principle and combinatorics.

Any clues? Thank you very much!

$\endgroup$
  • 5
    $\begingroup$ The place to start is to think about what happens if the number is $1$. If there are no jokers, what are the answers? If there is one joker, there are two possibilities for the answers. What are they? Who can you point to that you know is a knight? Now suppose the number is $2$. Does your strategy for $1$ still work? $\endgroup$ – Ross Millikan Feb 14 at 3:46
  • $\begingroup$ @RossMillikan you are right - I edited the question. $\endgroup$ – Salem Ohio Feb 14 at 3:59
  • 6
    $\begingroup$ For starters, it definitely must be less than $15$. Take the case of Knight and joker always alternating (Knight, joker, Knight, joker etc...but this is unknown to us). Suppose in this particular case the jokers always lied for some particular reason. Then every answer would be "Joker", leaving us with no leads. $\endgroup$ – WaveX Feb 14 at 4:24
6
$\begingroup$

There are two interpretations of this question. If it is taken to mean "What is the maximum number of jokers so that there is some configuration which identifies at least one knight", then our answer is 29 - if all but one person says "Knight", the sole dissenter is the only knight present.

If it is taken to mean "What is the maximum number of jokers so that all possible answers reveal at least one person as a knight?", then the problem is rather more difficult.

One can place an upper bound of 8: if you hear responses of the form KKKKJKKKKJKKKKJKKKKJKKKKJKKKKJ, then it is possible for the group's identities to be JJJJJKKKKKJKKKKJKKKKJKKKKJKKKK or any multiple-of-5 rotation thereof, so this is a situation where a cap of 9 does not suffice.

However, we can also place a lower bound of 8.

Observe that a string of $n$ consecutive people saying "joker" forces at least $\lceil\frac{n}2\rceil$ of the people in that string of jokers and the following knight to be jokers. (E.g., if people say in order JJJJJK, 3 of those 6 (at least) are jokers.)

Observe also that if $n$ consecutive people say "knight", either the last of them really is a knight or every one of them is a joker.

This means that, if we note the sizes of consecutive blocks of joker-sayers $c=(c_1,c_2,\ldots,c_m)$, we can locate $\sum_{i=1}^m\left\lceil\frac{c_i}2\right\rceil$ of the jokers. Denote by $s$ the total number of joker-sayers. Of the remaining $30-s$ knight-sayers, at least one of the $m$ consecutive blocks of them is of size at least $\lceil\frac{30-s}m\rceil$. If the final knight-sayer is a joker, then this gives us $\lceil\frac{30-s}m\rceil-1$ additional jokers not counted by the previous sum (all of those knights except the first). If this puts us above the maximum 8 jokers, we will know that this final knight-sayer must really be a knight, and so will have identified the desired individual.

Finally, note that if we have an even number of consecutive joker-sayers and exactly half are jokers, then the knight-sayer following this block must really be a knight, so cases where all $c_i$ are even give us a "free" point in our sum (because the longest block of knight-sayers is forced to follow one of these even-sized joker-sayer blocks).

Given this setup, it will suffice to show that every tuple $(c_1,c_2,\ldots,c_m)$ has such a sum of at least 9.

Our total number of jokers is greater than or equal to each of $\lceil(30-s)/m\rceil+m-1$ and $\lceil(30-s)/m\rceil+\frac{s}2-1$. If we simply check this for all possible values of $m\le s$, we find that the only options are $(m,s)=(5,10)$ or $(6,12)$, which force us to have $c=(2,2,2,2,2)$ or $c=(2,2,2,2,2,2)$ respectively. But either of these fail to the "free joker" condition given earlier, so in fact neither work. Thus the answer is an 8 joker cap in order to always solve the puzzle.

The casework in establishing the lower bound for this proof is pretty ugly - I would be curious to see if anyone else can improve on it.

$\endgroup$
  • 1
    $\begingroup$ It seems like we can locate $$\sum_{i=1}^m\left\lceil\frac{c_i+1}2\right\rceil$$ of the jokers from what has gone before, because you counted the "following knight" in the $n$ in $\lceil\frac n2\rceil$. I don't know if this makes the case work easier. $\endgroup$ – saulspatz Feb 14 at 14:34
  • $\begingroup$ @saulspatz so does this change the maximum possible number of jokers? $\endgroup$ – Chen Aavaz Feb 15 at 12:31
  • $\begingroup$ Btw I agree with the second interpretation of @RavenclawPrefect. $\endgroup$ – Chen Aavaz Feb 15 at 12:33
  • $\begingroup$ @ChenAavaz I was responding to the last sentence in the answer. $\endgroup$ – saulspatz Feb 15 at 13:45
  • $\begingroup$ You seem to assume that the jokers ALWAYS lie. The problem says they SOMETIMES lie. $\endgroup$ – richard1941 Feb 19 at 2:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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