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.

Login or Register

Powered by
Powered by Novacaster
 
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
AB...
...C.
.....
.B...
...CA
ABAAA
ABACA
ABACA
ABACA
AAACA

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) >>
View Comments (Threaded Mode) Printer Version
How to handle a half in integer arithmetic. Hugo van der Sanden - 23:50 24/04/07
Re: How to handle a half in integer arithmetic. Bruce Ure - 11:55 25/04/07
Yep, that's pretty much what I found.

--

Re: How to handle a half in integer arithmetic. Steve - 18:41 25/04/07
I bet you solve hard Sudoku puzzles in less than 5 minutes. You math whiz, you.

Out of curiosity, what software did you use to compose that message? Did you actually create the tables directly in the Novacaster editor?

--
stevepa

Re: How to handle a half in integer arithmetic. Hugo van der Sanden - 12:50 26/04/07
I got bored with Sudoku a while back, though I still do the Killer Sudoku problems sometimes.

And yes, I wrote the HTML straight into the Novacaster editor.

Hugo