8
$\begingroup$

Here are 0 to 15 in binary:

0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111

I have shuffled and concatenated them to obtain the following strings:

  1. 01011111001011110010101110110011110110111101100011

  2. 11101011111011011011111011100101100011100101011001

  3. 11111011111010011010101111000100011101101010011111

Can you recover the order of each binary number in each string? There is a single unique solution in each case. This fact should actually help you solve them. No computers are allowed.

$\endgroup$
10
  • 3
    $\begingroup$ It was somewhat tricky to find strings that have a single solution. $\endgroup$ Nov 4 at 1:29
  • 4
    $\begingroup$ About 0.8% of random shuffles produce a string with a single solution. One can easily generate thousands of these puzzles. Of course, building one manually is a puzzle in and of itself. $\endgroup$ Nov 4 at 4:14
  • 1
    $\begingroup$ Curious which string has the highest number of possible shuffles S_max, and what that number is? and can we get a closed-form expression for S_max as a function of the number of binary digits b (in this case b=4)? $\endgroup$
    – smci
    Nov 4 at 23:32
  • 2
    $\begingroup$ @smci At least 718, with 10011101100101010111111111110101011110110011101000 (hexadecimal: 0x27655ffd5ece8) I'll let the code run overnight to see what else pops up. $\endgroup$ Nov 5 at 1:42
  • 2
    $\begingroup$ I expect this to be maximal: 0x22765d57ff6ce (890 solutions) 1000.10011101100.10111010101011111111111011011001110, also 0x2765d57ff6ce8 which has 1000 on the right instead of the left. The other four permutations of the three groups (0x22eabffb674ec, 0x2eabffb6744ec, 0x2eabffb674ec8, 0x27645d57ff6ce) have 886 solutions each. $\endgroup$ Nov 5 at 18:30

1 Answer 1

9
$\begingroup$

First string:

First, there's only one 000, which must be part of 1000, and the initial 0 must stand alone:
0 1011111001011110010101110110011110110111101 1000 11

Next, note that

The three 00 pairs must lie in 100, 1001, and 1100, in some order. The third of these is the only one that isn't within the sequence 0010, so that must be where 1001 goes:
0 10111110010111100101011101 1001 1110110111101 1000 11

Next, there's only one way

To place the sequence 1111 without leaving a leading 0, within the sequence 11111. From there we can also place 100, and thus 1100:
0 10 1111 100 1011 1100 101011101 1001 1110110111101 1000 11

By the same argument,

We can also place the 111 within the only remaining 1111 sequence:
0 10 1111 100 1011 1100 101011101 1001 1110110 111 101 1000 11

Now, we can finish things off:

0 10 1111 100 1011 1100 1010 1 1101 1001 1110 110 111 101 1000 11


Second string:

First, we can find the sequence 000 and thus the string 1000:
11101011111011011011111011100101 1000 11100101011001

Next, let's look at:

The three occurrences of 00. One of them must be within 1001, which is probably the last occurrence. It's not guaranteed, but it allows us to not lock in the 0. We can then put separators after the other two 00s:
11101011111011011011111011100 101 1000 11100 10101 1001

Next let's guess that

The 10101 sequence near the end shookd be split into 1010 and 1, as we already have a 101:
11101011111011011011111011100 101 1000 11100 1010 1 1001

We can now place

The 100 and 1100, so as not to duplicate the 1:
1110101111101101101111101 1100 101 1000 11 100 1010 1 1001

Now there's only one place for the

1111 to go, in the first 11111 block, as the second would create another 101. Instead, let's carve a 1101 out of the second block:
111010 1111 10110110111 1101 1100 101 1000 11 100 1010 1 1001

And now let's finish things up:

1110 10 1111 1011 0 110 111 1101 1100 101 1000 11 100 1010 1 1001


Third string:

Note that there's two 000 sequences, so one is in a 1000, and the other is ...00 0. So there's a break after each 000:
11111011111010011010101111000 1000 11101101010011111

Next, let's look at

The two other 00 sequences. They both are within 0100 sequences, so neither is in the 1100. So we can identify the 1100:
111110111110100110101011 1100 0 1000 11101101010011111

Next, we can

Separate out the other two 00 sequences, at least their beginnings:
111110111110 100110101011 1100 0 1000 111011010 10011111

Next, note that because there's a unique solution,

The final 00 sequence can't be within a 100 sequence, because the five 11111 sequence could be divided multiple ways. Thus:
111110111110 100 110101011 1100 0 1000 111011010 1001 1111

Next, note that

The later big string can't be split as 1110 110 10, because there's nothing left for the end of the first big string. Thus:
111110111110 100 110101011 1100 0 1000 11101 1010 1001 1111

Now, let's start guessing to wrap it up:

111 1101 1 1110 100 110 10 1011 1100 0 1000 11 101 1010 1001 1111

$\endgroup$
2
  • 2
    $\begingroup$ great deduction $\endgroup$ Nov 4 at 3:10
  • $\begingroup$ Congratulations you have completed this difficult puzzle! $\endgroup$ Nov 5 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.