|
United States24745 Posts
Someone I met on irc proposed a math problem and asked me to help him construct a computer program to solve it. I have some ideas about how to make the code, but I don't have the time to try to make the program, and he is a coding beginner so he can't do it himself. I can't think of any way to solve it without a computer, but I'd love to offer the problem to the community.
The Problem: (proposed by Joseph)
Imagine nine boxes equally spaced along the perimeter of a circle. We'll call the top-most position position #1. The next position clockwise is position #2, etc. through to #9. The goal is to place the numbers 1-9 in the boxes such that they obey the following:
If you place the number 3 in position one, then you have to count 3 boxes clockwise and place the next number in position 4. Then, if you put a '2' in that box your next number would have to go in position 6, etc. Essentially, if you place a number n in a box, then your next number goes n places clockwise from that position. You need to place 1-8 such that they don't overlap and previous numbers, and then 9 goes in the final position.
Solutions?
How many, if any, possible sequences of numbers can you use in order to solve this? Is there a mathematical way to solve it without using a computer program? If not, how would you construct a program to do this?
Disclaimer: this problem is for pure intellectual curiosity and is not assigned work
 
|
Seems like a fairly straightforward backtracking problem unless I'm missing something.
|
My solution:
+ Show Spoiler +Not possible. Since 9 would make a full circle and land on itself, it must be placed last. That means 1-8 must be placed first, but 1-8 sum up to 36, which is a multiple of 9, and so after placing the first 8 numbers, you will land on the first square you started at, which already has a number.
|
On July 03 2009 05:30 Dromar wrote:My solution: + Show Spoiler +Not possible. Since 9 would make a full circle and land on itself, it must be placed last. That means 1-8 must be placed first, but 1-8 sum up to 36, which is a multiple of 9, and so after placing the first 8 numbers, you will land on the first square you started at, which already has a number.
You need to place 1-8 such that they don't overlap and previous numbers, and then 9 goes in the final position.
|
On July 03 2009 05:30 Pawsom wrote:Show nested quote +On July 03 2009 05:30 Dromar wrote:My solution: + Show Spoiler +Not possible. Since 9 would make a full circle and land on itself, it must be placed last. That means 1-8 must be placed first, but 1-8 sum up to 36, which is a multiple of 9, and so after placing the first 8 numbers, you will land on the first square you started at, which already has a number. You need to place 1-8 such that they don't overlap and previous numbers, and then 9 goes in the final position.
I'm aware.
+ Show Spoiler +After placing the first 8 in such a manner, your only possible outcome is to have jumped 36 spaces, landing on an already filled space (specifically, the one you started on).
+ Show Spoiler +In fact, this is impossible not for just 9 boxes and numbers 1-9, but for any number n boxes and numbers 1-n where n is odd. The proof is is simple as showing that for any n odd, the sum of 1 through (n-1) mod n is 0
|
United States24745 Posts
Dromar I think you are correct. It makes sense.
|
Ah I see what you mean. Silly me!
Looking at this further, there are only 8 possible solutions.
1 2 _ 3 _ _ 4 _ _. And here the five would "land" on the two. So four must be placed before two.
3 _ _ 4 _ _ _ 5 _. And here the six would land on the four. So six must be placed before five.
6 _ _ 9 8 _ 7 _ _. And here the nine lands on itself. Which brings us to what Dromar said about 9 having to be placed last.
|
Yeah, unless you described something wrong, Dromar's right.
|
Sanya12364 Posts
Partial Solution:
I'm not going to tackle the computer programming portion just yet.
+ Show Spoiler +
The goal is to produce a sequence that produces a partial sum value that is always a different modulo with respect to 9 at all points in the series.
First of all the sum of 1-8 is 36 which is a multiple of 9 - equivalent of modulo 0.
Since the sequence always returns to the first position at the end, the sequence is cyclical. The starting point of any sequence that works doesn't matter. Inversion of the order also only results in inversion of the sign with respect to modulo, resulting in yet another valid sequence.
For example:
8-2-6-4-3-7-1-5 works so
2-6-4-3-7-1-5-8 also works and
5-1-7-3-4-6-2-8 also works
There's 16 derived solutions coming out of any one unique cycle.
This can be seen as creating 2 unique cyclical paths around the circle. One consisting of just the number 9, and one consisting of 1-8.
|
On July 03 2009 06:02 TanGeng wrote:Partial Solution: I'm not going to tackle the computer programming portion just yet. + Show Spoiler +
The goal is to produce a sequence that produces a partial sum value that is always a different modulo with respect to 9 at all points in the series.
First of all the sum of 1-8 is 36 which is a multiple of 9 - equivalent of modulo 0.
Since the sequence always returns to the first position at the end, the sequence is cyclical. The starting point of any sequence that works doesn't matter. Inversion of the order also only results in inversion of the sign with respect to modulo, resulting in yet another valid sequence.
For example:
8-2-6-4-3-7-1-5 works so
2-6-4-3-7-1-5-8 also works and
5-1-7-3-4-6-2-8 also works
There's 16 derived solutions coming out of any one unique cycle.
This can be seen as creating 2 unique cyclical paths around the circle. One consisting of just the number 9, and one consisting of 1-8.
Where does 9 lie in your given solutions? Unless I missed something, that needs to be included as well.
|
Sanya12364 Posts
On July 03 2009 06:14 vAltyR wrote:Show nested quote +On July 03 2009 06:02 TanGeng wrote:Partial Solution: I'm not going to tackle the computer programming portion just yet. + Show Spoiler +
The goal is to produce a sequence that produces a partial sum value that is always a different modulo with respect to 9 at all points in the series.
First of all the sum of 1-8 is 36 which is a multiple of 9 - equivalent of modulo 0.
Since the sequence always returns to the first position at the end, the sequence is cyclical. The starting point of any sequence that works doesn't matter. Inversion of the order also only results in inversion of the sign with respect to modulo, resulting in yet another valid sequence.
For example:
8-2-6-4-3-7-1-5 works so
2-6-4-3-7-1-5-8 also works and
5-1-7-3-4-6-2-8 also works
There's 16 derived solutions coming out of any one unique cycle.
This can be seen as creating 2 unique cyclical paths around the circle. One consisting of just the number 9, and one consisting of 1-8.
Where does 9 lie in your given solutions? Unless I missed something, that needs to be included as well.
1-8 is part of one cycle. 9 is its own cycle. That's how the problem is posed. There is no need to worry about 9 since it'll just occupy the only space that remains.
|
On July 03 2009 06:17 TanGeng wrote:Show nested quote +On July 03 2009 06:14 vAltyR wrote:On July 03 2009 06:02 TanGeng wrote:Partial Solution: I'm not going to tackle the computer programming portion just yet. + Show Spoiler +
The goal is to produce a sequence that produces a partial sum value that is always a different modulo with respect to 9 at all points in the series.
First of all the sum of 1-8 is 36 which is a multiple of 9 - equivalent of modulo 0.
Since the sequence always returns to the first position at the end, the sequence is cyclical. The starting point of any sequence that works doesn't matter. Inversion of the order also only results in inversion of the sign with respect to modulo, resulting in yet another valid sequence.
For example:
8-2-6-4-3-7-1-5 works so
2-6-4-3-7-1-5-8 also works and
5-1-7-3-4-6-2-8 also works
There's 16 derived solutions coming out of any one unique cycle.
This can be seen as creating 2 unique cyclical paths around the circle. One consisting of just the number 9, and one consisting of 1-8.
Where does 9 lie in your given solutions? Unless I missed something, that needs to be included as well. 1-8 is part of one cycle. 9 is its own cycle. That's how the problem is posed. There is no need to worry about 9 since it'll just occupy the only space that remains.
There is one worry: you need to land on that "only space" in order to place the 9 there.
|
Sanya12364 Posts
On July 03 2009 06:20 Dromar wrote:Show nested quote +On July 03 2009 06:17 TanGeng wrote:On July 03 2009 06:14 vAltyR wrote:On July 03 2009 06:02 TanGeng wrote:Partial Solution: I'm not going to tackle the computer programming portion just yet. + Show Spoiler +
The goal is to produce a sequence that produces a partial sum value that is always a different modulo with respect to 9 at all points in the series.
First of all the sum of 1-8 is 36 which is a multiple of 9 - equivalent of modulo 0.
Since the sequence always returns to the first position at the end, the sequence is cyclical. The starting point of any sequence that works doesn't matter. Inversion of the order also only results in inversion of the sign with respect to modulo, resulting in yet another valid sequence.
For example:
8-2-6-4-3-7-1-5 works so
2-6-4-3-7-1-5-8 also works and
5-1-7-3-4-6-2-8 also works
There's 16 derived solutions coming out of any one unique cycle.
This can be seen as creating 2 unique cyclical paths around the circle. One consisting of just the number 9, and one consisting of 1-8.
Where does 9 lie in your given solutions? Unless I missed something, that needs to be included as well. 1-8 is part of one cycle. 9 is its own cycle. That's how the problem is posed. There is no need to worry about 9 since it'll just occupy the only space that remains. There is one worry: you need to land on that "only space" in order to place the 9 there.
9 goes in the final position - the only one that remains. There is no stipulation that the 8th number in the sequence leads you to where you need to place 9.
|
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?
|
Im gonna check this using group algebra, then in something about half an hour i can give you a good solution aplicable to summative groups of n elements...
|
United States24745 Posts
On July 03 2009 06:22 TanGeng wrote:Show nested quote +On July 03 2009 06:20 Dromar wrote:On July 03 2009 06:17 TanGeng wrote:On July 03 2009 06:14 vAltyR wrote:On July 03 2009 06:02 TanGeng wrote:Partial Solution: I'm not going to tackle the computer programming portion just yet. + Show Spoiler +
The goal is to produce a sequence that produces a partial sum value that is always a different modulo with respect to 9 at all points in the series.
First of all the sum of 1-8 is 36 which is a multiple of 9 - equivalent of modulo 0.
Since the sequence always returns to the first position at the end, the sequence is cyclical. The starting point of any sequence that works doesn't matter. Inversion of the order also only results in inversion of the sign with respect to modulo, resulting in yet another valid sequence.
For example:
8-2-6-4-3-7-1-5 works so
2-6-4-3-7-1-5-8 also works and
5-1-7-3-4-6-2-8 also works
There's 16 derived solutions coming out of any one unique cycle.
This can be seen as creating 2 unique cyclical paths around the circle. One consisting of just the number 9, and one consisting of 1-8.
Where does 9 lie in your given solutions? Unless I missed something, that needs to be included as well. 1-8 is part of one cycle. 9 is its own cycle. That's how the problem is posed. There is no need to worry about 9 since it'll just occupy the only space that remains. There is one worry: you need to land on that "only space" in order to place the 9 there. 9 goes in the final position - the only one that remains. There is no stipulation that the 8th number in the sequence leads you to where you need to place 9.
I think I was unclear in describing the problem. Although I didn't come up with it, I think the 9 is supposed to be landed on as a result of placing 8.
|
The code would be easy to do. PM me and we should discuss. My main language is Java but I do C++ and Python also. And this other thing called Fortran, stupid punch cards.
|
It's not possible, Dromar is 100% correct.
|
On July 03 2009 07:14 micronesia wrote:Show nested quote +On July 03 2009 06:22 TanGeng wrote:
9 goes in the final position - the only one that remains. There is no stipulation that the 8th number in the sequence leads you to where you need to place 9. I think I was unclear in describing the problem. Although I didn't come up with it, I think the 9 is supposed to be landed on as a result of placing 8.
When you say 8 here, are you referring to the 8th number in the sequence, or the actual number 8? If you mean the actual number 8, does this also generalize so that the number n must be landed on as a result of placing n-1?
|
United States24745 Posts
On July 03 2009 08:13 cichli wrote:Show nested quote +On July 03 2009 07:14 micronesia wrote:On July 03 2009 06:22 TanGeng wrote:
9 goes in the final position - the only one that remains. There is no stipulation that the 8th number in the sequence leads you to where you need to place 9. I think I was unclear in describing the problem. Although I didn't come up with it, I think the 9 is supposed to be landed on as a result of placing 8. When you say 8 here, are you referring to the 8th number in the sequence, or the actual number 8? If you mean the actual number 8, does this also generalize so that the number n must be landed on as a result of placing n-1?
I meant 9 should be placed as a result of laying all numbers 1-8 in any order.... 8 could be first or fifth it don't matter.
|
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....
|
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...
|
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
|
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.
|
On July 03 2009 09:31 cichli wrote:Show nested quote +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.
Ohhh, your answer details position and number. I thought it was the sequence of numbers to be inserted. My apologies.
|
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.
|
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 
|
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.
|
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).
|
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.
|
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)
|
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?
|
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.
|
|
|
|
|
|
EPT
