Ask Question and Get Free Answers - JUST Ask And Answer > QA > Science & Mathematics > Mathematics
Drat on a tesseract...?

Answers:1   |   LastAnswerAt:2010.10  

Zo Maar 
Asked at 2010.10.12 23:52:09
Drat sits on a tesseract vertex. She repeatedly jumps with the equal probability to one of the four neighboring vertices. After how many jumps (in average) will drat land on the opposite vertex?
answer ☮ VaÅ¡ek  Answered at 2010.10.12 23:52:09
Let's divide the vertices into groups by their distance from the target vertex and call these subsets A_k, where k in {0,1,2,3,4} is the distance. The sets A_0 and A_4 contain one element each which are the end and the start, respectively.

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)
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.

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.

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));
} while (a);
return s;

int main() {
int n;
unsigned long v = 0;
for(n = 0; n < N; n++)
v += pokus();
printf("%fn", (float)v / N);
return 0;
  • Answer This Question:Drat on a tesseract...? 

  • insert image

    image url:

    such as:**/**.jpg

    insert video

    vedio url: