Saturday, April 24, 2010

Board Game

The Chess board is divided into 64 regular squares. The Go board is also divided into regular squares. The Hex board is divided into regular hexagons. The Risk board is divided into irregular regions. What if dividing the board into regions was part of the game. Each player could take turns placing points or linear boundaries in a space.
I can imagine more than one possible goal in such a game. The goal could be to have the most regions containing only friendly points. Or, the goal could be to have the most regions with friendly point majorities. The game could be played by two or more people. It could be limited by number of moves or by time. It could be scored at the end, or the score could be averaged over number of moves or time. The game could be played in any number of dimensions. Two dimensions would be significantly easier than three, and four dimensions would be extremely difficult.
This game could only be played on a computer because pencil and paper could not produce precise enough lines. A computer could zoom in on detailed portions of the game space. Larger structures could be represented together with smaller ones by using spherical projection or something. I have no idea how higher dimensional game spaces could be displayed. I think each player would prepare for such a game by writing a program to make the moves understandable.
I would restrict the moves such that no played point lies on a boundary. I would also restrict boundary moves such that no two boundaries are parallel, and no more than n boundaries share a point in an n dimensional game. And, I would restrict point and boundary moves as follows. Taking played points and boundary intersection points as origins, I would restrict point moves and boundary moves such that no set of fewer than n+1 played points and/or boundary intersection points are linearly dependent in an n dimensional game. For example, a move which put 3 played points on the same line, or 2 played points and 2 intersection points on the same plane, would be illegal. One motivation for these restrictions is that moves would not have to be infinitely precise. Moves would have a little wiggle room without affecting the game play. This is important to accommodate rounding errors in the computer. In my opinion, another motivation for these restrictions is that it is more realistic. What are the chances of 3 unrelated points being on the same line in real life?

Friday, February 5, 2010

Counting Linear Regions

The question "how many" has motivated me in what little math I have done. For example, how many tetrahedron overlaps are there? That led me to the question of how many equivalent linear spaces there are. I used a recursive formula to define linear space in the first entry on this blog. Now I will present the closed form for f(d,b), the number of nonempty regions in a linear space of d dimensions and b boundaries. For example,
f(3,b) = 1 + b + x=0..b−1x + y=0..b−1x=0..y−1x
By definition,
f(d,b) =
f(d,b−1) + f(d−1,b−1) =
f(d,b−2) + f(d−1,b−2) + f(d−1,b−1) =
f(d,0) + f(d−1,0) + f(d−1,1) + f(d−1,2) + ... + f(d−1,b−1) =
1 + x=0..b−1f(d−1,x) =
1 + y=0..b−1(1+∑x=0..y−1f(d−2,x)) =
1 + b + y=0..b−1x=0..y−1f(d−2,x) =

Removing subscripts for brevity,
1 + b + ∑∑f(d−2,x) =
01 + 11 + 2(1+∑f(d−3,x)) =
01 + 11 + 21+∑3f(d−3,x) =
01 + 11 + ... + d−11 + df(0,x) =
0 + 1 + ... + d−1 + d =

I have always liked figurate numbers. For example, the triangular numbers are 1, 3, 6, 10, 15, .... Consider points on a page. Each line has one more point than the last. Then the total number of points is 2, the triangular number P2(b−1). Now make a stack of pages with successive triangular numbers on them. The total number of points in the stack is 3, the tetrahedral number P3(b−2). In general, d is the polytopic number Pd(b−d+1). The diagonals of Pascal's triangle of binomial coefficients are the polytopic numbers. Thus, d = Pd(b−d+1) = (b+1)!/d!(b−d+1)!, and f(d,b) = x>−1,x<d+1,x<b+1(b+1)!/x!(b−x+1)!.