0

I have to find the Number of N X M matrices containing a 1 in the top left entry, all entries are integer values and adjacent entries differ by at most 1, knowing that N is at most 5 and M can go up to 10^9. Obviously a backtracking algorithm is not fast enough, and i think that this problem can be solved using matrix exponentiation, but i do not have any ideea further this point. Thanks in advance!

4
  • I don't think matrix multiplication is the way to go. I'm thinking along the lines of dynamic programming. If there's any chance for a closed formula or a semi-famous number series (I think there's a decent chance of a semi-famous number series) you should ask at Mathematics instead of here. Dec 27, 2012 at 21:16
  • What have you tried? What language are you using?
    – Foggzie
    Dec 27, 2012 at 21:17
  • Oops, I missed the "N is at most 5". That kinda... simplifes things, and a matrix multiplication is the way to go. What have you tried? Dec 27, 2012 at 21:19
  • I have an ideea of generating the possibilites for the first 2 columns and then try to create a state which represents a column and use matrix multiplication on this. Dec 27, 2012 at 21:24

1 Answer 1

0

Every row is in the following form:

x (y=x+1/x/x-1) (z=y+1/y/y-1) ...

The value of x doesn't really matter, so (for N = 5) there are 3^4 = 81 possibilities for each row.

From here you write a simple program to determine which possibilities appear how often in the next row for each of these 81 possibilities in the current row.

From there you should be able to figure out a formula if there is a simple one, otherwise you have a O(10^9) algorithm, which is at least better than what you started with.

"at most" and "can go up to" does mess with the algorithm a bit.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.