## Separation of Numbers

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

EricH
Posts: 259
Joined: Tue May 15, 2007 3:41 am UTC
Location: Maryland

### Separation of Numbers

I have a list of twenty-one (21) two digit numbers; none are multiples of 11, none include the digits 8, 9, or 0, and no two contain the same two digits. (That is, the list doesn't contain both 57 and 75.)
The challenge: Organize all of these numbers into circular list, where no element of the list shares a digit with either of its neighbors, and the neighbors don't share any digits with each other.

(So, for example, 13-42-67-15 is an acceptable segment of the list, but 12-34-15-67 is not, because 12 & 15 share a '1', and they're both neighbors of 34.
If I need to define it, circular list means that the first element and the last element are neighbors.)
Pseudomammal wrote:Biology is funny. Not "ha-ha" funny, "lowest bidder engineering" funny.

Mouffles
Posts: 60
Joined: Fri Jul 06, 2007 10:02 am UTC
Location: New Zealand

### Re: Separation of Numbers

Spoiler:
There are no solutions.

Am I right, or is my code broken?
In the spirit of taking things too far - the 5x5x5x5x5 Rubik's Cube.

Torn Apart By Dingos
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC

### Re: Separation of Numbers

I got the same result.

Spoiler:
There are plenty non-circular solutions though. There are 480 ones that start with 12 (treating 12 as equal to 21, and so on).

Geekthras
3) What if it's delicious?
Posts: 529
Joined: Wed Oct 03, 2007 4:23 am UTC
Location: Around Boston, MA

### Re: Separation of Numbers

I'm bored so...

12 34 56 41 32 57 16 23 45 61 72 53 42 67... Later
Wait. With a SPOON?!

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

### Re: Separation of Numbers

Geekthras wrote:I'm bored so...

12 34 56 41 32 57 16 23 45 61 72 53 42 67... Later

That one goes wrong at the fourth number.

I'm doing a full exhaustive check by hand, merely because it's something to do instead of actual work. I've covered about 50% of the possibilities so far. Only one full sequence, and it doesn't wrap around.

EDIT: Apparently I was more than 50% through. It's difficult to tell.

Spoiler:
There is no such sequence. Yes, two people have already found this, but I don't consider a proof valid unless it can be / has been checked by hand.

To check all sequences, I first defined an equivalence class.

Let X be the set of permutations of the 21 allowed numbers (for convenience, assume if xy < yx, then xy is the one we keep). We define an relation R on X such that xRy iff x can be turned into y by swapping all instances of one digit with all instances of another digit, or if there exists some z such that xRz and yRz. R is clearly reflexive and symmetric, and has been defined to be transitive, so is an equivalence relation.

Now we need only check equivalence classes of sequences to see if they satisfy the condition that any three consecutive numbers have no digit in common. Let us call a sequence an n-sequence if the first n numbers satisfy this condition. We are looking for 21-sequences that also satisfy the wrap around condition. (Note: if n>m, then any n-sequence is also an m-sequence.)

First, we note that if an equivalence class contains a k-sequence for some k, then all its members are k-sequences. Secondly, a lot of work is saved if we observe that any equivalence class which contains a 6-sequence contains a sequence that starts 12 34 56 17 23 45. Now we need only check such sequences.

Next step: given the first n numbers of a sequence, if n>2, we can narrow down the choice of the next number to at most two possibilities. Firstly, the number must contain 2 of the 3 digits not in the last 2 numbers of the given n numbers. However, one of these choices will be the 3rd-last number in the sequence, so can be eliminated. Then, we just check to see if the 2 numbers we have found occur already in the sequence. If they do, we can eliminate them.

Now we have a method for building all possible 21-sequences (up to equivalence under R). First, we start with the sequence (12 34 56 17 23 45). Then we apply the following algorithm to our set of candidate sequences Y:

1) Remove a sequence from Y.
2) Find the 2 numbers x and y that could be a possible next number in the sequence.
3) If either x or y already appears in the sequence, discard it.
4) If either don't, append it to the original sequence.
4a) If the new sequence has less than 21 numbers, add it to Y.
4b) If the new sequence has exactly 21 numbers, add it to Z, our set of 21-sequences (initially empty).

In this way, each sequence in Y is replaced with 2 longer sequences. Since Y is finite, the algorithm will eventually terminate. It isn't too much work to run (or check) it by hand - here are the results.

Code: Select all

`12 34 56 17 23 45 16 27 35 14 26 37 15 24 36 57 x12 34 56 17 23 45 16 27 35 14 26 37 15 24 67 13 25 46 x12 34 56 17 23 45 16 27 35 14 26 37 15 24 67 13 25 47 36 x12 34 56 17 23 45 16 27 35 14 26 37 15 46 x12 34 56 17 23 45 16 27 35 14 26 57 13 24 67 15 x12 34 56 17 23 45 16 27 35 14 26 57 13 46 25 37 x12 34 56 17 23 45 16 27 35 14 26 57 34 x12 34 56 17 23 45 16 27 35 14 67 25 13 46 57 x12 34 56 17 23 45 16 27 35 14 67 25 13 47 26 15 37 24 x12 34 56 17 23 45 16 27 35 14 67 25 13 47 26 15 37 46 x12 34 56 17 23 45 16 27 35 46 x12 34 56 17 23 45 16 37 24 15 36 27 14 35 26 47 13 25 46 x12 34 56 17 23 45 16 37 24 15 36 27 14 35 26 47 13 25 67 x12 34 56 17 23 45 16 37 24 15 36 27 14 35 67 x12 34 56 17 23 45 16 37 24 15 36 47 25 13 4612 34 56 17 23 45 16 37 24 15 36 47 25 13 67 x12 34 56 17 23 45 16 37 24 15 67 x12 34 56 17 23 45 16 37 25 14 36 27 15 46 x12 34 56 17 23 45 16 37 25 14 36 57 24 13 67 x12 34 56 17 23 45 16 37 25 14 67 35 24 x12 34 56 17 23 45 16 37 25 46 13 27 x12 34 56 17 23 45 16 37 25 46 13 57 24 36 15 27 34 x12 34 56 17 23 45 16 37 25 46 13 57 24 36 15 47 26 35 14 27 x12 34 56 17 23 45 16 37 25 46 13 57 24 36 15 47 26 35 14 67 2712 34 56 17 23 45 16 37 25 46 13 57 26 14 35 27 x12 34 56 17 23 45 16 37 25 46 13 57 26 14 35 67 24 15 36 27 x12 34 56 17 23 45 16 37 25 46 13 57 26 14 35 67 24 15 36 47 x12 34 56 17 23 45 16 37 25 46 17 35 24 x12 34 56 17 23 45 16 37 25 46 17 35 26 14 57 36 12 34 56 17 23 45 16 37 25 46 17 35 26 47 13 x12 34 56 17 23 45 16 37 25 46 17 35 26 47 15 36 24 57 13 x12 34 56 17 23 45 16 37 25 46 17 35 26 47 15 36 27 14 56 x12 34 56 17 23 45 67 13 24 57 16 x12 34 56 17 23 45 67 13 24 57 36 14 25 37 16 x12 34 56 17 23 45 67 13 24 57 36 14 25 37 46 15 27 x12 34 56 17 23 45 67 13 24 57 36 14 27 35 16 47 25 x12 34 56 17 23 45 67 13 24 57 36 14 27 35 46 x12 34 56 17 23 45 67 13 24 57 36 14 27 56 x12 34 56 17 23 45 67 13 25 46 37 15 24 36 57 14 26 35 47 16 x12 34 56 17 23 45 67 13 25 46 37 15 26 47 35 16 24 57 36 14 2712 34 56 17 23 45 67 13 25 46 37 15 26 47 35 16 27 x12 34 56 17 23 45 67 13 25 47 16 35 24 x12 34 56 17 23 45 67 13 25 47 16 35 27 14 36 57 24 x12 34 56 17 23 45 67 13 25 47 16 35 27 46 15 37 24 x12 34 56 17 23 45 67 13 25 47 16 35 27 46 15 37 26 14 57 36 2412 34 56 17 23 45 67 13 25 47 36 15 24 37 16 x12 34 56 17 23 45 67 13 25 47 36 15 24 37 56 14 27 35 16 x12 34 56 17 23 45 67 13 25 47 36 15 24 37 56 14 27 35 46 x12 34 56 17 23 45 67 13 25 47 36 15 27 46 35 x `

A sequence ends with an x if there is no possible number that can be added to it. There are only 3 21-sequences:

12 34 56 17 23 45 16 37 25 46 13 57 24 36 15 47 26 35 14 67 27
12 34 56 17 23 45 67 13 25 46 37 15 26 47 35 16 24 57 36 14 27
12 34 56 17 23 45 67 13 25 47 16 35 27 46 15 37 26 14 57 36 24

Note that none of them wrap around, so no sequence in their equivalence classes can wrap around. Since these are the only possible 21-sequences, there is no sequence that satisfies all the given conditions. Q.E.D., bitches.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

EricH
Posts: 259
Joined: Tue May 15, 2007 3:41 am UTC
Location: Maryland

### Re: Separation of Numbers

Mouffles is first to answer correctly, but Token's proof is what I was looking for. The result is counterintuitive...well, at least it was unexpected, when I found it myself. That leads me to extend the problem to a list of 42, where each two digits appear twice, e.g. both 67 and 76 are included. Is that enough freedom to find a solution? I honestly don't know yet, but when I get time, I intend to check....

Edit: Obviously, a solution to the first problem would lead quickly to a solution for this one, just by taking the list, making a copy, reversing the digits in each element of the copy, and appending the copy to the original list.
Last edited by EricH on Tue Oct 23, 2007 10:10 pm UTC, edited 1 time in total.
Pseudomammal wrote:Biology is funny. Not "ha-ha" funny, "lowest bidder engineering" funny.

Geekthras
3) What if it's delicious?
Posts: 529
Joined: Wed Oct 03, 2007 4:23 am UTC
Location: Around Boston, MA

### Re: Separation of Numbers

Durr brainfart.
Wait. With a SPOON?!

Buttons
Posts: 858
Joined: Wed May 02, 2007 3:27 pm UTC
Location: Somerville

### Re: Separation of Numbers

Wait, I'm confused. I mean, that proof looks valid, but isn't that essentially saying that KG7,2 is not Hamiltonian? Because that seems to contradict this theorem. What am I missing?

EDIT: Oops. I forgot about the second condition. That's the problem. Ignore me.

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

### Re: Separation of Numbers

EricH wrote:Mouffles is first to answer correctly, but Token's proof is what I was looking for. The result is counterintuitive...well, at least it was unexpected, when I found it myself. That leads me to extend the problem to a list of 42, where each two digits appear twice, e.g. both 67 and 76 are included. Is that enough freedom to find a solution? I honestly don't know yet, but when I get time, I intend to check....

Edit: Obviously, a solution to the first problem would lead quickly to a solution for this one, just by taking the list, making a copy, reversing the digits in each element of the copy, and appending the copy to the original list.

Hmm... trying the same method on this one would work, but would take significantly longer. There'd be five possible options for the next number instead of two, so the number of sequences to check would be more than squared from that, then a good bit more from the extra length, then a bit more because there's less restriction on how the sequence starts (and by "bit more" I mean "orders of magnitude more"). And I'm lazy. Someone get a computer on it (I'd do it myself, but see previous sentence.)
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

Mouffles
Posts: 60
Joined: Fri Jul 06, 2007 10:02 am UTC
Location: New Zealand

### Re: Separation of Numbers

EricH wrote:Obviously, a solution to the first problem would lead quickly to a solution for this one, just by taking the list, making a copy, reversing the digits in each element of the copy, and appending the copy to the original list.

Spoiler:
You don't need a full solution to be able to do this. Just take one of the near solutions and append it to itself, with the numbers changed the second time so that it wraps.

12 34 56 17 23 45 67 13 25 47 16 35 27 46 15 37 26 14 57 36 24 + 15 37 26 14 53 72 64 13 52 74 16 32 54 76 12 34 56 17 24 36 57

(2 swapped with 5 and 4 swapped with 7 for the second one)

Then reverse the digits of some numbers.
In the spirit of taking things too far - the 5x5x5x5x5 Rubik's Cube.

EricH
Posts: 259
Joined: Tue May 15, 2007 3:41 am UTC
Location: Maryland

### Re: Separation of Numbers

Oh, nicely done, Mouffles. I guess I won't be looking for that solution myself.
Pseudomammal wrote:Biology is funny. Not "ha-ha" funny, "lowest bidder engineering" funny.