3
$\begingroup$

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?

| improve this question | |
$\endgroup$
  • $\begingroup$ Hopefully this is explained well enough to be understood. If you want clarification for anything, feel free to ask. $\endgroup$ – David Starkey Mar 16 '17 at 15:56
  • 2
    $\begingroup$ What about over/underflow? Is it possible to distinguish the operations -3 and +252? $\endgroup$ – jarnbjo Mar 16 '17 at 17:01
  • $\begingroup$ 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? $\endgroup$ – Gareth McCaughan♦ Mar 16 '17 at 17:07
  • $\begingroup$ @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. $\endgroup$ – David Starkey Mar 16 '17 at 17:10
  • 2
    $\begingroup$ Then I would still claim that it is impossible to distinguish between the operations +n and -n (if n stays the same). $\endgroup$ – jarnbjo Mar 16 '17 at 17:45
7
$\begingroup$

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).

| improve this answer | |
$\endgroup$
  • $\begingroup$ @DavidStarkey So the solution is, that there is no solution? $\endgroup$ – jarnbjo Mar 20 '17 at 14:30

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.