**Drat on a tesseract...?**

Answers:1 | LastAnswerAt:2010.10

**Q**uestion

- Zo Maar
- Asked at 2010.10.12 23:52:09

answer Ã¢ËœÂ® VaÃ…Â¡ek Answered at 2010.10.12 23:52:09

Let's further denote n(k) the average number of jumps the drat undergoes when starting in the set A_k until it hits A_0. We can do this due to the high degree of symmetry of the tesseract. We will fix n(0) at zero, and n(4) is what you are asking for.

From A_4 = {start}, any possible step ends in A_3. Thus:

n(4) = 1 + n(3).

From any point in A_3, there are three ways to A_2 and one back to A_4. The probabilities are distributed accordingly. This produces an equation:

n(3) = 3/4 * (1 + n(2)) + 1/4 * (1 + n(4)),

which can be expanded and simplified to

n(3) = 1 + 3/4*n(2) + 1/4*n(4).

Analogically, we will find out that

n(2) = 1 + 1/2*n(3) + 1/2*n(1)

and

n(1) = 1 + 3/4*n(2) + 1/4*n(0) = 1 + 3/4*n(2).

This is a system of four linear equations with four unknowns, n(1) through n(4). The complete solution is

n(1) = 15

n(2) = 56/3 = 18.67

n(3) = 61/3 = 20.33

n(4) = 64/3 = 21.33,

thus the answer is 21 and one third of a jump on average.

jaz_will:

Let me defend my answer. Imagine that the drat is staying at a distance 1 from the target vertex. One edge of the connection graph leads to the target while three other ones will lead it farther to distance 2. Thus, with probability 1/4, we will count exactly one step, and with probability 3/4, we will count one step plus the number of steps from distance 2, which is n(2). Thus indeed

n(1) = 1/4 * (1) + 3/4 * (1 + n(2)) = 1 + 3/4*n(2).

I am quite sure about my approach, I have tested it directly in a smaller dimension.

Dragan K:

You have to count the number of edges between the layers.

Edit2:

Also, right now, I wrote a small simulation program modelling the given situation and it gives results about 21.333. You will find it listed below in case you want to go through it and tell me about an error there.

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#define D 4

#define N 1000000

int pokus() {

int a = (1<<D)-1;

int s = 0;

do {

a ^= (1 << (rand()%D));

s++;

} while (a);

return s;

}

int main() {

int n;

unsigned long v = 0;

srand(time(NULL));

for(n = 0; n < N; n++)

v += pokus();

printf("%fn", (float)v / N);

return 0;

}

Related Questions

**1**