שאלה 3 בסאמפל

שאלה 3 בסאמפל

אסף (guest) 27 Feb 2012 20:31

איך פותרים את השאלה הזאת?

Re: שאלה 3 בסאמפל

RaeNye 28 Feb 2012 13:54

We'll go over it tomorrow.

Re: שאלה 3 בסאמפל

RaeNye 29 Feb 2012 16:42

Here the short code I promised.

E = get_Hamming_code(5) # 2**26 words of length 31
# get the encoding of X from Tzfania
z = 0
for i in range(31):
  S = {x for x in range(2**26) if (E[x] >> i)%2}
  if tzfania(S):
    z |= 2**i
# decode naively
for i in range(31):
  y = z ^ 2**i # did Tzfania lie in the i'th bit?
  if y in E: # yes!
    return E.index(y)
else:
  return E.index(z) # Tzfania didn't lie at all

cant understand (guest) 29 Feb 2012 20:00

רני.. אתה יכול להסביר את הקוד?
כי אני ממש לא מבין אותו
ונראה לי חשוב להבין את הדרך שמביאה את מלוא הנק' בשאלה הזאת

benny_chor 01 Mar 2012 15:11

The code can be written in many different ways. First and more importantly, you should understand
the solution, write it clearly in Hebrew. Only then comes the code (a code not accompanied with a verbal explanation won't score very high even if it is perfectly OK).

To make life easier, suppose the secret binary string is chosen from $\{0,1\}^4$, so it consists of 4 bits, lets say we denote them by $x_3 x_2 x_1 x_0$ . Yehopatz could first ask about these 4 bits directly. Note that asking about a bit is the same as asking about a subset of $\{0,1\}^4$. For example, $x_0=1$ iff $x\in S_0=\{x | \mbox{ the least significant bit of x is } 1\}$.

Tzfania is a known crook and can cheat, however we are told he could only cheat once.
The hint suggests we use error correction - specifically Hamming error correction code.
Lets ask good old Tzfania for the value of $x_3+x_2+x_0 \ \bmod 2$, $x_3+x_1+x_0 \ \bmod 2$, and $x_2+x_1+x_0 \ \bmod 2$. For each, we formulate the query as a set membership.

We can now look at the seven bits we get back from Tzfania's answers. If they are a codeword in
Hamming $(7,4,3)$ code, then the first 4 bits determine the secret binary string. Otherwise,
Tzfania has lied, and in this case he lied exactly once. We apply the decoding procedure to the
7 bits string, find the closest codeword (necessarily at distance 1), and take the first four bits
of this codeword.

The original question referred to the Hamming $(31,26,3)$ code, but the spirit of the solution is the same. Once this idea is found, you can go ahead and put it into a Python code. The code does not have to be as slick as Rani's code to get full credit. It suffices if it is both correct and readable.