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

Postby EricH » Tue Oct 23, 2007 3:45 am UTC

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.

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

Re: Separation of Numbers

Postby Mouffles » Tue Oct 23, 2007 11:00 am UTC

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.

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

Re: Separation of Numbers

Postby Torn Apart By Dingos » Tue Oct 23, 2007 11:27 am UTC

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).

User avatar
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

Postby Geekthras » Tue Oct 23, 2007 11:57 am UTC

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

Postby Token » Tue Oct 23, 2007 12:06 pm UTC

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 x
12 34 56 17 23 45 16 27 35 14 26 37 15 24 67 13 25 46 x
12 34 56 17 23 45 16 27 35 14 26 37 15 24 67 13 25 47 36 x
12 34 56 17 23 45 16 27 35 14 26 37 15 46 x
12 34 56 17 23 45 16 27 35 14 26 57 13 24 67 15 x
12 34 56 17 23 45 16 27 35 14 26 57 13 46 25 37 x
12 34 56 17 23 45 16 27 35 14 26 57 34 x
12 34 56 17 23 45 16 27 35 14 67 25 13 46 57 x
12 34 56 17 23 45 16 27 35 14 67 25 13 47 26 15 37 24 x
12 34 56 17 23 45 16 27 35 14 67 25 13 47 26 15 37 46 x
12 34 56 17 23 45 16 27 35 46 x
12 34 56 17 23 45 16 37 24 15 36 27 14 35 26 47 13 25 46 x
12 34 56 17 23 45 16 37 24 15 36 27 14 35 26 47 13 25 67 x
12 34 56 17 23 45 16 37 24 15 36 27 14 35 67 x
12 34 56 17 23 45 16 37 24 15 36 47 25 13 46
12 34 56 17 23 45 16 37 24 15 36 47 25 13 67 x
12 34 56 17 23 45 16 37 24 15 67 x
12 34 56 17 23 45 16 37 25 14 36 27 15 46 x
12 34 56 17 23 45 16 37 25 14 36 57 24 13 67 x
12 34 56 17 23 45 16 37 25 14 67 35 24 x
12 34 56 17 23 45 16 37 25 46 13 27 x
12 34 56 17 23 45 16 37 25 46 13 57 24 36 15 27 34 x
12 34 56 17 23 45 16 37 25 46 13 57 24 36 15 47 26 35 14 27 x
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 16 37 25 46 13 57 26 14 35 27 x
12 34 56 17 23 45 16 37 25 46 13 57 26 14 35 67 24 15 36 27 x
12 34 56 17 23 45 16 37 25 46 13 57 26 14 35 67 24 15 36 47 x
12 34 56 17 23 45 16 37 25 46 17 35 24 x
12 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 x
12 34 56 17 23 45 16 37 25 46 17 35 26 47 15 36 24 57 13 x
12 34 56 17 23 45 16 37 25 46 17 35 26 47 15 36 27 14 56 x
12 34 56 17 23 45 67 13 24 57 16 x
12 34 56 17 23 45 67 13 24 57 36 14 25 37 16 x
12 34 56 17 23 45 67 13 24 57 36 14 25 37 46 15 27 x
12 34 56 17 23 45 67 13 24 57 36 14 27 35 16 47 25 x
12 34 56 17 23 45 67 13 24 57 36 14 27 35 46 x
12 34 56 17 23 45 67 13 24 57 36 14 27 56 x
12 34 56 17 23 45 67 13 25 46 37 15 24 36 57 14 26 35 47 16 x
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 46 37 15 26 47 35 16 27 x
12 34 56 17 23 45 67 13 25 47 16 35 24 x
12 34 56 17 23 45 67 13 25 47 16 35 27 14 36 57 24 x
12 34 56 17 23 45 67 13 25 47 16 35 27 46 15 37 24 x
12 34 56 17 23 45 67 13 25 47 16 35 27 46 15 37 26 14 57 36 24
12 34 56 17 23 45 67 13 25 47 36 15 24 37 16 x
12 34 56 17 23 45 67 13 25 47 36 15 24 37 56 14 27 35 16 x
12 34 56 17 23 45 67 13 25 47 36 15 24 37 56 14 27 35 46 x
12 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

Postby EricH » Tue Oct 23, 2007 7:21 pm UTC

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.

User avatar
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

Postby Geekthras » Tue Oct 23, 2007 8:30 pm UTC

Durr brainfart.
Wait. With a SPOON?!

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

Re: Separation of Numbers

Postby Buttons » Tue Oct 23, 2007 9:43 pm UTC

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

Postby Token » Tue Oct 23, 2007 11:12 pm UTC

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.

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

Re: Separation of Numbers

Postby Mouffles » Wed Oct 24, 2007 4:36 am UTC

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

Postby EricH » Wed Oct 24, 2007 12:21 pm UTC

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.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 9 guests