Unambiguous number concatenation

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Aldarion
Posts: 133
Joined: Thu Jul 19, 2007 7:00 pm UTC

Unambiguous number concatenation

Postby Aldarion » Sat Jun 11, 2016 1:01 pm UTC

Here's a puzzle I invented only a few minutes ago, which seems interesting enough to share.

I take the one- and two-digit binary numbers:

0, 1, 10, 11


Now I shuffle them in some way and concatenate them together into one string of ones and zeros, like this:

011110


Can you break up this string back into the original numbers? Turns out, this particular string cannot be broken up in a single way:

011110 = (0, 11, 1, 10) / (0, 1, 11, 10)


On the other hand, the string 011011 can only be broken up to make (0, 1, 10, 11).

Let's call strings like 011110 ambiguous and strings like 011011 unambiguous.

How many unambiguous strings are there? As there are only 24 ways to order the four numbers, we can quite quickly try all of them and see that there are seven unambiguous strings:

011011
011101
110011
101101
110101
111001
111010


Of course, we're just starting. Let's define the function U(n, k) to be the number of unambiguous strings made up of base n numbers up to k digits. The example was in binary (n=2), and the numbers were up to two digits (k=2), so now we know:

U(2,2) = 7


What can you tell me about U? My original thought was about U(10, 2). How large is it?
I'm not good, I'm not nice, I'm just right.

ThemePark
Posts: 450
Joined: Fri Jun 27, 2008 5:42 pm UTC
Location: Århus, Denmark

Re: Unambiguous number concatenation

Postby ThemePark » Sat Jun 11, 2016 5:07 pm UTC

I can't tell you much, but I CAN tell you that U(2,2) = 6 because

111010 = (11, 1, 0, 10) / (11, 10, 1, 0)
I have traveled from 1979 to be a member of the unofficial board Council of Elders. Phear M3

User avatar
Kingreaper
Posts: 169
Joined: Sun Jan 27, 2008 4:23 pm UTC

Re: Unambiguous number concatenation

Postby Kingreaper » Sat Jun 11, 2016 6:17 pm UTC

The trivial starting points:
U(n,1)=0
U(1,k)=k

U(2,2)=6, as pointed out by ThemePark.

U(2,3) has 0, 1, 2, 10, 11, 12, 20, 21, 22. 9 digits. 9!=362880 so we can't just bruteforce it by hand.

So I'm going to see if I can work out what would make it not work.
Spoiler:
1 and 2 can't be adjacent, as that would be ambiguous with 12 or 21. That removes 7!*2*8 possibilities, or 80640. 1 can't be next to 11, and 2 can't be next to 22, again removing 80640 each

Neither 1 nor 2 can be followed by 0.That removes 40320 each, for 80640. We've removed 80640 four times, making 322560, leaving 40320 left.

But that requires that A) there be no overlap in the ones removed by each rule (there must be) and B) there be no further rules.

Further rules include: a set with both 1, 12 and 11, 2 or 21, 1 and 2, 11 etc.

User avatar
Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 2054
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

Re: Unambiguous number concatenation

Postby Soupspoon » Sat Jun 11, 2016 6:52 pm UTC

The generalisations to the solution that I am considering are complicated by the number-strings being not front-padded by any zeros, yet zero itself leads alone. But I'm still pondering away on that irregularity in the symbol-based analysis.

ThemePark
Posts: 450
Joined: Fri Jun 27, 2008 5:42 pm UTC
Location: Århus, Denmark

Re: Unambiguous number concatenation

Postby ThemePark » Sat Jun 11, 2016 7:09 pm UTC

Kingreaper, you mean U(3,2). And I actually wrote a program to build all unambiguous solutions to test a thought I had. It's about halfway done, so I should know soon if my theory is correct.

My theory is that for any U(n,2)=x, x can be divided by (n-1)!. So for U(3,2) all 1s and 2s in an unambiguous solution could be interchanged to make another unambiguous solution. And the same goes for any n>2, all digits from 1 and up can be interchanged with each other, i.e. making another permutation of the digit order.

I don't know if this helps any though, but that is all I am able to come up with.

Edit: So my program is done running, and it outputted that there should be 64728 solutions to U(3,2). I looked at some of them and I could indeed find another solution where the 1s and 2s were swapped. But I haven't checked every solution, so I'll let others see if they can confirm or deny my number.
I have traveled from 1979 to be a member of the unofficial board Council of Elders. Phear M3

User avatar
jaap
Posts: 2061
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Unambiguous number concatenation

Postby jaap » Sun Jun 12, 2016 7:32 am UTC

ThemePark wrote:Edit: So my program is done running, and it outputted that there should be 64728 solutions to U(3,2). I looked at some of them and I could indeed find another solution where the 1s and 2s were swapped. But I haven't checked every solution, so I'll let others see if they can confirm or deny my number.

For (3,2) my program also gives 64728 unambiguous solutions and 106476 ambiguous ones. The worst ambiguous cases have 8 ways to read them (e.g. 102221121121020).
For (2,3) it gives 1240 unambiguous, 8070 ambiguous, worst cases have 20 readings (e.g. 101111111010110100)

As my program is just a simple brute-force without any pruning, it can't get through any larger cases.

User avatar
Carlington
Posts: 1574
Joined: Sun Mar 22, 2009 8:46 am UTC
Location: Sydney, Australia.

Re: Unambiguous number concatenation

Postby Carlington » Sun Jun 12, 2016 8:41 am UTC

I don't know if this will help, but I noticed that single-digit '0' cannot be the end of any unambiguous number.

I briefly tried to figure out if this can be made easier by building a graph with digits as vertices and edges representing possible paths through the set of digits, but it's beyond my ability to do. I don't know if there's any simple way to count the number of paths through a graph, but if so then that might be useful too (I think you could build a graph where every path is valid, then prune individual edges that can never be unambiguous like ThemePark's rules)
Kewangji: Posdy zwei tosdy osdy oady. Bork bork bork, hoppity syphilis bork.

Eebster the Great: What specifically is moving faster than light in these examples?
doogly: Hands waving furiously.

Please use he/him/his pronouns when referring to me.

User avatar
Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 2054
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

Re: Unambiguous number concatenation

Postby Soupspoon » Sun Jun 12, 2016 9:35 am UTC

Carlington wrote:I don't know if this will help, but I noticed that single-digit '0' cannot be the end of any unambiguous number.
That's something I was looking at.

Because of 0's unique status as a 0-starting number (prefixing null further digits), wherever it appears after any other single/multiple digit-component, N, it looks indistinguishable from the entry(/ies) elsewhere in the mashup representing N*10. So long as the digit-limit in the sample is greater than 1, there's always a direct swap possible between two such sequences that together become the two (at least) sources of a single ambiguous concatenation.

In my head, I first thought tbis would restrict 0 to the start of a sequence, where it could only be a lone zero, but the example in the OP actively proves that wrong. In those examples, double-zeroes and close zeroes indicate that the potential N*10 is also unambiguously tied up next to the zero, (100 can only be 10 then 0, for d<3; 010 can only be 0 and 10 if the 1 can not be single to let the leading 0 be part of a 10 or any other zero-ender for that particular specificafion; 0101 cannot be 0 then 1 then the fictional 01(...) but must* be 0/10/1; etc).

* - or (...)0/10/1(...) or (...)01/0/1(...) or (...)010/1(...) or (...)0101(...), and perhaps more, with other digit lengths and/or bases, of course

But there's definitely no ambiguity in a leading zero (from which any further zeros start to 'unwrap' in an unbranching sequence 'solution'), and I'm sure there's a phase-spacey diagram or something k-d treey that can pick out such cases as distinct from the others, ready to be solved by finding unambiguous *10s, etc. Then, from the others, extract further 'uniquifying' features that I haven't yet worked out (but at some point any "zero following an x+max_zeros" has got to be one of the secondary-level disambiguators.)

Needs more working on, though.

ThemePark
Posts: 450
Joined: Fri Jun 27, 2008 5:42 pm UTC
Location: Århus, Denmark

Re: Unambiguous number concatenation

Postby ThemePark » Sun Jun 12, 2016 3:12 pm UTC

jaap wrote:
ThemePark wrote:Edit: So my program is done running, and it outputted that there should be 64728 solutions to U(3,2). I looked at some of them and I could indeed find another solution where the 1s and 2s were swapped. But I haven't checked every solution, so I'll let others see if they can confirm or deny my number.

For (3,2) my program also gives 64728 unambiguous solutions and 106476 ambiguous ones. The worst ambiguous cases have 8 ways to read them (e.g. 102221121121020).
For (2,3) it gives 1240 unambiguous, 8070 ambiguous, worst cases have 20 readings (e.g. 101111111010110100)

As my program is just a simple brute-force without any pruning, it can't get through any larger cases.

When the great jaap confirms my number, then I am sure it is correct. :D I also tried out U(2,3) and also got 1240 unambiguous solutions, though I haven't tested how many different ambiguous there are, or the worst cases.

As for the permutations I mentioned, that means that we only have to consider and check the strings where for all the digits except zero, the first occurence of a digit is somewhere before the first occurence of the digit following it in its base. For example, the first 1 is somewhere before the first 2, the first 2 is somewhere before the first 3 and so on. For any string where that is not the case, all occurrences of any two digits can be swapped, so you end up with such a string, a base case if you will.
I have traveled from 1979 to be a member of the unofficial board Council of Elders. Phear M3


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 6 guests