4
$\begingroup$

Hopefully in the spirit of the Fortnightly Challenge 3rd Sept 2018 - Reusing Information

If we are given a binary string, say:

1100010101100011

and we wish to transmit it safely, we might use 'double reading'. This reads the string twice, to produce, using the example above, say:

(11)(10)(00)(00)(01)(10)(01)(10)(01)(11)(10)(00)(00)(01)

This decreases the chance of data corruption when the data is transmitted.

This puzzle involves a two dimensional version, but we hit a snag when we try to encode.

If we wish to transmit a $3\times3$ block, we encode by placing a $4\times4$ grid on top of it:

.   .   .   .
  x   x   x
.   .   .   .
  x   x   x
.   .   .   .
  x   x   x
.   .   .   .

The x's are the data to transmit, and the dots are the encoding.

Unfortunately, encodings aren't unique! And nor are encoding methods!

One encoding method is to say if an 'x' is $0$, then it has an even number of its diagonally neighbouring '.''s set to $0$, otherwise set an odd number of $0$'s. Another is to use number of neighbours.

So if the block to encode is:

.   .   .   .
  1   1   0
.   .   .   .
  0   1   0
.   .   .   .
  0   1   1
.   .   .   .

then:

1   0   0   1
  1   1   0
0   0   1   0
  0   1   0
0   0   0   1
  0   1   1
1   1   0   0

is a solution, and we would transmit:

100001100001100000000111111000

Your job is to find the number of solutions to:

.   .   .   .   .   .   .
  0   1   0   0   1   1
.   .   .   .   .   .   .
  0   1   1   0   0   1
.   .   .   .   .   .   .
  0   1   0   1   1   0
.   .   .   .   .   .   .
  1   0   1   1   0   1
.   .   .   .   .   .   .
  1   1   1   0   0   1
.   .   .   .   .   .   .
  1   1   1   0   0   0
.   .   .   .   .   .   .
$\endgroup$
2
$\begingroup$

I'd say

2^13 = 8192.

Let's start with the top left 0. There are 2^4=16 options for the four dots surrounding it. But only 2^3=8 of them have an even number of ones.

Now let's look at the 1 next to it. Given the four dots around the 0, there are only two dots around it to fix - the two dots to its right. So there are 2^2=4 options for the dots surrounding it (given the dots around the top left 0). But only 2 of the options give an odd number of ones around it.

And so we go on and on to the right, each 'x' adds 2 to the multiplication - 2^5 overall.

We use exactly the same logic going down from the top left 0, again each 'x' multiplies the number of options by 2, and we get 2^5 again.

Overall we get 2^3*2^5*2^5=2^13=8192 options.

This in fact fixes the whole solution. If we look at the 1 diagonally to the top left 0, we're already fixed three of the four dots surrounding it, and so the fourth one is fixed by the condition. (If zero or two of the three dots are ones - the fourth dots must be one, and vice versa.) And we can in fact fill the whole grid, going all the way right, line by line, with just one possible set of bits.

$\endgroup$
  • $\begingroup$ nice, because there are $2^{36}$ 'x' grids which gives us the $2^{49}$ '.' grids. $\endgroup$ – JMP Sep 9 '18 at 19:23
  • $\begingroup$ alternatively, we can set the left and top edges to whatever we want and fill in the grid according to the x's. $\endgroup$ – JMP Sep 9 '18 at 22:25

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.