Math Problem: Placing Numbers

micronesia

United States24799 Posts

July 02 2009 20:05 GMT

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

Pawsom

United States928 Posts

July 02 2009 20:26 GMT

Seems like a fairly straightforward backtracking problem unless I'm missing something.

Dromar

United States2145 Posts

July 02 2009 20:30 GMT

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.

Pawsom

United States928 Posts

July 02 2009 20:30 GMT

On July 03 2009 05:30 Dromar wrote:
My solution:

+ Show Spoiler +

You need to place 1-8 such that they don't overlap and previous numbers, and then 9 goes in the final position.

Dromar

United States2145 Posts

July 02 2009 20:34 GMT

On July 03 2009 05:30 Pawsom wrote:

Show nested quote +

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

micronesia

United States24799 Posts

July 02 2009 20:34 GMT

Dromar I think you are correct. It makes sense.

Pawsom

United States928 Posts

July 02 2009 20:35 GMT

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.

armed_

Canada443 Posts

July 02 2009 20:35 GMT

Yeah, unless you described something wrong, Dromar's right.

TanGeng

Sanya12364 Posts

July 02 2009 21:02 GMT

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.

vAltyR

United States581 Posts

July 02 2009 21:14 GMT

#10

On July 03 2009 06:02 TanGeng wrote:
Partial Solution:
I'm not going to tackle the computer programming portion just yet.

+ Show Spoiler +

Where does 9 lie in your given solutions? Unless I missed something, that needs to be included as well.

TanGeng

Sanya12364 Posts

July 02 2009 21:17 GMT

#11

On July 03 2009 06:14 vAltyR wrote:

Show nested quote +

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.

Dromar

United States2145 Posts

July 02 2009 21:20 GMT

#12

On July 03 2009 06:17 TanGeng wrote:

Show nested quote +

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.

TanGeng

Sanya12364 Posts

July 02 2009 21:22 GMT

#13

On July 03 2009 06:20 Dromar wrote:

Show nested quote +

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.

cichli

Sweden84 Posts

July 02 2009 21:31 GMT

#14

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?

coltrane

Chile988 Posts

July 02 2009 21:42 GMT

#15

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

micronesia

United States24799 Posts

July 02 2009 22:14 GMT

#16

On July 03 2009 06:22 TanGeng wrote:

Show nested quote +

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.

ReMiiX

United States338 Posts

July 02 2009 22:18 GMT

#17

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.

Crunchums

United States11144 Posts

July 02 2009 22:43 GMT

#18

It's not possible, Dromar is 100% correct.

cichli

Sweden84 Posts

July 02 2009 23:13 GMT

#19

On July 03 2009 07:14 micronesia wrote:

Show nested quote +

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?

micronesia

United States24799 Posts

July 02 2009 23:53 GMT

#20

On July 03 2009 08:13 cichli wrote:

Show nested quote +

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.

1 2 Next All

Please or register to reply.

Math Problem: Placing Numbers

Completed

Ongoing

Upcoming