IBM Puzzle December 2008 Challenge
Source: #-Link-Snipped-#
Consider a random walk on the 2-d integer lattice starting at (0,0). From a lattice point (i,j) the walk moves to one of the four points (i-1, j), (i+1, j), (i, j-1) or (i, j+1) with equal probability. The walk continues until four different points (including (0,0)) have been visited. These four points will form one of the five tetrominoes (considering mirror images to be the same). For each tetromino find the probability that it will be the one formed in this way.
Please make sure you clearly identify the tetrominoes when submitting a solution. You may wish to use the wikipedia letter designations, I,L,O,S and T. A few solutions did not receive credit
because I could not tell which tetrominoes were which. Also I am requiring exact values for the probabilities.
Consider a random walk on the 2-d integer lattice starting at (0,0). From a lattice point (i,j) the walk moves to one of the four points (i-1, j), (i+1, j), (i, j-1) or (i, j+1) with equal probability. The walk continues until four different points (including (0,0)) have been visited. These four points will form one of the five tetrominoes (considering mirror images to be the same). For each tetromino find the probability that it will be the one formed in this way.
Please make sure you clearly identify the tetrominoes when submitting a solution. You may wish to use the wikipedia letter designations, I,L,O,S and T. A few solutions did not receive credit
because I could not tell which tetrominoes were which. Also I am requiring exact values for the probabilities.
Replies
-
durga chI don't understand it much 😕 -
Kaustubh KatdareNo one tried this one. Here is the solution -
Source: #-Link-Snipped-#
XXX = 8/21
X
XX = 4/21
xx
XX = 4/21
xx
XXX = 3/21
x
XXXX = 2/21
They can be found by working out the transition probabilities from smaller forms. The calculations are simplified by taking symmetry into account. For example at each step the unique domino has a 1/2 probability of becoming a bent tromino, a 1/4 probability of becoming a straight tromino and a 1/4 probability of remaining a domino. So the random walk has a 2/3 probability of forming the bent tromino and a 1/3 probability of forming the straight tromino. Similarly one can compute the probability of transitioning from each tromino to each tetromino (keeping track of whether the walker is in the middle or at the end of the tromino). Then sum over the ways of forming each tetromino to find the values above. I omit the details.
You are reading an archived discussion.
Related Posts
glad been here folks, a newbie computer engineer from the Philippines......
I wish all our fellow CEans a very
HaPpy & Prosperous New Year 2009​
May your life be filled with eternal joy. May your dreams come true. May you change...
Hi all,
I need formula to find skew and flight time(Printed circuit traces).
Please help me!
Hi there,
I'm trying to solve this heat conduction problem using boundary element methods. The problem involves a circle that is cut into half, with each having its own thermal...
Hi,
I am working as system admin in unix, solaris, network for 1.5 years and also have entry knowledge of veritas and sun volume manager and dont have much kernel...