7
$\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 this string:

11001011011011111101110011001110111010111010001101

Can you recover the order of each binary number in this string? No computers are allowed.

Bonus: can you find multiple solutions?

HINT:

It is possible to make a simple modification to a solution to create another solution.

Improve this question
$\endgroup$
12
  • $\begingroup$ This is trivial to brute force, should there be a no-computers tag? $\endgroup$
    – fljx
    Commented Nov 2, 2023 at 10:59
  • $\begingroup$ yes good point. I will add it. $\endgroup$
    – Dmitry Kamenetsky
    Commented Nov 2, 2023 at 11:01
  • 2
    $\begingroup$ How will we know we've found them all without computers? $\endgroup$
    – Someone
    Commented Nov 2, 2023 at 12:08
  • 2
    $\begingroup$ @someone It turns out the search space is pretty small, so enumerating the solutions by hand doesn't take too long. $\endgroup$
    – fljx
    Commented Nov 2, 2023 at 16:05
  • 5
    $\begingroup$ is there a string that only has 1 solution? $\endgroup$
    – Magma
    Commented Nov 3, 2023 at 4:59

2 Answers 2

Reset to default
17
$\begingroup$

There are a total of:

Twelve solutions:

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

Firstly, there's only one possible place to take 1010 and 1000:

 1100101101101111110111001100111011 1010 1110 1000 1101

Then there is only one block of four or more 1's which must contain the 1111.

We now need three consecutive 1's for each of 111 and 1110.
There are no remaining blocks of four or more 1's, so 111 must be followed by 0 (the only number that starts with "0").
And neither of them can use the "11100" section which would require another number starting with "0".

That gives us the following four possibilities:

 110010110110 1111 110111001100 111 0 11 1010 1110 1000 1101
 110010110110 1111 110111001100 1110 11 1010 111 0 1000 1101
 1100101101101 1111 10111001100 111 0 11 1010 1110 1000 1101
 1100101101101 1111 10111001100 1110 11 1010 111 0 1000 1101

Now look for 1001. We can't have 1,1001 at the start of the string because that leaves another number starting with "0").
So there is only one option in each case:

 110010110110 1111 11011 1001 100 111 0 11 1010 1110 1000 1101
 110010110110 1111 11011 1001 100 1110 11 1010 111 0 1000 1101
 1100101101101 1111 1011 1001 100 111 0 11 1010 1110 1000 1101
 1100101101101 1111 1011 1001 100 1110 11 1010 111 0 1000 1101

Now we have some isolated sections that cannot be split further (100, 11), identifying two more numbers.
And the 1100 can only be at the start:

 1100 10110110 1111 11011 1001 100 111 0 11 1010 1110 1000 1101
 1100 10110110 1111 11011 1001 100 1110 11 1010 111 0 1000 1101
 1100 101101101 1111 1011 1001 100 111 0 11 1010 1110 1000 1101
 1100 101101101 1111 1011 1001 100 1110 11 1010 111 0 1000 1101

Now 1011 can only go in one place without leaving a leading "0":

 1100 10110110 1111 1 1011 1001 100 111 0 11 1010 1110 1000 1101
 1100 10110110 1111 1 1011 1001 100 1110 11 1010 111 0 1000 1101
 1100 101101101 1111 1011 1001 100 111 0 11 1010 1110 1000 1101
 1100 101101101 1111 1011 1001 100 1110 11 1010 111 0 1000 1101

In two of the four cases, that also isolates the 1, which means the final section cannot be split and must be 1101.
In the other two cases, we have two other places for the 1101, expanding our possibilities to eight:

 1100 10110110 1111 1 1011 1001 100 111 0 11 1010 1110 1000 1101
 1100 10110110 1111 1 1011 1001 100 1110 11 1010 111 0 1000 1101
 1100 10 1101 101 1111 1011 1001 100 111 0 11 1010 1110 1000 1101
 1100 10110 1101 1111 1011 1001 100 111 0 11 1010 1110 1000 1101
 1100 101101101 1111 1011 1001 100 111 0 11 1010 1110 1000 1101
 1100 10 1101 101 1111 1011 1001 100 1110 11 1010 111 0 1000 1101
 1100 10110 1101 1111 1011 1001 100 1110 11 1010 111 0 1000 1101
 1100 101101101 1111 1011 1001 100 1110 11 1010 111 0 1000 1101

Finally we still need to fit 101 and 110 somewhere.
There are only one or two ways to do that in each case, leading to the following twelve solutions 

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Great solution, well done! $\endgroup$
    – Dmitry Kamenetsky
    Commented Nov 2, 2023 at 18:30
  • $\begingroup$ I didn't expect someone to find all solutions by hand. Impressive! $\endgroup$
    – Dmitry Kamenetsky
    Commented Nov 2, 2023 at 18:50
6
$\begingroup$

Solution:

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

Started with the first four and spotted the last four. Found the next four at the start until i discovered the 0. To this point i thought every number must start with a 1. So i found the solution with luck and the wrong assumption.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Yes that's correct! But now I realized that my question has multiple plausible solutions... can you find any other ones? $\endgroup$
    – Dmitry Kamenetsky
    Commented Nov 2, 2023 at 11:27
  • $\begingroup$ Also welcome to Puzzling! I hope you like it here :) $\endgroup$
    – Dmitry Kamenetsky
    Commented Nov 2, 2023 at 11:30
  • $\begingroup$ Note (for the bonus): 101 10 110 1111 1 can also be 10 110 1 101 1111 $\endgroup$
    – Stiv
    Commented Nov 2, 2023 at 13:12
  • 3
    $\begingroup$ @Stiv Or more simply 1111 1 can be 1 1111. My computer says there are 12 solutions, half of which are formed by swapping 111 0 and 1110. $\endgroup$
    – Jaap Scherphuis
    Commented Nov 2, 2023 at 13:20
  • $\begingroup$ @JaapScherphuis #oopsoverthinkingagain :) $\endgroup$
    – Stiv
    Commented Nov 2, 2023 at 13:26

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