Math Problem: Placing Numbers - Page 2

coltrane

Chile988 Posts

July 02 2009 23:58 GMT

#21

ok, lets begin...

You are working in the additive quotient group Z/9Z, therefore 9 is equivalent to 0, the additive neutro.

So, as said you cant use it until the last step, he completes the cicle.

Moreover, in any partial of the sumatory it cant be a multiple of 9.

Actually is a little bit more on it. When you use a slot, any of them, you are using the whole class, so when you use in example the 5 you cannot get any partial on a nine multiple plus 5.

This limits us as hell, but, is a start.

Let me work in a correct method to do this and some lections to extend this to Z/nZ, i suppose i will have to use ciclic groups and subgroups, but at the last i will be able to do it really fast with any group that has a solution and know just by looking if some n doesnt have it with proofs of it.

edit: so, that last thing should do for a simple coding, you take the sum, make a mod(9) (the rest of the integer divition) of it and if you get any number alredy picked then chose the next number....

Cambium

United States16368 Posts

July 03 2009 00:18 GMT

#22

On July 03 2009 06:31 cichli wrote:
Placing numbers 1 to 9 on a circle according to your description has been solved by others on this thread, but if we generalize the problem to sequence of length n rather than length 9, we find the following solutions:

+ Show Spoiler +

Numbers 1-1 has one solution:
- [1]
Numbers 1-2 has one solutions:
- [1, 2]
Numbers 1-3 has no solutions.
Numbers 1-4 has two solutions:
- [1, 2, 4, 3]
- [3, 1, 4, 2]
Numbers 1-5 has no solutions.
Numbers 1-6 has four solutions:
- [1, 4, 2, 6, 5, 3]
- [2, 3, 5, 6, 1, 4]
- [4, 2, 5, 6, 1, 3]
- [5, 3, 1, 6, 4, 2]
Numbers 1-7 has no solutions.
Numbers 1-8 has 24 solutions:
- [1, 2, 5, 3, 8, 7, 4, 6]
- [1, 5, 2, 4, 8, 6, 7, 3]
- [1, 6, 2, 3, 8, 5, 7, 4]
- [1, 6, 4, 2, 8, 7, 5, 3]
- [2, 4, 5, 1, 8, 6, 3, 7]
- [2, 4, 7, 3, 8, 6, 1, 5]
- [2, 6, 1, 3, 8, 4, 7, 5]
- [2, 6, 3, 1, 8, 4, 5, 7]
- [3, 1, 4, 6, 8, 2, 7, 5]
- [3, 1, 5, 2, 8, 4, 6, 7]
- [3, 4, 5, 7, 8, 1, 6, 2]
- [3, 6, 7, 2, 8, 1, 4, 5]
- [5, 1, 2, 4, 8, 6, 3, 7]
- [5, 3, 1, 6, 8, 2, 4, 7]
- [5, 3, 4, 7, 8, 6, 1, 2]
- [5, 6, 2, 7, 8, 1, 3, 4]
- [6, 1, 3, 4, 8, 7, 5, 2]
- [6, 1, 5, 2, 8, 7, 3, 4]
- [6, 3, 1, 4, 8, 5, 7, 2]
- [6, 3, 7, 2, 8, 5, 1, 4]
- [7, 2, 4, 1, 8, 5, 3, 6]
- [7, 4, 1, 3, 8, 5, 6, 2]
- [7, 5, 1, 2, 8, 4, 6, 3]
- [7, 5, 3, 1, 8, 6, 4, 2]

I solved this by writing a simple SML program that does it by brute force: for each permutation of the numbers 1 through n, check if it's a valid sequence as defined in this thread. Thus, I ran out of memory when I tried solving it for sequence size 10 or larger.

Interesting observation:

+ Show Spoiler +

It seems that so far, only even sequence sizes yield solutions. Perhaps this holds some useful clue to the nature of these sequences?

Did you try working out your solution by hand?

I tried one:
- [1, 2, 5, 3, 8, 7, 4, 6] and it doesn't work

It fails on 8...

Cambium

United States16368 Posts

July 03 2009 00:20 GMT

#23

Solution to the original problem (assuming you can place 9 anywhere...):
+ Show Spoiler +

Sequence of insertions (initial position does not matter, obviously)
->1->2->8->6->5->3->7->4
->1->2->8->5->6->4->7->3
->1->2->3->5->6->8->7->4
->1->2->5->8->6->7->4->3
->1->2->5->8->6->7->3->4
->1->2->5->8->7->6->4->3
->1->2->5->6->8->3->4->7
->1->2->5->6->8->7->4->3
->1->4->2->8->6->5->3->7
->1->4->2->6->8->3->5->7
->1->4->2->6->8->5->3->7
->1->4->2->6->8->5->7->3
->1->4->2->5->8->6->7->3
->1->4->8->2->6->5->3->7
->1->4->6->2->8->5->7->3
->1->4->3->8->6->2->5->7
->1->4->3->7->6->8->2->5
->1->4->3->7->6->8->5->2
->1->4->3->7->5->2->8->6
->1->4->3->5->2->6->8->7
->1->4->7->8->6->5->2->3
->1->4->7->8->6->5->3->2
->1->4->7->8->5->6->2->3
->1->4->7->3->2->8->6->5
->1->4->7->3->5->6->8->2
->1->4->7->5->8->6->2->3
->1->6->4->2->8->5->7->3
->1->6->8->2->5->7->3->4
->1->6->7->3->4->8->2->5
->1->6->5->2->8->4->3->7
->1->6->5->2->8->4->7->3
->1->6->5->2->8->7->4->3
->1->6->5->8->2->4->7->3
->1->3->2->6->8->5->7->4
->1->3->2->6->5->8->4->7
->1->3->2->6->5->8->7->4
->1->3->2->5->6->8->7->4
->1->3->4->8->5->2->6->7
->1->3->4->6->2->8->5->7
->1->3->4->6->2->5->8->7
->1->3->4->6->7->8->5->2
->1->3->4->7->8->2->5->6
->1->3->4->7->8->6->5->2
->1->3->4->7->6->8->5->2
->1->3->8->5->6->2->4->7
->1->3->7->4->2->8->5->6
->1->3->7->4->8->2->5->6
->1->3->7->4->6->5->8->2
->1->3->7->6->8->5->2->4
->1->3->7->5->8->2->4->6
->1->3->7->5->8->2->6->4
->1->3->7->5->8->6->2->4
->1->7->4->2->6->5->8->3
->1->7->4->8->3->2->6->5
->1->7->4->8->5->6->2->3
->1->7->4->3->8->2->6->5
->1->7->4->3->8->6->2->5
->1->7->4->3->8->6->5->2
->1->7->8->6->2->5->3->4
->1->7->8->5->2->6->4->3
->1->7->6->2->5->8->4->3
->1->7->3->4->8->2->6->5
->1->7->3->4->8->2->5->6
->1->7->3->4->6->2->8->5
->1->7->3->5->8->6->2->4
->1->7->3->5->6->2->8->4
->1->7->3->5->6->8->2->4
->1->7->5->2->6->8->3->4
->1->7->5->8->2->6->4->3
->1->7->5->3->8->6->2->4
->1->5->2->8->4->3->7->6
->1->5->2->8->6->7->3->4
->1->5->2->6->8->3->4->7
->1->5->8->2->6->4->3->7
->1->5->6->2->8->4->3->7
->1->5->6->2->8->3->4->7
->1->5->6->2->3->8->4->7
->1->5->6->8->2->3->7->4
->2->4->6->1->3->7->5->8
->2->4->1->3->7->6->8->5
->2->4->1->3->7->5->8->6
->2->4->1->7->3->5->8->6
->2->4->1->7->3->5->6->8
->2->4->1->7->5->3->8->6
->2->4->7->1->3->8->5->6
->2->4->7->3->1->6->5->8
->2->8->4->1->7->3->5->6
->2->8->4->3->7->6->1->5
->2->8->4->3->7->1->6->5
->2->8->4->3->7->1->5->6
->2->8->4->7->3->1->6->5
->2->8->6->1->4->3->7->5
->2->8->6->7->3->4->1->5
->2->8->6->5->1->4->7->3
->2->8->6->5->3->7->4->1
->2->8->6->5->3->7->1->4
->2->8->3->4->7->1->5->6
->2->8->7->4->3->1->6->5
->2->8->5->6->4->7->3->1
->2->8->5->6->1->3->7->4
->2->8->5->1->7->3->4->6
->2->8->5->7->1->3->4->6
->2->8->5->7->3->1->4->6
->2->8->5->7->3->1->6->4
->2->6->4->1->3->7->5->8
->2->6->4->3->1->7->8->5
->2->6->4->3->1->7->5->8
->2->6->4->3->7->1->5->8
->2->6->8->3->4->1->7->5
->2->6->8->3->4->7->1->5
->2->6->8->3->5->7->1->4
->2->6->8->7->1->4->3->5
->2->6->8->5->3->7->1->4
->2->6->8->5->7->4->1->3
->2->6->8->5->7->3->1->4
->2->6->7->1->3->4->8->5
->2->6->5->8->4->7->1->3
->2->6->5->8->3->1->7->4
->2->6->5->8->7->4->1->3
->2->6->5->1->7->4->8->3
->2->6->5->1->7->4->3->8
->2->6->5->1->7->3->4->8
->2->6->5->3->7->1->4->8
->2->1->4->3->7->6->8->5
->2->1->4->7->8->6->5->3
->2->1->4->7->3->5->6->8
->2->1->3->4->6->7->8->5
->2->1->3->4->7->8->6->5
->2->1->3->4->7->6->8->5
->2->1->3->7->4->6->5->8
->2->1->7->4->3->8->6->5
->2->3->8->4->7->1->5->6
->2->3->1->4->7->8->6->5
->2->3->1->4->7->8->5->6
->2->3->1->4->7->5->8->6
->2->3->1->7->4->8->5->6
->2->3->7->4->1->5->6->8
->2->3->5->6->8->7->4->1
->2->5->8->4->3->1->7->6
->2->5->8->6->7->4->3->1
->2->5->8->6->7->3->4->1
->2->5->8->6->7->3->1->4
->2->5->8->7->6->4->3->1
->2->5->8->7->1->3->4->6
->2->5->6->8->3->4->7->1
->2->5->6->8->7->4->1->3
->2->5->6->8->7->4->3->1
->2->5->6->1->3->4->7->8
->2->5->6->1->3->7->4->8
->2->5->6->1->7->3->4->8
->2->5->1->4->3->7->6->8
->2->5->1->6->7->3->4->8
->2->5->1->7->4->3->8->6
->2->5->3->4->1->7->8->6
->2->5->7->1->4->3->8->6
->2->5->7->3->4->1->6->8
->3->2->8->6->5->1->4->7
->3->2->6->8->5->7->4->1
->3->2->6->5->8->4->7->1
->3->2->6->5->8->7->4->1
->3->2->6->5->1->7->4->8
->3->2->1->4->7->8->6->5
->3->2->5->6->8->7->4->1
->3->4->8->2->6->5->1->7
->3->4->8->2->5->6->1->7
->3->4->8->2->5->1->6->7
->3->4->8->5->2->6->7->1
->3->4->6->2->8->5->1->7
->3->4->6->2->8->5->7->1
->3->4->6->2->5->8->7->1
->3->4->6->7->8->5->2->1
->3->4->1->2->5->8->6->7
->3->4->1->6->8->2->5->7
->3->4->1->7->8->6->2->5
->3->4->1->7->5->2->6->8
->3->4->1->5->2->8->6->7
->3->4->7->8->2->5->6->1
->3->4->7->8->6->5->2->1
->3->4->7->6->8->5->2->1
->3->4->7->1->2->5->6->8
->3->4->7->1->5->2->6->8
->3->4->7->1->5->6->2->8
->3->8->2->6->5->1->7->4
->3->8->4->7->1->5->6->2
->3->8->6->2->4->1->7->5
->3->8->6->2->5->1->7->4
->3->8->6->2->5->7->1->4
->3->8->6->5->2->1->7->4
->3->8->5->6->2->4->7->1
->3->1->2->8->5->6->4->7
->3->1->2->5->8->6->7->4
->3->1->2->5->8->7->6->4
->3->1->2->5->6->8->7->4
->3->1->4->2->6->8->5->7
->3->1->4->2->5->8->6->7
->3->1->4->6->2->8->5->7
->3->1->4->7->8->6->5->2
->3->1->4->7->8->5->6->2
->3->1->4->7->5->8->6->2
->3->1->6->4->2->8->5->7
->3->1->6->5->2->8->4->7
->3->1->6->5->2->8->7->4
->3->1->6->5->8->2->4->7
->3->1->7->4->2->6->5->8
->3->1->7->4->8->5->6->2
->3->1->7->8->5->2->6->4
->3->1->7->6->2->5->8->4
->3->1->7->5->8->2->6->4
->3->7->4->2->8->5->6->1
->3->7->4->8->2->5->6->1
->3->7->4->6->5->8->2->1
->3->7->4->1->2->8->6->5
->3->7->4->1->5->6->8->2
->3->7->6->8->2->5->1->4
->3->7->6->8->5->2->4->1
->3->7->6->8->5->2->1->4
->3->7->6->1->5->2->8->4
->3->7->1->4->2->8->6->5
->3->7->1->4->2->6->8->5
->3->7->1->4->8->2->6->5
->3->7->1->6->5->2->8->4
->3->7->1->5->8->2->6->4
->3->7->1->5->6->2->8->4
->3->7->5->2->8->6->1->4
->3->7->5->8->2->4->6->1
->3->7->5->8->2->6->4->1
->3->7->5->8->6->2->4->1
->3->5->2->6->8->7->1->4
->3->5->8->6->2->4->1->7
->3->5->6->2->8->4->1->7
->3->5->6->8->2->4->1->7
->3->5->6->8->2->1->4->7
->3->5->6->8->7->4->1->2
->3->5->7->1->4->2->6->8
->4->2->8->6->5->3->7->1
->4->2->8->5->6->1->3->7
->4->2->8->5->7->3->1->6
->4->2->6->8->3->5->7->1
->4->2->6->8->5->3->7->1
->4->2->6->8->5->7->3->1
->4->2->6->5->8->3->1->7
->4->2->5->8->6->7->3->1
->4->8->2->6->5->1->7->3
->4->8->2->6->5->3->7->1
->4->8->2->5->6->1->3->7
->4->8->2->5->6->1->7->3
->4->8->2->5->1->6->7->3
->4->8->3->2->6->5->1->7
->4->8->5->2->6->7->1->3
->4->8->5->6->2->3->1->7
->4->6->2->8->5->1->7->3
->4->6->2->8->5->7->1->3
->4->6->2->8->5->7->3->1
->4->6->2->5->8->7->1->3
->4->6->1->3->7->5->8->2
->4->6->7->8->5->2->1->3
->4->6->5->8->2->1->3->7
->4->1->2->8->6->5->3->7
->4->1->2->3->5->6->8->7
->4->1->2->5->8->6->7->3
->4->1->6->8->2->5->7->3
->4->1->3->2->6->8->5->7
->4->1->3->2->6->5->8->7
->4->1->3->2->5->6->8->7
->4->1->3->7->6->8->5->2
->4->1->3->7->5->8->2->6
->4->1->3->7->5->8->6->2
->4->1->7->8->6->2->5->3
->4->1->7->3->5->8->6->2
->4->1->7->3->5->6->2->8
->4->1->7->3->5->6->8->2
->4->1->7->5->2->6->8->3
->4->1->7->5->3->8->6->2
->4->1->5->2->8->6->7->3
->4->1->5->6->8->2->3->7
->4->3->8->2->6->5->1->7
->4->3->8->6->2->5->1->7
->4->3->8->6->2->5->7->1
->4->3->8->6->5->2->1->7
->4->3->1->2->5->8->6->7
->4->3->1->2->5->8->7->6
->4->3->1->2->5->6->8->7
->4->3->1->6->5->2->8->7
->4->3->1->7->8->5->2->6
->4->3->1->7->6->2->5->8
->4->3->1->7->5->8->2->6
->4->3->7->6->8->2->5->1
->4->3->7->6->8->5->2->1
->4->3->7->6->1->5->2->8
->4->3->7->1->6->5->2->8
->4->3->7->1->5->8->2->6
->4->3->7->1->5->6->2->8
->4->3->7->5->2->8->6->1
->4->3->5->2->6->8->7->1
->4->7->8->2->5->6->1->3
->4->7->8->6->5->2->1->3
->4->7->8->6->5->2->3->1
->4->7->8->6->5->3->2->1
->4->7->8->5->6->2->3->1
->4->7->6->8->5->2->1->3
->4->7->1->2->5->6->8->3
->4->7->1->3->2->6->5->8
->4->7->1->3->8->5->6->2
->4->7->1->5->2->6->8->3
->4->7->1->5->6->2->8->3
->4->7->1->5->6->2->3->8
->4->7->3->2->8->6->5->1
->4->7->3->1->2->8->5->6
->4->7->3->1->6->5->2->8
->4->7->3->1->6->5->8->2
->4->7->3->5->6->8->2->1
->4->7->5->8->6->2->3->1
->5->2->4->1->3->7->6->8
->5->2->8->4->3->7->6->1
->5->2->8->4->3->7->1->6
->5->2->8->4->7->3->1->6
->5->2->8->6->1->4->3->7
->5->2->8->6->7->3->4->1
->5->2->8->7->4->3->1->6
->5->2->6->4->3->1->7->8
->5->2->6->8->3->4->1->7
->5->2->6->8->3->4->7->1
->5->2->6->8->7->1->4->3
->5->2->6->7->1->3->4->8
->5->2->1->4->3->7->6->8
->5->2->1->3->4->6->7->8
->5->2->1->3->4->7->8->6
->5->2->1->3->4->7->6->8
->5->2->1->7->4->3->8->6
->5->2->3->1->4->7->8->6
->5->8->2->4->6->1->3->7
->5->8->2->4->7->3->1->6
->5->8->2->6->4->1->3->7
->5->8->2->6->4->3->1->7
->5->8->2->6->4->3->7->1
->5->8->2->1->3->7->4->6
->5->8->4->3->1->7->6->2
->5->8->4->7->1->3->2->6
->5->8->6->2->4->1->3->7
->5->8->6->2->4->1->7->3
->5->8->6->2->3->1->4->7
->5->8->6->7->4->3->1->2
->5->8->6->7->3->4->1->2
->5->8->6->7->3->1->4->2
->5->8->3->1->7->4->2->6
->5->8->7->4->1->3->2->6
->5->8->7->6->4->3->1->2
->5->8->7->1->3->4->6->2
->5->6->2->4->7->1->3->8
->5->6->2->8->4->1->7->3
->5->6->2->8->4->3->7->1
->5->6->2->8->3->4->7->1
->5->6->2->3->8->4->7->1
->5->6->2->3->1->4->7->8
->5->6->2->3->1->7->4->8
->5->6->4->7->3->1->2->8
->5->6->8->2->4->1->7->3
->5->6->8->2->1->4->7->3
->5->6->8->2->3->7->4->1
->5->6->8->3->4->7->1->2
->5->6->8->7->4->1->2->3
->5->6->8->7->4->1->3->2
->5->6->8->7->4->3->1->2
->5->6->1->3->4->7->8->2
->5->6->1->3->7->4->2->8
->5->6->1->3->7->4->8->2
->5->6->1->7->3->4->8->2
->5->1->4->3->7->6->8->2
->5->1->4->7->3->2->8->6
->5->1->6->7->3->4->8->2
->5->1->7->4->8->3->2->6
->5->1->7->4->3->8->2->6
->5->1->7->4->3->8->6->2
->5->1->7->3->4->8->2->6
->5->1->7->3->4->6->2->8
->5->3->2->1->4->7->8->6
->5->3->4->1->7->8->6->2
->5->3->8->6->2->4->1->7
->5->3->7->4->1->2->8->6
->5->3->7->1->4->2->8->6
->5->3->7->1->4->2->6->8
->5->3->7->1->4->8->2->6
->5->7->4->1->3->2->6->8
->5->7->1->4->2->6->8->3
->5->7->1->4->3->8->6->2
->5->7->1->3->4->6->2->8
->5->7->3->4->1->6->8->2
->5->7->3->1->4->2->6->8
->5->7->3->1->4->6->2->8
->5->7->3->1->6->4->2->8
->6->2->4->1->3->7->5->8
->6->2->4->1->7->3->5->8
->6->2->4->1->7->5->3->8
->6->2->4->7->1->3->8->5
->6->2->8->4->1->7->3->5
->6->2->8->4->3->7->1->5
->6->2->8->3->4->7->1->5
->6->2->8->5->1->7->3->4
->6->2->8->5->7->1->3->4
->6->2->8->5->7->3->1->4
->6->2->3->8->4->7->1->5
->6->2->3->1->4->7->8->5
->6->2->3->1->4->7->5->8
->6->2->3->1->7->4->8->5
->6->2->5->8->4->3->1->7
->6->2->5->8->7->1->3->4
->6->2->5->1->7->4->3->8
->6->2->5->3->4->1->7->8
->6->2->5->7->1->4->3->8
->6->4->2->8->5->7->3->1
->6->4->1->3->7->5->8->2
->6->4->3->1->2->5->8->7
->6->4->3->1->7->8->5->2
->6->4->3->1->7->5->8->2
->6->4->3->7->1->5->8->2
->6->4->7->3->1->2->8->5
->6->8->2->4->1->7->3->5
->6->8->2->1->4->7->3->5
->6->8->2->3->7->4->1->5
->6->8->2->5->1->4->3->7
->6->8->2->5->7->3->4->1
->6->8->3->4->1->7->5->2
->6->8->3->4->7->1->2->5
->6->8->3->4->7->1->5->2
->6->8->3->5->7->1->4->2
->6->8->7->4->1->2->3->5
->6->8->7->4->1->3->2->5
->6->8->7->4->3->1->2->5
->6->8->7->1->4->3->5->2
->6->8->5->2->4->1->3->7
->6->8->5->2->1->4->3->7
->6->8->5->2->1->3->4->7
->6->8->5->3->7->1->4->2
->6->8->5->7->4->1->3->2
->6->8->5->7->3->1->4->2
->6->1->4->3->7->5->2->8
->6->1->3->4->7->8->2->5
->6->1->3->7->4->2->8->5
->6->1->3->7->4->8->2->5
->6->1->3->7->5->8->2->4
->6->1->7->3->4->8->2->5
->6->1->5->2->8->4->3->7
->6->7->4->3->1->2->5->8
->6->7->8->5->2->1->3->4
->6->7->1->3->4->8->5->2
->6->7->3->4->8->2->5->1
->6->7->3->4->1->2->5->8
->6->7->3->4->1->5->2->8
->6->7->3->1->4->2->5->8
->6->5->2->8->4->3->7->1
->6->5->2->8->4->7->3->1
->6->5->2->8->7->4->3->1
->6->5->2->1->3->4->7->8
->6->5->2->1->7->4->3->8
->6->5->2->3->1->4->7->8
->6->5->8->2->4->7->3->1
->6->5->8->2->1->3->7->4
->6->5->8->4->7->1->3->2
->6->5->8->3->1->7->4->2
->6->5->8->7->4->1->3->2
->6->5->1->4->7->3->2->8
->6->5->1->7->4->8->3->2
->6->5->1->7->4->3->8->2
->6->5->1->7->3->4->8->2
->6->5->3->2->1->4->7->8
->6->5->3->7->4->1->2->8
->6->5->3->7->1->4->2->8
->6->5->3->7->1->4->8->2
->7->4->2->8->5->6->1->3
->7->4->2->6->5->8->3->1
->7->4->8->2->5->6->1->3
->7->4->8->3->2->6->5->1
->7->4->8->5->6->2->3->1
->7->4->6->5->8->2->1->3
->7->4->1->2->8->6->5->3
->7->4->1->2->3->5->6->8
->7->4->1->3->2->6->8->5
->7->4->1->3->2->6->5->8
->7->4->1->3->2->5->6->8
->7->4->1->5->6->8->2->3
->7->4->3->8->2->6->5->1
->7->4->3->8->6->2->5->1
->7->4->3->8->6->5->2->1
->7->4->3->1->2->5->8->6
->7->4->3->1->2->5->6->8
->7->4->3->1->6->5->2->8
->7->8->2->5->6->1->3->4
->7->8->6->2->5->3->4->1
->7->8->6->5->2->1->3->4
->7->8->6->5->2->3->1->4
->7->8->6->5->3->2->1->4
->7->8->5->2->6->4->3->1
->7->8->5->2->1->3->4->6
->7->8->5->6->2->3->1->4
->7->6->2->5->8->4->3->1
->7->6->4->3->1->2->5->8
->7->6->8->2->5->1->4->3
->7->6->8->5->2->4->1->3
->7->6->8->5->2->1->4->3
->7->6->8->5->2->1->3->4
->7->6->1->5->2->8->4->3
->7->1->2->5->6->8->3->4
->7->1->4->2->8->6->5->3
->7->1->4->2->6->8->3->5
->7->1->4->2->6->8->5->3
->7->1->4->8->2->6->5->3
->7->1->4->3->8->6->2->5
->7->1->4->3->5->2->6->8
->7->1->6->5->2->8->4->3
->7->1->3->2->6->5->8->4
->7->1->3->4->8->5->2->6
->7->1->3->4->6->2->8->5
->7->1->3->4->6->2->5->8
->7->1->3->8->5->6->2->4
->7->1->5->2->6->8->3->4
->7->1->5->8->2->6->4->3
->7->1->5->6->2->8->4->3
->7->1->5->6->2->8->3->4
->7->1->5->6->2->3->8->4
->7->3->2->8->6->5->1->4
->7->3->4->8->2->6->5->1
->7->3->4->8->2->5->6->1
->7->3->4->8->2->5->1->6
->7->3->4->6->2->8->5->1
->7->3->4->1->2->5->8->6
->7->3->4->1->6->8->2->5
->7->3->4->1->5->2->8->6
->7->3->1->2->8->5->6->4
->7->3->1->4->2->6->8->5
->7->3->1->4->2->5->8->6
->7->3->1->4->6->2->8->5
->7->3->1->6->4->2->8->5
->7->3->1->6->5->2->8->4
->7->3->1->6->5->8->2->4
->7->3->5->8->6->2->4->1
->7->3->5->6->2->8->4->1
->7->3->5->6->8->2->4->1
->7->3->5->6->8->2->1->4
->7->5->2->8->6->1->4->3
->7->5->2->6->8->3->4->1
->7->5->8->2->4->6->1->3
->7->5->8->2->6->4->1->3
->7->5->8->2->6->4->3->1
->7->5->8->6->2->4->1->3
->7->5->8->6->2->3->1->4
->7->5->3->8->6->2->4->1
->8->2->4->6->1->3->7->5
->8->2->4->1->7->3->5->6
->8->2->4->7->3->1->6->5
->8->2->6->4->1->3->7->5
->8->2->6->4->3->1->7->5
->8->2->6->4->3->7->1->5
->8->2->6->5->1->7->4->3
->8->2->6->5->1->7->3->4
->8->2->6->5->3->7->1->4
->8->2->1->4->7->3->5->6
->8->2->1->3->7->4->6->5
->8->2->3->7->4->1->5->6
->8->2->5->6->1->3->4->7
->8->2->5->6->1->3->7->4
->8->2->5->6->1->7->3->4
->8->2->5->1->4->3->7->6
->8->2->5->1->6->7->3->4
->8->2->5->7->3->4->1->6
->8->4->1->7->3->5->6->2
->8->4->3->1->7->6->2->5
->8->4->3->7->6->1->5->2
->8->4->3->7->1->6->5->2
->8->4->3->7->1->5->6->2
->8->4->7->1->3->2->6->5
->8->4->7->1->5->6->2->3
->8->4->7->3->1->6->5->2
->8->6->2->4->1->3->7->5
->8->6->2->4->1->7->3->5
->8->6->2->4->1->7->5->3
->8->6->2->3->1->4->7->5
->8->6->2->5->1->7->4->3
->8->6->2->5->3->4->1->7
->8->6->2->5->7->1->4->3
->8->6->1->4->3->7->5->2
->8->6->7->4->3->1->2->5
->8->6->7->3->4->1->2->5
->8->6->7->3->4->1->5->2
->8->6->7->3->1->4->2->5
->8->6->5->2->1->3->4->7
->8->6->5->2->1->7->4->3
->8->6->5->2->3->1->4->7
->8->6->5->1->4->7->3->2
->8->6->5->3->2->1->4->7
->8->6->5->3->7->4->1->2
->8->6->5->3->7->1->4->2
->8->3->2->6->5->1->7->4
->8->3->4->1->7->5->2->6
->8->3->4->7->1->2->5->6
->8->3->4->7->1->5->2->6
->8->3->4->7->1->5->6->2
->8->3->1->7->4->2->6->5
->8->3->5->7->1->4->2->6
->8->7->4->1->2->3->5->6
->8->7->4->1->3->2->6->5
->8->7->4->1->3->2->5->6
->8->7->4->3->1->2->5->6
->8->7->4->3->1->6->5->2
->8->7->6->4->3->1->2->5
->8->7->1->4->3->5->2->6
->8->7->1->3->4->6->2->5
->8->5->2->4->1->3->7->6
->8->5->2->6->4->3->1->7
->8->5->2->6->7->1->3->4
->8->5->2->1->4->3->7->6
->8->5->2->1->3->4->6->7
->8->5->2->1->3->4->7->6
->8->5->6->2->4->7->1->3
->8->5->6->2->3->1->4->7
->8->5->6->2->3->1->7->4
->8->5->6->4->7->3->1->2
->8->5->6->1->3->7->4->2
->8->5->1->7->3->4->6->2
->8->5->3->7->1->4->2->6
->8->5->7->4->1->3->2->6
->8->5->7->1->3->4->6->2
->8->5->7->3->1->4->2->6
->8->5->7->3->1->4->6->2
->8->5->7->3->1->6->4->2
Source (brute force java):
http://pastebin.com/m21e7a247

cichli

Sweden84 Posts

July 03 2009 00:31 GMT

#24

On July 03 2009 09:18 Cambium wrote:
Did you try working out your solution by hand?

I tried one:
- [1, 2, 5, 3, 8, 7, 4, 6] and it doesn't work

It fails on 8...

No, it does not fail. This is a solution for a different version of the problem originally posed: what you're looking at is a solution for placing the numbers 1-8 in 8 boxes, rather than the numbers 1-9 in 9 boxes. Thus, 8 is the last number in the sequence and should reach itself. 8 is also reachable from 7.

Cambium

United States16368 Posts

July 03 2009 00:37 GMT

#25

On July 03 2009 09:31 cichli wrote:

Show nested quote +

Ohhh, your answer details position and number. I thought it was the sequence of numbers to be inserted. My apologies.

coltrane

Chile988 Posts

July 03 2009 00:47 GMT

#26

ahah, didnt read dromar second spoiler before, he is right...

46 is the totall sum, if we asume 9 is our last number we have a partial sum of 37, that is 1+36, so is the class of 1, is already taken by our first number.

cichli

Sweden84 Posts

July 03 2009 00:52 GMT

#27

Wrote an improved SML solution that uses backtracking instead of testing all permutations. The code is still pretty ugly and completely undocumented, but performance increased somewhat and I could test it with slighly larger problem sizes. We now have the following results:

(number of boxes to fill, number of possible solutions)
________________________________
(0,0)
(1,1)
(2,1)
(3,0)
(4,2)
(5,0)
(6,4)
(7,0)
(8,24)
(9,0)
(10,288)
(11,0)
(12,3856)
(13,0)
(14,89328)

The trend continues: for sequences with length >1, only sequences of even length yield any solutions at all. It sounds like a reasonable hypothesis, but does it hold in general? How many of our first-born must we sacrifice to the number theory gods in order to prove it?

Also, for even-length sequences, the number of possible solutions seems to increase exponentially. This is hardly surprising.

When I feel like it, I'll try to state this as a constraint satisfaction problem in GeCode/J and see if I get better performance that way.

On July 03 2009 09:37 Cambium wrote:
Ohhh, your answer details position and number. I thought it was the sequence of numbers to be inserted. My apologies.

No problem: I should have bothered to explain my notation better

coltrane

Chile988 Posts

July 03 2009 00:58 GMT

#28

u dont need number theory... u probe it with group theory in 2 steps, im sure, but i am looking at my old university books to write it well.

moriya

United States54 Posts

July 03 2009 01:47 GMT

#29

it is no surprise that only even numbers have solution. The sum of 1 to n-1 can be divided by n if n is odd, which means that the last number n have to be put on the same position of 1.
If n is even, the solution is actually a sequence Ai where A1,A2,...A(n-1) is picked from 1 to n-1 and satisfy that A1,A1+A2,...A1+....A(n-1)|| mod n are all different (1 to n-1).

ReMiiX

United States338 Posts

July 03 2009 04:38 GMT

#30

I am working on coding the solution now, it should take quite a while to write then run so I will post my results later today.

Joseph A. T.

Lebanon6 Posts

July 03 2009 06:50 GMT

#31

Thanks a lot, because you are interested in the problem micronesia have posted for me ...
I'm sorry because the first problem (with numbers from 1 to 9) was impossible to solve, but i understand why it won't work with odd numbers, I think moriya is completely true.
And, if someone knows C++, could he send me the source code of the program to solve this problem , plz ...

(Sorry for my poor english)

cichli

Sweden84 Posts

July 03 2009 09:06 GMT

#32

On July 03 2009 10:47 moriya wrote:
it is no surprise that only even numbers have solution. The sum of 1 to n-1 can be divided by n if n is odd, which means that the last number n have to be put on the same position of 1.
If n is even, the solution is actually a sequence Ai where A1,A2,...A(n-1) is picked from 1 to n-1 and satisfy that A1,A1+A2,...A1+....A(n-1)|| mod n are all different (1 to n-1).

Good observations! It's easy to prove that odd numbers >1 don't have solutions: the sum of the numbers 1 to n-1 is the n-1:th trianglular number. can be written on the form T(n) = n*(n-1)/2. If n is odd and n>1, n is a divisor of T(n): (n-1)=2*m for some integer m and thus T(n) = n*2*m/2 = n*m which is divisible by n. This means that n will land on the same spot as 1 no matter which order we place the others in.

So far so good: we have proven that odd numbers >1 don't have solutions. But can we prove that all even-length sequences have solutions?

igotmyown

United States4291 Posts

July 03 2009 12:21 GMT

#33

Let p be prime. There exists a generator (I forget the language) a, such that, |{a^i mod p: i in {1..p-1} }| = p-1; that is each a^i is unique mod p. a^(i+1)-a^i=(a-1)*a^i, and since a-1 is relatively prime to p, and a^i generates 1..p-1, we have a solution. That is, start at 1, fill in a-1. Move a-1 mod p, you're at box a mod p. Fill in (a-1)*a^i, you will end up in box a^i. There will be no repeats, since a is a generator.

I'm ignoring the pth (or 0 mod p term). You should be able to fill in the boxes relatively prime to n. As for the rest of the boxes, hopefully people can figure out something clever.

Prev 1 2 All

Please or register to reply.

Math Problem: Placing Numbers - Page 2

Completed

Ongoing

Upcoming