Our website would like to use cookies to store information on your computer. You may delete and block all cookies from this site, but parts of the site will not work as a result. Find out more about how we use cookies.
 Keyword Search: Advanced Search

 How to handle a half in integer arithmetic.
 by Hugo van der Sanden at 23:50 24/04/07 (Blogs::Hugo)
 I've been doing some sums involving floor(n/2).

I've been toying with another calculation: in this case, trying to enumerate the number of ways a rectangular m x n grid can be annotated to be a valid game of ''Arukone'' (also called Number Link.

Say your game has labels A, B, and C. Then the game involves finding 3 paths simultaneously - one path joining the two A labels, one for the Bs and one for the Cs - such that each square in the grid is traversed exactly once by some path. Eg:

ProblemSolution
 A B . . . . . . C . . . . . . . B . . . . . . C A
 A B A A A A B A C A A B A C A A B A C A A A A C A

So the enumeration is trying to count, for an m x n grid, how many ways it is possible to label some 2p of the squares such that it is possible to traverse all the squares exactly once by the paths joining corresponding labels.

I looked first at the 1 x n case, which turned out to be quite straightforward. The 2 x n case quickly got rather harder though, so I tried to decompose the problem further by finding the counts for a specific number of label pairs. And again, the p=1 case turned out to be easy, and the p=2 case turned out to be hard.

In fact, I've managed to break down the p=2 case into 32 classes, for each of which I know (well, I think I know) an expression for the number of possibilities, expressed as a double sum:

ABCD
[0, 0](j - 1)2(j - 1)200
[-, 0']k v(j - 1)k v(j - 1)k v(j - 1) - c(j = 1)k v(j - 1) - c(j = 1)
[-, +]0v(j - 1) v(n - s)v(j - 1) v(n - s)0
[0, 0]k (k - 1) / 2k (k + 1) / 2k (k - 1) / 2(k - 1) (k - 2) / 2
[0', 0']k (k - 1) / 2k (k - 1) / 2(k - 1) (k - 2) / 2(k - 1) (k - 2) / 2
[0, +]k v(n - s)00k v(n - s) - c(n = s)
[0', +]0k v(n - s)k v(n - s) - c(n = s)0
[+, +](n - s)2(n - s)200

8 of those entries are 0, so life is good - only 24 sums to calculate.

Things are made slightly trickier though by the nature of k in those expressions - in the case A above, we need to iterate j over the values 1 ... n, and iterate k over the values 0 ... (n-j)/2. And since it takes only integer values, that limit is actually floor((n - j)/2).

I wasn't too sure how to do maths with that, so I played around a bit, and found it was easiest if I defined an auxiliary function m(x) to be 0 when x is even, and 1 when x is odd.

Now this has some handy properties:

• floor(x / 2) = (x - m(x)) / 2
• m(x)2 = m(x)
• m(x) + m(x + 1) = 1
• sum_{x = 0}^{n}{m(x)} = (n + m(n)) / 2
• sum_{x = 0}^{n}{x m(x)} = (n + m(n))2 / 4

.. as a result of which I've now managed to evaluate 4 of those sums. Just 20 more to go ...

I also am now prepared if a future problem needs a floor(n / 3) or similar, since I know I'll need a similar auxiliary - it is effectively a modulo function.

Hugo

 << The logical next step Religion (2) >> How to handle a half in intege... Hugo van der Sanden - 24/04 Re: How to handle a half in in... Bruce Ure - 25/04 Re: How to handle a half in in... Steve - 25/04 Re: How to handle a half in in... Hugo van der Sanden - 26/04