Euler Problem 85

This one has to do with combinatorics. Here is a page that contain a formula to solve all permutations on a m x n grid.
http://www.gottfriedville.net/mathprob/comb-subrect.html

I used a simple quadratic equation to determine that if one dimension never exceeds 1, then the other cannot exceed 2000 (roughly). So I just created a nested loop for m & n and tested for a smaller and smaller delta.

class Problem:
    def Solution(self):
        mBest = 0
        nBest = 0
        delta = 2000000
        goal = 2000000
        for m in range (1,2001):
            for n in range (1, 2001):
                test = m*(m+1)*n*(n+1)/4
                if abs(test-goal) < delta:
                    mBest = m
                    nBest = n
                    delta = abs(test-goal)
            if m % 100 == 0:
                print m,
        print "\nBest m, Best n, Delta =", mBest, nBest, delta
        print "Answer =", mBest*nBest
if __name__ == '__main__':
    P = Problem()
    P.Solution()

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s