# The Lying Servers

You have 4 servers which accept a positive number from 0 to 255 (8 bits). Each server takes it's input, performs a basic addition or subtraction of a single digit, non-zero number, and outputs the result. Each server performs the same operation as the other servers. Your goal is to figure out what that operation is in as few queries as possible.

The twist is that only one server is configured properly, and the others will invert the input, output, or both. However, you may proxy through any number of servers as a single query (meaning output from one server is used as input of another, but you are only told the final output).

Server Configurations

    A:   Input --> Add/Subtract -->  Output
B:   Input --> Add/Subtract --> !Output
C:  !Input --> Add/Subtract -->  Output
D:  !Input --> Add/Subtract --> !Output


Here's an example of input 10 for each server having the operation of -3

    A:   10 -->  10-3 -->   7
B:   10 -->  10-3 --> 248
C:  245 --> 245-3 --> 242
D:  245 --> 245-3 -->  13


Proxy example

A > B:  10 --> A --> B --> 251


What is the optimal strategy for figuring out what each server does? What is the optimal strategy for figuring out the configuration of each server?

• Hopefully this is explained well enough to be understood. If you want clarification for anything, feel free to ask. Mar 16, 2017 at 15:56
• What about over/underflow? Is it possible to distinguish the operations -3 and +252? Mar 16, 2017 at 17:01
• Do we know which server is which? I mean, do they have labels A,B,C,D such that if A does $a->a+x$ then B does $a->\textrm{not}(a+x)$, etc., as per the list in the question? Or do we just have four servers and know that one of them does each of those four things? Mar 16, 2017 at 17:07
• @GarethMcCaughan You do not know which server is which, but you know there is one of each configuration and each server performs the same mathematical operation. Mar 16, 2017 at 17:10
• Then I would still claim that it is impossible to distinguish between the operations +n and -n (if n stays the same). Mar 16, 2017 at 17:45

It is not possible to distinguish between the servers A/D or B/C or if the operation is an addition or substraction.

A bitwise inversion of x is equal to 255-x. Let us assume that the operation is +y, in which case:

• a(x) = x + y
• b(x) = 255 - (x + y) = 255 - x - y
• c(x) = 255 - x + y
• d(x) = 255 - (255 - x + y) = x-y

Replacing the operand in the operation (+ with -) only switches the output between the servers A and D and between the servers B and C.

It is trivial to find the absolute value of the operation and which servers only invert either the input or the output, but unless you know the sign of the operation, you can not distinguish between servers A or D (inverting either none or both inputs/outputs) and servers B or C (inverting either the input or the output).

• @DavidStarkey So the solution is, that there is no solution? Mar 20, 2017 at 14:30