Ponder This

April 2006

<<March April May>>

Ponder This Challenge:

Puzzle for April 2006.

This month's puzzle concerns random walks on a n-dimensional hypercube. Each step of the random walk moves from one of the 2**n vertices of the hypercube to one of the n adjacent vertices selected at random. The vertices of a n-dimensional hypercube can be identified with length n 0-1 vectors in an obvious way. Consider random walks starting at the vertex (0,0,....,0). We want to know how many steps on average it will take for the random walk to reach the diagonally opposite vertex. This can be found by answering the following questions.

1. How many steps on average does it take the random walk to return to its starting point?

2. How many steps on average does it take the random walk to return to its starting point or reach the diagonally opposite vertex (ie the vertex (1,1,...,1))?

3. What is the probability that the random walk reaches the diagonally opposite vertex before it returns to its starting point?

4. How many steps on average does it take the random walk to reach the diagonally opposite vertex?

The first 100 people who answer all 4 parts correctly will be listed. The answer will be posted a week after the 100th is received, or at the end of the month.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

  

Challenge: 03/31/2006 @ 12:00 PM EST
Solution: 05/01/2006 @ 09:00 AM EST
List Updated: 03/31/2006 @ 12:00 PM EST

People who answered correctly:

Graeme McRae (04.02.2006 @08:44:47 AM EDT)
Balakrishnan V (04.02.2006 @05:40:21 PM EDT)
Roberto Tauraso (04.03.2006 @04:43:46 AM EDT)
Frank Yang (04.04.2006 @10:18:07 AM EDT)
Dan Dima (04.10.2006 @04:56:12 PM EDT)
John G. Fletcher (04.10.2006 @07:36:05 PM EDT)
Zhou Guang (04.10.2006 @10:00:35 PM EDT)
Jomy (04.15.2006 @03:09:47 AM EDT)
Jack Kennedy (04.15.2006 @05:58:33 PM EDT)
Se Kwon Kim (04.16.2006 @11:04:52 PM EDT)
Frank Mullin (04.19.2006 @08:40:05 AM EDT)
David Wolfe (04.20.2006 @01:35:10 PM EDT)
Phil Muhm (04.20.2006 @10:44:16 PM EDT)
Dinesh (04.21.2006 @02:18:19 PM EDT)
Dharmadeep Muppalla (04.24.2006 @10:46:54 AM EDT)
Rubén Hernández Aza (04.24.2006 @03:53:37 PM EDT)
Bernie R. Erickson (04.24.2006 @05:13:55 PM EDT)
David McQuillan (04.26.2006 @06:12:35 PM EDT)
Yurun Liu (04.30.2006 @09:58:25 PM EDT)

Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.