6 replies to this topic

[jake_harper]

I came across this somewhere on the web.

 

A pawn is sitting at one corner of an 8X8 chess board. It can take one step at a time in the horizontal or vertical direction (not diagonal). What is total number of ways in which it can reach the diagonally opposite end given that the pawn always tries to go towards the destination (i.e. no back-tracking).

 

 

I came up with an answer. Wanted to see whether it is the correct approach. Thank you

Hope you will enjoy

[bushindo]

I came across this somewhere on the web.

 

A pawn is sitting at one corner of an 8X8 chess board. It can take one step at a time in the horizontal or vertical direction (not diagonal). What is total number of ways in which it can reach the diagonally opposite end given that the pawn always tries to go towards the destination (i.e. no back-tracking).

 

 

I came up with an answer. Wanted to see whether it is the correct approach. Thank you

Hope you will enjoy

 

My guess

Spoiler for

Let's say that the pawn is in the lower left corner. It has to go up 8 times and right 8 times to get the the other corner. This makes the total number of ways ₁₆C₈ = 12870.

[jake_harper]

I came across this somewhere on the web.

 

A pawn is sitting at one corner of an 8X8 chess board. It can take one step at a time in the horizontal or vertical direction (not diagonal). What is total number of ways in which it can reach the diagonally opposite end given that the pawn always tries to go towards the destination (i.e. no back-tracking).

 

 

I came up with an answer. Wanted to see whether it is the correct approach. Thank you

Hope you will enjoy

 

My guess

Spoiler for

Let's say that the pawn is in the lower left corner. It has to go up 8 times and right 8 times to get the the other corner. This makes the total number of ways ₁₆C₈ = 12870.

Can you explain why you limit the number of squares that can form a path to 16? Shouldn't it be 64-2=62.

The approach I took was a bit different.

assume the pawn starts from the bottom right square. According to the given condition he can move to any square on the board while reaching the target. The pawn has two options at each square except for the squares lying on the leftmost column and topmost row (see the attached image)

 

based on this: 2*(64-2-14)*14 is my answer.

[phil1882]

Spoiler for actual answer

 

0 1  1   1   1   1    1  1
1 2  3   4   5   6    7  8
1 3  6  10  15  21   28 36
1 4 10  20  35  56   84 120
1 5 15  35  70 126  210 330
1 6 21  56 126 252  462 792
1 7 28  84 210 462  924 1716
1 8 36 120 330 792 1716 3432

Edited by phil1882, 30 January 2013 - 07:56 AM.

[Prime]

Hello Jake. Welcome to the Den.

Bushindo's answer has the right logic. His numbers are slightly off. I'll put my solution inside Spoiler, to let other people tackle this problem on their own.

 

Spoiler for solution

In accordance with OP conditions the pawn will make exactly 14 moves to reach its destination. Exactly 7 of those moves shall be in upward direction and 7 to the side. Different mixes of "up" and "side" will produce ₁₄C₇= 14! / (14-7)! / 7! = 3432 variations. This is a simple perspective yielding a simple solution.

Your method is more complex. It requires rasing to power, rather than multiplication. Seems something to the tune 2¹² . Then we'd have to take into account that different paths intersect and share some squares. Complexity of this perspective compounds making solution impossible.

Edited by Prime, 30 January 2013 - 08:40 AM.

[jake_harper]

Thank you all

[bonanova]

Another difference in people's answers might stem from the "no backtracking" stricture in the OP.

Bushindo interpreted that to mean only up and only right [no down and no left] moves may be made.

 

A less restrictive interpretation would give a higher answer.

One such might permit revisiting a previously occupied square but not to retracing any piece of your path.

That is, not reversing any previous move between squares.

 

No backtracking, therefore, should be clarified.