Liar scale 2: Duel of perfect logicians.
James and Jane are two perfect logicians. However, their technician friends insist that one of them must be better than the other. They then set up a contest using an unusual device. One technician makes a scale that is remotely controlled. When objects are put in the two pans, it will send the result of the weighing to a separate laptop (the scale doesn't move). Then, the person operating the laptop can send an output back to the scale about which pan it should consider heavier, or whether both pans should be of equal weight. The scale will then move according to the instruction sent by the laptop, even if the instruction is not the same with the actual weighing result.
Both James and Jane are told about this strange device. They are asked to play a game. Jane is given 10 balls numbered 1-10. One of the ball weighs more than the other, but only James is told which one. Jane operates the scale, while James operates the laptop. James can see the actual weighing result, but Jane cannot. Jane can only see the result sent by James. James is restricted by the rule known to both of them: That he cannot make five consecutive lies when sending his weighing result. But other than that rule, he's free to send any result he wants (but he still must send a result after each weighing). Jane can decide what to balance and is free to use any amount of balancing she needs. Since Jane is perfect logician, and she knows that James is also perfect logician, she will give up if she no longer can do anything.
On the first day, Jane is asked to weigh the balls. To win, she needs to lower the number of suspected balls into five balls. But since her technician friends are watching (and they are also good at logic!), she cannot guess randomly and has to provide justifiable argument. James can use any algorithm to give output to confuse Jane, while Jane can use any algorithm of weighing the balls.
On the second day, the number is reshuffled, and only James know which is the heavier ball. Jane and James restart the game again, but now Jane needs to lower the number of suspected balls to four balls.
Who wins in each of these days?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
It seems like James has an advantage, but we will later see that Jane can actually force James to make moves that are almost robotic. During each weighing, there are three possible results. A is heavier than B, A equals B, or B is heavier than A. In each result, we need to look at all three groups: The one in pan A, the one in pan B, and the one uninvolved with the weighing. Since the abnormal ball is heavier, then the three result means: A heavier than B = affirming that the abnormal is in pan A, denying that the abnormal is in pan B, and denying that the abnormal is in group C (not balanced) A lighter than B = affirming that the abnormal is in pan B, denying that the abnormal is in pan A, and denying that the abnormal is in group C (not balanced) A equals B = affirming that the abnormal is in group C (not balanced), denying that the abnormal is in pan A, and denying that the abnormal is in pan B. So, in each weighing, Jane needs to create three groups and let James decide which one group is "affirmed", and which two groups are "denied".
However, if we seek to shrink the number of suspects by "affirmation", we need to understand that "affirming" a group means considering all possible abnormals in five consecutive weighing. Even if ball number 1 is only included once in the affirmed group during a single balancing among 5 consecutive balancing, it still needs to be considered as a suspect. All James need to do is to affirm every single balls at least once in every 5 consecutive balancing. So what Jane needs to do is to ensure there is a ball that is not affirmed in 5 weighing, or in other words, denied in 5 consecutive weighing (then she can exclude that single ball from the suspects). On the other hand, if James can create algorithm to ensure some number of balls can always become a suspect (always get affirmed in every 5 balancing), he can win.
Now we can see that James can definitely win in day 2. Without loss of generality, we can consider the abnormal as ball 1. James can indefinitely maintain 5 balls as suspects if he does: Balancing 1: Affirming group containing ball 1 (truth) Balancing 2: Affirming group containing ball 2 (truth/lie?) Balancing 3: Affirming group containing ball 3 (truth/lie?) Balancing 4: Affirming group containing ball 4 (truth/lie?) Balancing 5: Affirming group containing ball 5 (truth/lie?) Balancing 6: Affirming group containing ball 1 (truth) Balancing 7: Affirming group containing ball 2 (truth/lie?) ... and so on. That way, Jane will never be able to exclude any of ball 1-5. And James is sure to say truth at least once in every 5 consecutive balancing.
But is it possible for James to maintain 6 balls as possible suspects indefinitely? The answer is NO. We will prove that Jane can always exclude a ball as long as there are 6 suspects or more. We can just consider ball 1-6 and ignore the rest of the suspects to prove this. We can just pretend that there are only 6 suspects left.
Jane can balance ball 1 against ball 2 repeatedly. If james send the result that it is equal five times, it's obvious that these two balls will be excluded. So at some time, James will definitely send result that the two pans weigh differently. This means that only 1 ball is affirmed while the other 5 are denied. As Jane needs to have as few ball affirmed as possible, it is a good start. We can ignore the previous balancing and consider it balancing 1. However, the condition cannot be repeated in the algorithm as James will find a way to affirm the other group. If we want to repeat it, we may need to do counterproductive action instead.
After balancing 1: 1 ball is affirmed, 5 balls are denied once
Now we take a look at James. In every five balancing, James need to affirm all 6 balls. If after 4th balancing, there are two suspects which are never affirmed, Jane will win, as she will put these two in different group for fifth balancing and James can only affirm one of them. So after 4th balancing, James have to ensure that only 1 ball at most is not affirmed. To ensure such condition, James have to ensure that after 3rd balancing, there are at most two balls not yet affirmed. Following this logic, after 2nd balancing, he has to ensure at most 4 balls remain not affirmed. It seems doable at first, but the strict condition for James may affect balancing 6, 7 and so on.
Now we see Jane again. As Jane's purpose is to exclude suspects by getting consecutive denial, an affirmation can be considered a reset as if it has gotten 0 "denial score".
In 2nd balancing, Jane can group the affirmed ball with 1 ball which is denied once, while the other 4 balls that are denied once are split into other two groups. The possible results are: 1. 2 balls which has been denied once get affirmed (reset as if they have never got denial), 1 ball which has been affirmed once get 1 denial, and 3 balls have gotten 2 denial. 2. 1 ball which has been affirmed get affirmed again, 1 ball which has gotten 1 denial is reset to 0 by affirmation, and 4 balls are getting denied twice. These two results equal: 2 balls getting 0 denial, 1 ball getting 1 or 2 denial, and 3 balls getting 2 denial.
As James is the one selecting the group getting affirmation, we can consider the worst result, such that Jane gets 2 balls with 0 denials, 1 ball with 1 denial, and 3 balls with 2 denials. Even if James choose the other way, the next algorithm can still be applied as ball with higher denial score only replace the ball with lower score without disadvantaging Jane.
Before 3rd balancing, we have 2 balls with 0 denials, 1 ball with 1 denial, and 3 balls with 3 denials. Now Jane needs to split all 3 balls with 2 denials in 3 different groups. She also needs to split the other three to three different groups to ensure none of the group are having more member than the other. As before, we will consider the worst possible situation that James will pick. After 3rd balancing, Jane has 2 balls with 0 denial, 2 balls with 1 denial, and 2 balls with 3 denials.
This is the end of James's free will. After 4th balancing, he has to have at most 1 ball not yet affirmed, while after 3rd balancing, there are still 2 balls with 3 denials (both of them are never affirmed yet in these 3 balancing). Jane can put these two balls in pan A and pan B. James is forced to affirm one of them to avoid losing. However, it causes him to deny all th other balls, and also deny the one he makes weigh less.
Before 4th balancing: 2 balls with 0 denial, 2 balls with 1 denial, and 2 balls with 3 denials. After 4th balancing: 1 balls with 0 denial, 2 balls with 1 denial, 2 balls with 2 denial, 1 ball with 4 denial.
In 5th balancing, James has to prevent 1 ball getting 5 denial. So Jane can just put the ball with 4 denial in pan A and put any random ball in pan B. James definitely need to affirm pan A to avoid losing. But now he denies every other balls.
Before 5th balancing: 1 ball with 0 denial, 2 balls with 1 denial, 2 balls with 2 denial, 1 ball with 4 denial. After 5th balancing: 1 ball with 0 denial, 1 ball with 1 denial, 2 balls with 2 denial, 2 balls with 3 denial
As before, James needs to prevent 2 balls getting 4 consecutive denials to prevent losing. So if Jane put the two balls with 3 consecutive denials in different pans, James will have to affirm one of them, denying the remaining balls.
Before 6th balancing: 1 ball with 0 denial, 1 ball with 1 denial, 2 balls with 2 denial, 2 balls with 3 denial After 6th balancing: 1 ball with 0 denial (reset), 1 ball with 1 denial, 1 ball with 2 denial, 2 balls with 3 denials, 1 ball with 4 denials.
As before, James must avoid a single ball getting 5 denials. So he definitely must affirm the single ball with 4 denials. Even if it was put in pan A alone, with random ball in pan B, causing James to deny other balls.
Before 7th balancing: 1 ball with 0 denial (reset), 1 ball with 1 denial, 1 ball with 2 denial, 2 balls with 3 denials, 1 ball with 4 denials. After 7th balancing: 1 ball with 0 denial, 1 ball with 1 denial, 1 ball with 2 denial, 1 ball with 3 denial, 2 balls with 4 denial.
As we now have 2 balls which haven't been affirmed in 4 consecutive balancing, Jane can win by putting them in different group, causing James to be able to affirm only one of them and denying the other one for 5 consecutive turn, excluding it from the subjects.
So, it was proven that as long as there are 6 or more suspects, Jane can always create a strategy to exclude one suspect. But she can't exclude anymore if there are only 5 suspects left.
q.e.d