Author Topic: Number game  (Read 11951 times)

testpost

  • Newbie
  • *
  • Posts: 23
Number game
« on: 八月 05, 2004, 06:22:38 pm »
*****184******

Put Number 1-N*N numbers into N by N board.

Rule 1: Top-left conner must be smaller than all other conner
Rule 2: Top-right conner must be smaller than bottom-left
Rule 3: Sum of any column must be N*(N*N+1)/2
Rule 4: Sum of any line must be N*(N*N+1)/2
Rule 5: Sum of diagonal must be N*(N*N+1)/2

For example (in case of 3x3, the only one possible):

2   9   4
7   5   3
6   1   8

How many possibles for 5x5?
testposttestposttestpost

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Number game
« Reply #1 on: 八月 06, 2004, 11:35:35 am »
The magic square problem is a classic problem, dating back to greeks. There's a stone board with a 4 x 4 magic square carved in it.  The bottom line was 4 14 15 1, and the center 2 number make up 1415, which was the year the stone was carved.  

It is old, but it still attract people's attention. There was a paper about 3-dimensional magic cube in the Mathematical intelligencer serveral years ago, very interesting stuff.

Generally speaking, there are two algorithms for magic squares, depends on mod(N,4) equal to zero or not. MATLAB actually has a function to do it. But I have never thought about the problem of "how many ways",  For a particular number, it might not be hard. But for general N, I wonder if there's a good way to show "how many ways". Good question.

I think you don't need the first two conditions in your problem. Any magic square will satisfy the first two rules after rotation and reflection.

testpost

  • Newbie
  • *
  • Posts: 23
Number game
« Reply #2 on: 八月 06, 2004, 12:39:04 pm »
Thank you for history posting. It was quite interesting.

To put the first 2 rules there just eliminate number count confusion. for 3x3 case, there are 8 appearence of 1 way by rotating and flip it.

I post it because the answer is quite impressive.

Here's hint for one of them:

 4  25  16  12   8
15   6   2  23  19
21  17  13   9   5
 7   3  24  20  11
18  14  10   1  22
testposttestposttestpost

Elixir

  • Jr. Member
  • **
  • Posts: 32
Number game
« Reply #3 on: 八月 06, 2004, 03:51:15 pm »
I read some article saying that there are 1 3x3 magic square, 880 4x4 magic squares and 275305224 5x5 magic squares. The exact numbers for higher degree ones are unknown and presumably very very large.

I don't know of any good way to deduct the number 880 or 275305224 other than a brutal-force computer program.

testpost

  • Newbie
  • *
  • Posts: 23
Number game
« Reply #4 on: 八月 06, 2004, 07:55:30 pm »
This looks like the least interesting one. So, try this one (totally
unrelated):

6 piece of checker chess on the board arranged in this way in a line:
xoxoxo

You are allowed to move:
each step 2 adjacent piece move together. They can move in the
line to 2 adjacent location but they can not exchange position:

xoxoxo -> x..oxo.OX (OK)
xoxoxo -> x..oxo.XO (NO)

With 3 steps, can you change it to:

xxxooo or
oooxxx

If this question is not clear enough, or if you want to know the answer,
scoll down.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

0. xoxoxo
1. xox__oox
2. __xxooox
3. ____oooxxx

The same condition, try 4:
xoxoxoxo -> xxxxoooo or ooooxxxx within 4 steps

How about 5, 6, 7, ...
Can you prove?
testposttestposttestpost

mars15

  • Newbie
  • *
  • Posts: 8
Re: Number game
« Reply #5 on: 十二月 05, 2005, 04:56:56 pm »
If you can make xxxxoooo to oxoxoxox or xoxoxoxo, you absolutely can make
oxoxoxox to xxxxoooo or ooooxxxx.
For any positive integer "n" greater than 2 (n>2), we can easily let "n" of "o" and "n" of "x"
, (for example, oooooxxxxx, ooooooxxxxxx) each time change 2 adjacent within "n" steps

change to "n" pairs of "ox" or "xo" (oxoxoxoxox, xoxoxoxoxoxo, ...).

The key is you should know the rules.
3(0), 4(1,2), 5(1,1), 6(1,3,0), 7(1,2,1), 8(1,2,2,2), 9(1,2,2,1), 10(1,2,2,3,0)

Did you find the similarity of above rules?

1. There are three groups: The first is 3,5,7,9,..(odd), the second is 6,10,14,...(single even)
    , and the third is 4, 8,12,...(double even).
2. Odd:(1,...(m of 2),1) m=n/2-2.5 ; n>3; when n=5, m=0(none),n=7, m=1
3. Single even: (1, ...(m of 2),3,0) m=n/2-3; n>=6,; when n=6, m=0, n=10, m=2
4. Double even: (1,...(m of 2),2) m=n/2-2; n>=4; when n=4, m=0, n=8, m=2
5. in (), show the steps you should move "oo" or "xx".

3(0)
OOOXXX
_ _ OXXXOO
_ _ OXX_ _ OXO
_ _ _ _ XOXOXO
(o) means take the most outside two adjacent in the first step.
4(1,2)
OOOOXXXX
O_ _ OXXXXOO
OXXO_ _ XXOO
OXXOXOX_ _ O
_ _ XOXOXOXO
(1,2) means the first step you should remain 1 in the most outside position, and the second

step remain 2 in the other side (from the original most outside).
5(1,1)
OOOOOXXXXX
O_ _ OOXXXXXOO
OXXOOXX_ _ XOO
OXXO_ _ XOXXOO
OXXOXOXOX_ _ O
_ _ XOXOXOXOXO
(1,1) means the first step you should remain 1 in the most outside position, and the second

step remain 1 in the other side (from the original most outside).
6
OOOOOOXXXXXX
O_ _ OOOXXXXXXOO
OXXOOOX_ _ XXXOO
OXX_ _ OXOOXXXOO
OXXOXOXO_ _ XXOO
OXXOXOXOXOX_ _ O
_ _ XOXOXOXOXOXO
(1,3,0) means the first step you should remain 1 in the most outside position,  the second step

remain 3 in the other side (from the original most outside), and the third time you should not

remain any in the previous (and back to the side) added adjacent position.
7 (1,2,1)
OOOOOOOXXXXXXX
O_ _ OOOOXXXXXXXOO
OXXOOOOXXX_ _ XXOO
OXXO_ _ OXXXOOXXOO
OXXOXOOXX_ _ OXXOO
OXXOXO_ _ XOXOXXOO
OXXOXOXOXOXOX_ _ O
_ _ XOXOXOXOXOXOXO

8 (1,2,2,2)
OOOOOOOOXXXXXXXX
O_ _ OOOOOXXXXXXXXOO
OXXOOOOOXXXX_ _ XXOO
OXXOO_ _ OXXXXOOXXOO
OXXOOXXO_ _ XXOOXXOO
OXXOOXXOXOX_ _ OXXOO
OXXO_ _ XOXOXOXOXXOO
OXXOXOXOXOXOXOX_ _ O
_ _ XOXOXOXOXOXOXOXO

9 (1,2,2,1)
OOOOOOOOOXXXXXXXXX
O_ _ OOOOOOXXXXXXXXXOO
OXXOOOOOOXXXXX_ _ XXOO
OXXOO_ _ OOXXXXXOOXXOO
OXXOOXXOOXX_ _ XOOXXOO
OXXOOXXO_ _ XOXXOOXXOO
OXXOOXXOXOXOX_ _ OXXOO
OXXO_ _ XOXOXOXOXOXXOO
OXXOXOXOXOXOXOXOX_ _ O
_ _ XOXOXOXOXOXOXOXOXO

14 (1,2,2,2,2,3,0)
OOOOOOOOOOOOOOXXXXXXXXXXXXXX
O_ _ OOOOOOOOOOOXXXXXXXXXXXXXXOO
OXXOOOOOOOOOOOXXXXXXXXXX_ _ XXOO
OXXOO_ _ OOOOOOOXXXXXXXXXXOOXXOO
OXXOOXXOOOOOOOXXXXXX_ _ XXOOXXOO
OXXOOXXOO_ _ OOOXXXXXXOOXXOOXXOO
OXXOOXXOOXXOOOX_ _ XXXOOXXOOXXOO
OXXOOXXOOXX_ _ OXOOXXXOOXXOOXXOO
OXXOOXXO_ _ XOXOXOOXXXOOXXOOXXOO
OXXOOXXOXOXOXOXOOXXXOOXXOOX_ _ O
OXXO_ _ XOXOXOXOXOOXXXOOXXOOXOXO
OXXOXOXOXOXOXOXOOXXXOOX_ _ OXOXO
OXXOXOXOXOXOXOXO_ _ XXOOXOXOXOXO
OXXOXOXOXOXOXOXOXOX_ _ OXOXOXOXO
_ _ XOXOXOXOXOXOXOXOXOXOXOXOXOXO


You can just reverse them to get the answer from
xoxoxoxo to ooooxxxx or problems of any n>2 positive integer.
An example:

10+10(1,2,2,3,0)
OOOOOOOOOOXXXXXXXXXX
O_ _ OOOOOOOXXXXXXXXXXOO
OXXOOOOOOOXXXXXX_ _ XXOO
OXXOO_ _ OOOXXXXXXOOXXOO
OXXOOXXOOOX_ _ XXXOOXXOO
OXXOOXX_ _ OXOOXXXOOXXOO
OXXOOXXOXOXO_ _ XXOOXXOO
OXXOOXXOXOXOXOX_ _ OXXOO
OXXO_ _ XOXOXOXOXOXOXXOO
OXXOXOXOXOXOXOXOXOX_ _ O
_ _ XOXOXOXOXOXOXOXOXOXO

_ _ XOXOXOXOXOXOXOXOXOXO
OXXOXOXOXOXOXOXOXOX_ _ O
OXXO_ _ XOXOXOXOXOXOXXOO
OXXOOXXOXOXOXOX_ _ OXXOO
OXXOOXXOXOXO_ _ XXOOXXOO
OXXOOXX_ _ OXOOXXXOOXXOO
OXXOOXXOOOX_ _ XXXOOXXOO
OXXOO_ _ OOOXXXXXXOOXXOO
OXXOOOOOOOXXXXXX_ _ XXOO
O_ _ OOOOOOOXXXXXXXXXXOO
OOOOOOOOOOXXXXXXXXXX