2
$\begingroup$

As part of my practice coding, I was given the following problem.

Let's say you have the binary string 011100011. One way to encode the string would be to add each digit to the sum of its adjacent digits. Resulting in the sting 123210122. Given the ENCRYPTED string 22111, what would the original string be using the same decryption pattern.

I would ideally like to solve the problem algebraically, but am a very novice mathematician.

Where Q is the encrypted string, P is the decrypted string then and i is the digit's position within the string:

$$Q^i = P^{i-1}+P^{i}+P^{i+1}$$

Now, I could solve this by using code, but surely there's an elegant mathematical solution to the decryption of the encoded strings. My problem is, I'm not even sure where I should be looking. Can anyone point me in the right direction?

EDIT: Having clarified this with my instructor, it turns out I'll need to provide to possible solutions to the problem. One assuming the first digit of the original string starts with 0, the other assuming it starts with a 1. To add also, just in case it wasn't clear before, the string can only contains ones and zeroes à la binary.

$\endgroup$
  • $\begingroup$ your example has the solution 11001, but in general strings of length 2,5,8,11,... have no solution (see Michael's answer's comments). you could change the question, and tell your instructor off for giving you an impossible problem. $\endgroup$ – JMP Jul 4 '15 at 15:15
  • $\begingroup$ Have just added an edit to my question @JonMarkPerry $\endgroup$ – Dan Jul 4 '15 at 17:54
4
$\begingroup$

You could write the encryption as a matrix product. The matrix has ones on the main diagonal, and one diagonal either side. To decrypt it, multiply by the inverse of the matrix.

$$\left[\begin{array}{ccccc}1&1&0&0&0\\1&1&1&0&0\\0&1&1&1&0\\0&0&1&1&1\\0&0&0&1&1\end{array}\right]\left[\begin{array}{c}a\\b\\c\\d\\e\end{array}\right]=\left[\begin{array}{c}2\\2\\1\\1\\1\end{array}\right]$$
EDIT: This matrix is not invertible, so I think there is no solution. You could add any multiple of $[1,-1,0,1,-1]$ to one solution, to get another solution.

$\endgroup$
  • 1
    $\begingroup$ Indeed, both $10110$ and $01101$ would be encoded as $12221$. However in general, adding a multiple of $(1,-1,0,1,-1)$ to a valid solution will not give a valid solution, since in a valid solution all entries have to be either $0$ or $1$. Especially if the encoded sequence begins with $2$, you know for sure that the decoded sequence begins with $11$, and therefore the solution is unique. $\endgroup$ – celtschk Jul 4 '15 at 14:31
  • $\begingroup$ i got the solution is not unique for 5 with 10010 and 01001 - are matrices of Michael's form ever invertible? $\endgroup$ – JMP Jul 4 '15 at 14:39
  • $\begingroup$ Perhaps only if $n$ is not $\sim2\pmod3$. When $n\sim2\pmod3$, there are two ways to add rows of the matrix to form $[1,1,1,...1]$ $\endgroup$ – Empy2 Jul 4 '15 at 14:44
  • $\begingroup$ @JonMarkPerry: If $d_n$ is the determinant of the $n\times n$matrix of this form, then we clearly have (by expansion over the first row) $d_n = d_{n-1} - d_{n-2}$. We also easily verify that $d_1=1$ (since that is just the matrix with a single entry $1$) and $d_2=0$ (since that is the matrix with all four elements $1$). So the first few determinants are $1,0,-1,-1,0,1,1,0,\ldots$. One sees that the recursion repeats here. Since a matrix in invertible exactly if its determinant is non-zero, you get a non-invertible matrix exactly if $n=3k-1$. $\endgroup$ – celtschk Jul 4 '15 at 14:52
  • $\begingroup$ Also I think the ambiguous sequences are always of the form $01x_101x_2\ldots01x_n01$ vs. $10x_110x_2\ldots10x_n10$ (where the $x_k$ are arbitrary). $\endgroup$ – celtschk Jul 4 '15 at 14:55
0
$\begingroup$

An encrypted string has a solution iff:

  • it is not length $2\mod3$
  • it is length $5\mod3$ and does not not start:end either $122:221$ or $111:111$

A solution can be found by examining the first two numbers in the encryption, say $AB$. The value of the $3^{rd}$ digit in the originator is then $B-A$.

As long as we can orientate the first two digits, we can proceed in the obvious fashion.

For example using $123210122$ from the question, we get:

  • $xx1xxxxxx$
  • $011xxxxxx$
  • $0111xxxxx$

    $\vdots$

  • $011100011$

If the start is hindered, we can start from the end.

In the cases $122$ and $111$, we get $xx1$ and $xx0$ respectively, but are unable to resolve whether we have $101$ or $011$ (and $100$ or $010$) and so progress is halted. A string length $2$ is ambiguous for $01$ and $10$, both of which have encryptions $11$.

I note that if $b_i$ is a binary string, then $En(b_i)\lt En(b_{i+1})$, with $En(b)$ being the encryption of $b$, except at $b_i=0111\dots111$.

$\endgroup$

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.