The shorter the message, the larger the prize (version II)

Question

This is a successor question to The shorter the message, the larger the prize . For completeness I will include the entire question even though only the numbers have changed. Solutions to this puzzle will be very different to solutions to the previous one.

Andrei and Belle have been set a task by their “friend”, Carroll. Carroll has promised them money depending on how well they do.

Carroll will give a 90 bit array to Andrei and a different one to Belle. They don’t see each other’s arrays. Andrei gets to send one message (made up of bits) to Belle and Belle then has to say whether she has no bits the same as Andrei’s in common positions or alternatively if exactly 90/3=30 of the bits in her array are the same as the bits in the corresponding position in Andrei’s array.

Carroll has promised that either one of those two conditions will be true.

To give an example with 3 bit arrays, if Andrei gets 011 and Belle gets 101 they have exactly 3/3=1 of their bits in common and 2 distinct. If Belle had received 100 then the two arrays are entirely distinct. Following Carroll’s rule, she could not have received 111 for example.

Clearly Andrei can just send his entire array to Belle. But here is the twist. Carroll will give them $(90-message length)*100 so that shorter messages get more money. She sets out the rules as follows:

• Andrei and Belle can talk only before they receive their arrays from Carroll.
• Whatever scheme they come up must always allow Belle to give the right answer no matter what arrays Carroll gives them. Belle’s decision on what to output must only depend on the message she gets from Andrei and her own array of bits.

How much money can they make?

Answer 1

I will give a very weak lower bound (improved based on xnor's idea), and a minor improvement to user1502040's answer.

Lower bound:

Andrei needs to send a message with at least $\log_2(38)$ bits of information (rounding up to 6 bits).

Proof:

The puzzle reduces to finding ($\log_2$ of) the chromatic number of a certain graph. For simplicity, pretend that Andrei's bit string is the complement of what is given in the question's formulation, so it is either identical to Belle's, or differs by 30 bits.

Let $f$ be the function that Andrei uses to generate his message from his secret bit string. Suppose Belle has bit string $x$. If she receives message $f(x)$, she must conclude that Andrei's string is also $x$. Andrei must have either $x$ or a string that differs from $x$ by 30 bits. If there is a string $y$ that differs from $x$ by 30 bits and $f(x) = f(y)$, then Belle will not be able to distinguish these cases. So, any two bit strings $x$ and $y$ that differ by 30 bits must have $f(x) \neq f(y)$.

This condition is also sufficient. If Belle has bit string $x$ and sees $f(x)$, she concludes that Andrei also has $x$. Otherwise, Andrei has $y$ which differs by 30 bits and $f(x) \neq f(y)$ so Belle concludes Andrei doesn't have $x$.

We can consider the graph where vertices are bit strings of length 90 and there are edges between strings that differ by 30 bits. (This is the distance-30 graph of the 90-dimensional hypercube graph.) If we color the vertices of this graph so that any pair of vertices joined by an edge have different colors, then Andrei can take $f(x)$ to be (a bit string encoding) the color of $x$ in this coloring. Thus, the number of bits Andrei needs is the $\log_2$ of the chromatic number of this graph.

There is a clique of size $38$ in this graph. The difference between any two of the bit strings below is 30 bits. Therefore, each must have a different color, so there are at least 38 colors in any valid coloring of the graph. (Following the convention of xnor, blank spaces are 0's.)

11111111111111111111                                             
11111               111111111111111                              
11111                              111111111111111               
11111                                             111111111111111
     11111          11111          11111          11111          
     11111               11111          11111          11111     
     11111                    11111          11111          11111
          11111     11111               11111               11111
          11111          11111               1111111111          
          11111               1111111111               11111     
               1111111111                    11111     11111     
               11111     11111     11111                    11111
               11111          11111     11111     11111          
1    1    1    1    1    1    1    1    1    1    1    1    1    1    1    1    1    1    
 1    1    1    1    1    1    1    1    1    1    1    1    1    1    1   1    1    1    
  1    1    1    1    1    1    1    1    1    1    1    1    1    1    1  1    1    1    
   1    1    1    1    1    1    1    1    1    1    1    1    1    1    1 1    1    1    
    1    1    1    1    1    1    1    1    1    1    1    1    1    1    11    1    1    
1    1    1     1    1    1     1    1    1     1    1    1     1    1    1 1    1    1   
 1    1    1     1    1    1     1    1    1     1    1    11    1    1     1    1    1   
  1    1    1     1    1    1     1    1    11    1    1     1    1    1    1    1    1   
   1    1    1     1    1    11    1    1     1    1    1     1    1    1   1    1    1   
    1    1    11    1    1     1    1    1     1    1    1     1    1    1  1    1    1   
1    1    1      1    1    1      1    1    1 1    1    1      1    1    1   1    1    1  
 1    1    1      1    1    1 1    1    1      1    1    1      1    1    1  1    1    1  
  1    1    1      1    1    1 1    1    1      1    1    1 1    1    1      1    1    1  
   1    1    1 1    1    1      1    1    1      1    1    1 1    1    1     1    1    1  
    1    1    1 1    1    1      1    1    1 1    1    1      1    1    1    1    1    1  
1    1    1       1    1    1  1    1    1       1    1    1  1    1    1     1    1    1 
 1    1    1       1    1    1  1    1    1  1    1    1       1    1    1    1    1    1 
  1    1    1  1    1    1       1    1    1  1    1    1       1    1    1   1    1    1 
   1    1    1  1    1    1       1    1    1  1    1    1  1    1    1       1    1    1 
    1    1    1  1    1    1  1    1    1       1    1    1  1    1    1      1    1    1 
1    1    1        1    1    1   1    1    1   1    1    1   1    1    1       1    1    1
 1    1    1   1    1    1        1    1    1   1    1    1   1    1    1      1    1    1
  1    1    1   1    1    1   1    1    1        1    1    1   1    1    1     1    1    1
   1    1    1   1    1    1   1    1    1   1    1    1        1    1    1    1    1    1
    1    1    1   1    1    1   1    1    1   1    1    1   1    1    1        1    1    1

The first 13 elements of the clique are just xnor's idea of using a finite projective plane. One way of understanding the additional 25 elements is to think of them as strings of base 5 digits. If the strings are broken up into blocks of 15 bits, the only blocks are 100001000010000, and the four rotations of this string which we will map to the digits $0$ through $4$. Thus if two of our 6-digit base 5 strings have digit of the same value in the same position, they have 3 overlapping 1's in the binary, and if they have don't have a matching digit in a position, it will contribute 6 to the difference from the three non-overlapping 1's in each string. Thus, there will be a difference of 30 bits whenever there is exactly one base 5 digit that matches in position and value. Furthermore, in the binary, each string has exactly one 1 bit in each block of 5 for 18 total 1's, four of which will overlap with any projective plane bit string (as these use the same blocks of 5 bits) which also gives a difference of 30 (four bits of difference contributed from each of four blocks where the projective string has 1's and one bit of difference from each other block: $4 \cdot 4 + 14 = 30$).

We can construct a set of 25 of these 6-digit base 5 strings such that every pair has exactly one digit that matches in both value and position. For every value/position combination, there can be at most 5 strings that share it, as a sixth string would have to match one of the others in a second position. Thus, each position can account for $5 {5 \choose 2} = 50$ pairs, and all six positions account for all ${25 \choose 2} = 300 = 6 \cdot 50$ pairs.

These strings can be constructed as follows: We will give each string a coordinate $(x, y)$ with each of $x$ and $y$ ranging from $0$ to $4$. Let $p$ indicate the index of a position in the string from $0$ to $4$. Then we choose the digit at $(x, y, p)$ to be $y+xp \bmod 5$. Thus, for any pair $(x, y)$ and $(x', y')$ with $x \neq x'$, there is a unique solution to $y+xp = y'+x'p$ given by $p=(y-y')/(x'-x)$. If $x = x'$, there is no solution (except pairing a string with itself), so we can just take the last digit to be $x$. The strings looks like this:

(0, 0): 000000
(0, 1): 111110
(0, 2): 222220
(0, 3): 333330
(0, 4): 444440
(1, 0): 012341
(1, 1): 123401
(1, 2): 234011
(1, 3): 340121
(1, 4): 401231
(2, 0): 024132
(2, 1): 130242
(2, 2): 241302
(2, 3): 302412
(2, 4): 413022
(3, 0): 031423
(3, 1): 142033
(3, 2): 203143
(3, 3): 314203
(3, 4): 420313
(4, 0): 043214
(4, 1): 104324
(4, 2): 210434
(4, 3): 321044
(4, 4): 432104

Further comments about this construction, cliques, and possible generalizations:

In general, different projective planes could be used. We perhaps don't need all the conditions of a projective plane, though. If we say graph points are plane points, we need exactly one line between every pair of points (ie every pair of points has the same size bit overlap), and every point needs to be incident to the same number of lines. But, we don't really need any condition on lines. A projective plane is still generally best because if all points are incident to $n + 1$ lines, and any line is incident to $n + 1$ points, the you can't have any line incident to more than $n + 1$ points (except having every point be collinear which may actually be useful in some generalizations) and having every line incident to $n + 1$ points gives the most points -- and this is a projective plane. But, a subset of a projective plane can be useful. For example, although xnor notes that the projective plane of order 5 doesn't quite fit (when tripled to meet the distance 30 condition), if we leave off one line and all the incident points, we can fit 25 points and 30 lines in 90 bits. (But, I don't know how to turn this into a bigger clique as it seems harder to extend.)

There are multiple ways to extend a projective plane clique. To have the same overlap with each projective plane element, one must have the same number of 1's in each block of the projective plane. For the plane used in this answer, that can be 0, 1, or 2. This answer uses 1, and xnor's uses 0. 2 also seems interesting, but it is maybe hampered because, the way the numbers work out, it can't use any additional bits.

For the base 5 construction, the same basic construction should work in any finite field (in other words if the base is a power of a prime, although finite fields of non-prime order aren't just the integers modulo the order of the field). I'm not sure what the best you can do is for other bases. Larger bases also need more bits to encode each digit. And, the number of non-matching digits (equal to the base) has to divide the distance. Most digit encodings will give an even contribution to distance, so in practice, the number of non-matching digits has to divide half the distance. (The only exception to an even-distance encoding is to encode a binary digit as a odd-length string or its complement.) Finding a digit encoding is the problem of again finding a clique of size equal to the base on some smaller number of bits with a smaller distance. (We may impose another restriction, like compatibility with a projective plane, but we don't necessarily need to do this. For example, the base 5 configuration can be encoded in fewer bits using a projective plane, but there seems to be no advantage to doing this because it breaks compatibility with the projective plane used for the additional clique elements.)

So, for the case of 30, the next higher divisor of 15 is 15 itself. Even if there was a good base 15 configuration, there's no way of encoding 16 base-15 digits (with the desired distance condition) in 90 bits.

Another option rather than using a divisor of the distance is to decompose the distance as a sum. One could find two cliques with distances that sum to the desired distance, and then pair elements of the cliques (with extra elements of the larger clique going to waste). 30 could be solved with a base 7 and a base 8 configuration each with digits contributing 2 each. This would give a clique of size 49, but I don't know how to encode it in fewer than 128 bits (7 bits for each base 7 digit and 8 bits for each base 8 digit). (For distance 2 digits, the shortest encoding I know is generally just to take the strings with a single 1. The only exception is perhaps base 4 which has 000, 011, 101, 110 as a 3-bit encoding.)

In general, using either technique seems to be a simplification to the question of finding a clique. In both cases, we are looking at overlap of a single digit. It is possible the only advantage of doing so is in managing complexity. Overlap of multiple digits could admit a larger clique, but then maybe finding a clique itself is already this kind of problem. And, of course, the chromatic number of the graph may be larger than the size of the largest clique anyway.

Also, note that it we take any two bit strings and take their bitwise-exlusive-or with some fixed string, the distance between the resulting strings is the same as the distance between the original strings. So, we could take the bitwise-exlusive-or of every member of a clique with one of its members to transform it into a clique containing the string of all zeroes and where every other string has 30 1's which must overlap with exactly 15 1's of each other member.

User1502040's answer can be improved to

44 bits

by the following method:

Observe that $f(x)$ and the bitwise complement of $f(x)$ are never adjacent since it would take at least a 44 bit change to invert the 44 bits of row parity information. If two colors are never adjacent, they can be merged into the same color. This halves the number of colors, saving one bit of information.

One way of making this concrete is to have Andrei follow the original procedure, then if the first row's parity is $1$, take the complement of the entire message. Don't send the parity of the first row (which is now $0$ either way).

The resulting coloring is at least locally optimal in the sense that every color is adjacent to every other color (and in fact every node is adjacent to every other color), but this seems to be quite a weak statement in general. (Very poor colorings can be "optimal" in this way.)

Further comments about this strategy and possible generalizations:

Taking the parity of a group of size 2 is powerful because if the parity matches there are only two possibilities: either there is a perfect match, or both bits have been flipped. If we try to take the parity of a larger group, there are more kinds of changes that can go undetected. This can create problems. For example, with at least three groups of size three or more, even if we know the parity of all the columns and even if we know the exact number of 1's in the string, we can't distinguish (110)(101)(011) from (101)(011)(110). These have a difference of 6. Since (10)(01) and (01)(10) also can't be distinguished, generally, any even error larger than size 2 can go undetected. Even with groups of size 2, we can't detect an error that's size is a multiple of 4 (at least, not without additional information).

We can fix this problem by taking more than one bit of information from a group. For example, by pairing each group configuration with its complement (e.g. by taking the complement if the first bit is $1$, then don't send the first bit of the group which is now $0$ either way), we get the same power as taking the parity of a group of size 2 (and saving one bit from sending the whole group): if this checksum matches, then the group is either identical or exactly the complement. Thus, if we split a string into groups of size 3 and all group checksums match, then either the strings match, or the number of errors is a multiple of 3. This isn't so useful for 30 errors, but it would immediately resolve the question whenever the number of errors isn't a multiple of 3. (It doesn't beat isaacg's approach if the number of errors is a third of the string length, but it is better if the number of errors is smaller.) If the number of errors is a multiple of 3, we would know the number of errors in any column is the quotient. In principle this is useful, and it is the information we use when dividing by 2 using groups of 2. In such cases we have to recurse, and that is most powerful when the quotient is odd, since that case can be solved in one bit.

In applying the optimization original to this answer (pairing up colors that are never adjacent), depending on the number of groups versus the size of the error, it might not be possible to do the optimization at all (if the number of errors is greater than or equal to number of groups for which information is being sent), or it might be possible to find larger sets of colors that can be merged. (I don't think it is possible to merge three or more colors in the example at hand.)

Also note that this message function is linear if we treat the bit strings as vectors over the finite field of order 2. Also (as noted above), the distance between two strings is preserved if we add the same vector to both. (Adding here is the same as taking the bitwise-exclusive-or of two bit strings.) This seems to be a favorable property. Given $x$ and $y$, then $f(x) = f(y)$ iff $f(0) = f(x+x)=f(x)+f(x)=f(x)+f(y)=f(x+y)$; and $0$ and $x+y$ are adjacent iff $x$ and $y$ are adjacent. Thus, linearity seems to give us a lot of what we want from symmetry (we only need to consider cases involving $0$ (or some other fixed element)). (The answer from isaacg is also linear.)

Answer 2

It is possible for them to make

\$4400 $4500 (46 45 bits used)

First, Andrei inverts his input, so either 0 bits or 30 bits differ. Then he splits the input into a 45x2 grid, and sends the parity of each row of 2 (edit: thanks to Retudin for pointing out that the parity of the last row is redundant and can be skipped), and the parity of the first column. Belle checks if she gets the same result as Andrei on her input. For each row to have the same parity for both parties, both bits must be flipped at once (or neither flipped), but that means 15 bits in each column will be flipped, and the column parity will not match.

Answer 3

I doubt this is optimal, but to get us started, Andrei and Belle can make

$3000

Andrei's procedure is:

If the first bit is a 1, invert all of the bits. Then send the next 60 bits.

Belle can reconstruct this:

If Belle's first bit is a 1, flip all of the bits received. Then check if they match Belle's next 60 bits.

The reason this works is:

If the first bit was flipped between Andrei and Belle, only 29 flips remain, so the next 60 will have at least 31 errors. If the first bit wasn't flipped, and 30 bits were flipped, the next 60 bits will have at least one error.

Answer 4

This is a weak lower bound showing that at least 4 bits must be sent.

We follow tehtmi's observation that the problem is to effectively to find the chromatic number of the graph on the $2^{90}$ binary strings of length 90 which has an edge between two strings whenever they differ by exactly 30 bit flips. We improve on their size-6 clique by finding a clique of size 14, which requires 14 colors and so means that at least $\log_2(14)$ bits of information must be sent, so at least 4.

The clique is the 14 rows below, with 0's shown as blank for clarity. You can check that any two rows differ in exactly 30 positions.

11111111111111111111                                             
11111               111111111111111                              
11111                              111111111111111               
11111                                             111111111111111
     11111          11111          11111          11111          
     11111               11111          11111          11111     
     11111                    11111          11111          11111
          11111     11111               11111               11111
          11111          11111               1111111111          
          11111               1111111111               11111     
               1111111111                    11111     11111     
               11111     11111     11111                    11111
               11111          11111     11111     11111          
                                                                 1111111111

The construction uses the projective place for $N=3$, which has $N^2+N+1=13$ points and lines:

Image from https://en.wikipedia.org/wiki/Projective_plane#A_finite_example

All rows have four 1's, and any two rows overlap in one 1, so there are 6 positions where they differ. By replacing each column with a block of 5, we scale up the difference to 30 positions, using 65 columns. We can then add a 14th row whose 1-bits occupy 10 used positions, and so also differs in 30 bits from any other row, having used total 75 columns of our allowance with 15 to spare.

Unfortunately we're just short of using the projective-plane for $N=5$, which has 31 rows and would use $31 \cdot 3= 93$ columns. This would show that for a 93-bit version of the problem, at least $\log_2(31)$ bits are needed, and so 5 at minimum. The $N=4$ plane isn't suitable either because an two rows different at 8 positions, and 30 isn't a multiple of 8.

Answer 5

The crc method and modulo methods didn't work (previous answers now deleted), but maybe 3rd time is the charm? I don't know how to prove / disprove it. I've done some exploratory coding.

Step 1: Send 5 bits with the count of the number of 1s in the number. 5?! Yes, 5 (I originally had 6, but commenters pointed out 5 is enough). Because 0-14 and 76-90 all just get a 0, and 15-75 get 1-61, and so I only need 0-62 or 6 bits. If there are 0-14 or 76-90 1s, then it's impossible to have a hamming distance of 30 and also have 0-14 or 76-90 1s in the string. But the parity is known, so you can save a bit.

So at the end of this, we will know that both numbers have the same number of 1s. Which means the only failure mode is 15 1s changed to 0s and 15 0s changed to 1s. Or, put another way, 15 1s moved to new spots on the string formerly occupied by 0s.

(Update: I've changed step 2. This was my original idea, but then I thought the modulo arithmetic idea was equivalent and easier to explain so I went with that, but commenters pointed out that it didn't work. So I reverted to this and I think it makes more sense.)

Step 2: Here it gets a little more sketchy and it may be possible to further optimize. But the basic idea is to efficiently detect movement of 1s, as follows:

1. Take these 6 prime numbers: [7,13,17,19,23,29]. These numbers are chosen because they are prime and the product of any 2 is bigger than 90, and 6 choose 2 is 15.
2. For each prime, create an index $a$, such that $a[(i\cdot p)\mod 90]=i$, for $i$ running from 0 to 90, and $p$ in the above list. So for $p=7$, the index is [0, 13, 26, 39, 52, 65, 78, 1, 14, 27, 40, 53, 66, 79, 2, 15, 28, 41, 54, 67, 80, 3, 16, 29, 42, 55, 68, 81, 4, 17, 30, 43, 56, 69, 82, 5, 18, 31, 44, 57, 70, 83, 6, 19, 32, 45, 58, 71, 84, 7, 20, 33, 46, 59, 72, 85, 8, 21, 34, 47, 60, 73, 86, 9, 22, 35, 48, 61, 74, 87, 10, 23, 36, 49, 62, 75, 88, 11, 24, 37, 50, 63, 76, 89, 12, 25, 38, 51, 64, 77].
3. Take the dot product of our binary string with the index mod $p$ for each $p$.
4. So if my binary were $[1,1,0,\ldots,0]$ (just two 1s), the remainders would be $(6, 7, 2, 0, 1, 1)$.
5. Encode these remainders into $7\times13\times\ldots\times29$ numbers and encode as 25 bits.
6. If all these remainders are the same, then you can assume that the numbers haven't moved.

I actually suspect that step 2 may work without step 1.

So a total of $25 + 5 = 30$ bits. My program is still running, but it won't finish in my life time with the current hardware. Or, if we don't need step 1, then $25$ bits will be enough.

So the above is a tentative answer, until I can justify it or find a counter-example, or (more likely) someone here figures out what I did wrong...

---

Hands-wavey argument that this is better than the original method. If you wanted to detect the movement of a 1 in a string of length 6, you could clearly do it with primes $[2,3]$ using this method. But using the old method, any strings that differed by 6 would return the same hash.

---

Coding update:

I'm looking at the worst-case scenario, which is 45 1s out of 90. I'm moving 15 1s from the original set into new locations. So far, I've checked 1,000,000 such moves, and have had 0 failures in the original divisor set [7,13,17,19,23,29] and the index formed by $a[(i*p)\mod90]=i$.

Answer 6

FWIW - this is my first post on PSE. Bear with me. ;)

This puzzle has been discussed long enough that there doesn't appear to be any value in using spoilers, so here goes.

It seems like it should be possible to get $7100 by expanding on User1502040's approach, but instead of using a 2x45 grid, use a 9x10 grid and send an array of the parity bits for each row and column (19 bits total).

After Andrei inverts his string and builds his grid, there are two (or maybe three) possibilities:

1. Some parity bits differ from the transmitted string, so the 30 bits must have been inverted.
2. The 30 bits were not inverted, so both strings of parity bits are exactly the same.
3. And maybe - the 30 bits were inverted, but the parity bit strings are still the same.

So the question is - is option #3 possible? If not, then that leaves only #1 or #2.

Clearly, any given row or column maintains its parity if an even number of bits are inverted (multiples of 2). The trick is - is there a sequence of bits that could result in inverting an even number of bits in all rows AND all columns? If the number of bits in question is divisible by 4, this is trivial (think a 2x2 grid within the larger grid, or 4 corners of a larger square).

But having 30 bits in question leaves 2 extra bits after you pair up the row & column groups of 4. So there will be one row (or column) with 2 inverted bits that span two columns (or rows) without an offsetting inversion. So these two columns (or rows) will change their parity bits. Therefore, option #3 is not possible, so there is a clear indicator of option #1 vs. option #2.

Is this optimal? I don't know in general, but for this grid based approach it's clearly optimal since 9x10 is as close as you can get to a square grid.