My Math Forum  

Go Back   My Math Forum > High School Math Forum > Probability and Statistics

Probability and Statistics Basic Probability and Statistics Math Forum


Thanks Tree2Thanks
  • 1 Post By romsek
  • 1 Post By romsek
Reply
 
LinkBack Thread Tools Display Modes
January 28th, 2017, 11:54 AM   #1
Newbie
 
Joined: Jan 2017
From: London

Posts: 10
Thanks: 0

Chessboard Different Routes Problem

On a chessboard, a king is to be allowed to move one square at a time: horizontally to the right, vertically downward, or diagonally to the right and downward. Imagine a reduced 4x4 chessboard, with the king beginning in the top-left square. By how many routes can he reach the bottom right square? By how many routes can a similar journey be made on a full 8x8 chessboard?

I tried to find for an answer, but there seemed to be a very large number of possibilities. Can anyone help?
Estermont is offline  
 
January 28th, 2017, 07:41 PM   #2
Senior Member
 
romsek's Avatar
 
Joined: Sep 2015
From: Southern California, USA

Posts: 1,397
Thanks: 709

Quote:
Originally Posted by Estermont View Post
On a chessboard, a king is to be allowed to move one square at a time: horizontally to the right, vertically downward, or diagonally to the right and downward. Imagine a reduced 4x4 chessboard, with the king beginning in the top-left square. By how many routes can he reach the bottom right square? By how many routes can a similar journey be made on a full 8x8 chessboard?

I tried to find for an answer, but there seemed to be a very large number of possibilities. Can anyone help?
Let's label paths as a trinary number
0: right
1: down/right
2: down

We'll look at the $4 \times 4$ matrix and then generalize it to $n \times n$

The following numbers will start at square $(1,1)$ and end at square $(4,4)$

$\begin{matrix}
\text{# 1's} &\text{# 0's} &\text{# 2's} &\text{total #}\\
0 &3 &3 &(6C0)(6C3)=20\\
1 &2 &2 &(5C1)(4C2)=30\\
2 &1 &1 &(4C2)(2C1)=12\\
3 &0 &0 &(3C3) = 1
\end{matrix}$

for a total of $63$ paths leading from $(1,1)$ to $(4,4)$

You should be able to see the pattern in the table.

Generalizing to an $n \times n$ chessboard we would get

$npaths = \displaystyle{\sum _{k=0}^{n-1}} \binom{2 (n-1)-k}{k} \binom{2 (n-1)-2 k}{n-k-1}$

This does have a sort of closed form

$\Large npaths(n) = \binom{2 (n-1)}{n-1} \, _2F_1(1-n,1-n;2-2 n;-1)$

see link below for explanation of

$_2F_1(1-n,1-n;2-2 n;-1)$

At any rate an $8\times 8$ chessboard has $48639$ possible paths to get from top left to bottom right
Thanks from Estermont
romsek is offline  
February 4th, 2017, 02:26 PM   #3
Newbie
 
Joined: Jan 2017
From: London

Posts: 10
Thanks: 0

I understand everything until you get to the point where you say that a pattern can be seen... Could you please explain the pattern and how it leads to what you say after?
Estermont is offline  
February 4th, 2017, 07:39 PM   #4
Senior Member
 
romsek's Avatar
 
Joined: Sep 2015
From: Southern California, USA

Posts: 1,397
Thanks: 709

Quote:
Originally Posted by Estermont View Post
I understand everything until you get to the point where you say that a pattern can be seen... Could you please explain the pattern and how it leads to what you say after?
look at the # of 1's and the total # column in the table

and match up those two binomial coefficient factors with those given in the expression for npaths a bit below that
Thanks from Estermont
romsek is offline  
February 26th, 2017, 05:08 AM   #5
Newbie
 
Joined: Feb 2017
From: UK

Posts: 1
Thanks: 0

Quote:
Originally Posted by romsek View Post
Let's label paths as a trinary number
0: right
1: down/right
2: down

We'll look at the $4 \times 4$ matrix and then generalize it to $n \times n$

The following numbers will start at square $(1,1)$ and end at square $(4,4)$

$\begin{matrix}
\text{# 1's} &\text{# 0's} &\text{# 2's} &\text{total #}\\
0 &3 &3 &(6C0)(6C3)=20\\
1 &2 &2 &(5C1)(4C2)=30\\
2 &1 &1 &(4C2)(2C1)=12\\
3 &0 &0 &(3C3) = 1
\end{matrix}$

for a total of $63$ paths leading from $(1,1)$ to $(4,4)$

You should be able to see the pattern in the table.

Generalizing to an $n \times n$ chessboard we would get

$npaths = \displaystyle{\sum _{k=0}^{n-1}} \binom{2 (n-1)-k}{k} \binom{2 (n-1)-2 k}{n-k-1}$

This does have a sort of closed form

$\Large npaths(n) = \binom{2 (n-1)}{n-1} \, _2F_1(1-n,1-n;2-2 n;-1)$

see link below for explanation of

$_2F_1(1-n,1-n;2-2 n;-1)$

At any rate an $8\times 8$ chessboard has $48639$ possible paths to get from top left to bottom right

How did you get the total numbers on the matrix
Mathshelpplease is offline  
Reply

  My Math Forum > High School Math Forum > Probability and Statistics

Tags
chessboard, problem, routes



Search tags for this page
Click on a term to search for related topics.
Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
a chessboard problem wuzhe Math Events 9 June 27th, 2012 11:41 AM
a chessboard set up problem wuzhe Algebra 1 August 11th, 2011 10:15 AM
A Chessboard Problem jason.spade Math Events 4 May 17th, 2010 10:47 AM





Copyright © 2017 My Math Forum. All rights reserved.