Puzzles/Statistical puzzles/A Bug Running

Puzzles | Statistical puzzles | A bug running

Consider a chess board of dimension $8 \times 8$ :

 -- -- -- -- -- -- -- -- 
|  |  |  |  |  |  |  | F|
 -- -- -- -- -- -- -- -- 
|  |  |  |  |  |  |  |  |
 -- -- -- -- -- -- -- -- 
|  |  |  |  |  |  |  |  |
 -- -- -- -- -- -- -- -- 
|  |  |  |  |  |  |  |  |
 -- -- -- -- -- -- -- -- 
|  |  |  |  |  |  |  |  |
 -- -- -- -- -- -- -- -- 
|  |  |  |  |  |  |  |  |
 -- -- -- -- -- -- -- -- 
|  |  |  |  |  |  |  |  |
 -- -- -- -- -- -- -- -- 
|B |  |  |  |  |  |  |  |
 -- -- -- -- -- -- -- --

A bug sits in the lower left corner and intends to reach the upper right corner, where food is present ready to be consumed. Given that the bug can only move either right or up, how many possible unique paths lead to the food?
Given the board is $n \times n$ , how many paths do exist?
Given the board is three dimensional $n \times n \times n$ , bug and food in opposite corners and movements are steps in positive directions in either dimension, how many paths do exist?
Given the board is $k$ dimensional $n^k$ , bug and food in opposite corners and movements are steps in positive directions in either dimension, how many paths do exist?

Consider again the $8 \times 8$ setting.

 -- -- -- -- -- -- -- -- 
|  |  |  |  |  |  |  | F|
 -- -- -- -- -- -- -- -- 
|  |  |  |  |  |  |  |  |
 -- -- -- -- -- -- -- -- 
|  |  |  |  |  |  |  |  |
 -- -- -- -- -- -- -- -- 
|  |  |  | *| *|  |  |  |
 -- -- -- -- -- -- -- -- 
|  |  |  | *| *|  |  |  |
 -- -- -- -- -- -- -- -- 
|  |  |  |  |  |  |  |  |
 -- -- -- -- -- -- -- -- 
|  |  |  |  |  |  |  |  |
 -- -- -- -- -- -- -- -- 
|B |  |  |  |  |  |  |  |
 -- -- -- -- -- -- -- --

The question again is about the number of paths, but this time 4 squares are blocked in the center (marked by '*'s) that the bug is not allowed to touch (for they are sticky with glue and would trap the bug thus making it starve). What is the number of allowed paths?

Solution

This article is issued from Wikibooks. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.