Jump to content
BrainDen.com - Brain Teasers
  • 0

chess board riddle


jake_harper
 Share

Question

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

Link to comment
Share on other sites

6 answers to this question

Recommended Posts

  • 0

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.

Link to comment
Share on other sites

  • 0

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

Link to comment
Share on other sites

  • 0

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
Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...