This was a tough one! So the problem is to find how many ways to get from one side of a 20x20 chessboard without backtracking.
As a simple example.. starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.
So the answer is to think about the problem rather differently… in fact the question is to use 20 Rights and 20 Downs to get across the chessboard… so how many combinations are there to arrange 20R and 20D?? So now it’s a combination problem which means we can use some stats..
The formula is n! / r! (n-r)!
Where n is 40 and r is 20… so 40!/(20! * 20!)
Which gives us: 137846528820 ways to get there!
In fact Google’s online calculator can do this for you….
Just type 40 choose 20 into Google!!
No comments:
Post a Comment