• 0

chess board riddle

Question

Posted · Report post

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

0

Share this post


Link to post
Share on other sites

6 answers to this question

  • 0

Posted · Report post

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

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 16C8 = 12870.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

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 16C8 = 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.1043ig5.jpg

0

Share this post


Link to post
Share on other sites
  • 0

Posted (edited) · Report post

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
1

Share this post


Link to post
Share on other sites
  • 0

Posted (edited) · Report post

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.

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

14C7= 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 212 . 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
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

Thank you all

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.