Expected Value

Revision en1, by gXa, 2018-10-03 12:06:32

A square grid(NxN) is given to you; Each location on the grid is either a brick (B) or its empty (_).

The total number of bricks is exactly equal to as much is required to build a “wall” in the grid. See example for clearer understanding.

That is, at the end , all bricks(B) should be placed at boundary locations.

For moving a brick from location <x,y> to <i,j> |i-x| + |j-y| fuel is used.

Each brick in the grid can be moved to any location on the boundary with equal probability. What is the expected value of the fuel required to do so? Each brick can be moved at-most once.

In the end (after moving all the bricks), the grid should look like:

 B B B B
 B _ _ B
 B _ _ B
 B B B B
Tags expectation

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English gXa 2018-10-03 12:09:50 21
en1 English gXa 2018-10-03 12:06:32 746 Initial revision (published)