<![CDATA[The Genius, by A Skymin’s Mind #5]]>

<![CDATA[The Genius, by A Skymin’s Mind #5]]>Truth Detector

Used as Season 2 Final Game, Round 2.

Rules

There are two players. Each player prepares a 4-digit password and tries to hide it from his opponent. Then each player, in turn, can start asking questions to each other, which must be answered untruthfully. In other words, if you ask “How many times the digit 0 appears in your code?” and you receive a reply of 0, it means there exists the digit 0 in the code (because the reply is wrong). However, this reply cannot be an impossible reply (such as an answer of “5” for the above, considering that there are only 4 digits) or an unrelated/evasive reply (such as “I don’t know”). Additionally, questions must only be about the password. When giving a truth or any of the forbidden replies above, the penalty is revealing a digit not in the password.

When one thinks he knows the password of the other, he may use the turn to answer instead, guessing the password. If this is correct, he is the winner; if this is incorrect, the turn passes to the opponent.

As this is a Final Game, there are three items given:

Starting Player: The person with this item may start asking question first.
Truth Penalty Exemption: If a person accidentally answers the truth, using this item he may avoid the penalty once.
Double Turn: This item may be used to give an additional turn, be it for asking or guessing.

Strategy

Let’s first go “innocent”. Suppose we ask a question with $x$ options. Then whatever option the opponent replies, it is not that. Clearly the opponent should choose the option that rules out the least possibilities. Suppose that we aren’t lucky; if the option that has the least possibilities is option A, then the opponent apparently responds by A (so the password is not in A). Then we reduce the number of possibilities into at least $\dfrac{x-1}{x}$ of the original. To make the best use of this, of course $x = 2$ so we halve the number of choices. With the correct question, we can make sure both cases have the same number of choices and thus the number of possibilities is cut as fast as possible. This is also known as binary search.

Since there are 10000 possibilities and this number is halved each turn, we need at least 14 turns to complete. This is easy to achieve; for example, “is your number bigger than 5000?”, then “is your number bigger than 2500/7500?”, then “is your number bigger than 1250/3750/6250/8750?”, and so on. Sangmin’s strategy is a slightly inefficient one at 16 turns (“even/odd?”, followed by 3-turn binary search, for each of the 4 digits), but is easier to keep track.

That’s the simple strategy. What approaches can help?

I have two strategies in mind, the second of which abuses the rules quite heavily, and given that I don’t know the exact rules, this might be unplayable. So let’s begin with the easier strategy first.

This strategy relies on the difficulty of answering some questions. For example, “if your number is divided by 256, is the remainder less than 128?” is a difficult question, which nevertheless splits the possibilities into two rather-equally-sized clumps. Indeed, the strategy is to reconstruct the binary representation of the number. On the $i$ -th question, ask “if your number is divided by $2^i$ , is the remainder less than $2^{i-1}$ ?” This is basically asking what the $i$ -th digit from the right is in the password’s binary representation. For example, if my password is $0492$ , then its binary representation is $00000111101100_2$ , and thus I will respond with “no, no, yes, yes, no, yes, …” to the questions. Due to how we phrase the question, if we take yes = 1 and no = 0, this is a truthful reconstruction of the number. And since things get heavy to compute at the later questions, it’s very likely that we will get some slip from the opponent, giving us one digit to rule out and potentially cutting some of the possibilities, making 12-13 turns of questioning (+1 to answer) possible. (For example, $10000111101100_2 = 8684$ ; if I answered incorrectly on some question above and gave the digit 8, then you would know without the 14th question that my number is $0492$ and not $8684$ .)

The second strategy is abusing the rules. What if our question has only one answer (“Does your password have 4 digits?”, for example)? Then answering truthfully means the opponent gives one digit to us, and answering untruthfully means giving an impossible reply, which also means the opponent gives one digit to us. The rules get unclear here; what happens if the opponent gets more than one penalty? Does he need to give different digits each time or not? If he needs to give different digits, what happens if he exhausted all digits not in the password? Here, I assume that different digits must be given, but if all digits have been exhausted, then we are simply notified of such.

Moreover, if we have ruled out a particular option (for example, “is your password 0000?” is answered yes), then can the opponent gives a reply that isn’t consistent with the remaining options (for example, “how many digits 0 are in your password?” is answered 4)? Here, we assume the opponent is allowed to do so, so we need to construct our questions carefully.

Then things get interesting.

If we only remove one digit at a time, the first digit removed, our possibilities reduce from $10^4 = 10000$ to $9^4 = 6561$ . This is not quite a nice drop, only 1/3 or so removed. We still fare better by using binary search (to 5000). We can continue cutting down to $8^4 = 4096, 7^4 = 2401, 6^4 = 1296, 5^4 = 625$ …oh hey, now we’re doing better than binary search! But with 5 questions, binary search from the beginning yields a nice $313$ possibilities remaining here. So we go lower to $4^4 = 256$ versus $157$ , then go lower…wait, now the opponent might have no more digit to remove. If we’re lucky, the opponent holds four different digits, and after being notified of such, our possibilities take a massive drop to $4! = 24$ versus $79$ , faring better than binary search! If we’re unlucky, now we’re left with $3^4 = 81$ versus $79$ , but we’re closing up!

Next, if the opponent holds three distinct digits, then we’re stuck here, having $3 \cdot 4 \cdot 3 = 36$ versus $40$ possibilities remaining. (3 for the digit repeated, 4 for the location of the smaller non-repeated digit, and 3 for the location of the larger non-repeated digit.) But we’re doing (slightly) better already. If we’re lucky, we might be left with only two digits, $2^4 = 16$ versus $40$ , where we can just continue with binary search.

Let’s compare the possibilities.

Four different digits: We take 6 questions to remove digits and 1 more question to know that we’re done removing digits. This means 7 questions. With $4! = 24$ possibilities left, binary search solves this in 5 questions, so that’s a total of 12 questions.
Three different digits: We take 7 questions to remove digits and 1 more question to know that we’re done removing digits. This means 8 questions. With $3 \cdot 4 \cdot 3 = 36$ possibilities left, binary search solves this in 6 questions, so that’s a total of 14 questions.
Two or one different digit: We take 8 questions to remove digits. With $2^4 = 16$ possibilities left, binary search solves this in 4 questions, so that’s a total of 12 questions.

So, hey, that’s an awesome combination. We fare generally better than binary search, considering that binary search takes 13-14 turns and ours take 12-14 turns. Expected value and such tells that binary search takes about 13.28771 turns while the above strategy takes about 12.29623 turns. (Try computing it yourself.) That’s one whole turn saved!

Of course, due to there being plenty of rules not revealed, I can’t be sure whether that strategy is allowed, or whether there’s an even better strategy. But that suffices. Safe to say Yohwan was pretty stupid with his sum and product thingies.

]]>