18
$\begingroup$

You begin on a hypercube of dimension N at the origin i.e. $(0,0,0,0,...,0)$

When at the origin you are able to "see" one and only one step away from you. So from the origin you can see vertices $(1,0,0,0..,0), (0,1,0,...,0),... (0,0,0,...,1)$

What is the function $f(M)$ that gives the total number of vertices seen after $M$ steps? (When $f(M=m)=2^N$ in this function then $m$ will be the minimum number of steps to see all vertices)

Step $0$: $\mathbf{(0,0,0)}, (0,0,1), (0,1,0), (1,0,0)$ 4 vertices

Step $1$: $\mathbf{(0,0,1)}, (0,1,1), (1,0,1)$ +2 vertices

Step $2$: $\mathbf{(1,0,1)}, (1,1,1)$ +1 vertex

Step $3$: $\mathbf{(1,1,1)}, (1,1,0)$ +1 vertex

$\endgroup$
  • 1
    $\begingroup$ We can give a lower bound of $N-1$, because if we start at $(0,0,\ldots,0)$, we need $N-1$ steps to get within one of $(1,1,\ldots,1)$. $\endgroup$ – Larry B. Nov 12 '18 at 19:58
  • 4
    $\begingroup$ We can give a lower bound of $\frac{2^N}{N}-1$, because we need to see $2^N$ vertices and we only see $N$ from each location. $\endgroup$ – Misha Lavrov Nov 12 '18 at 20:17
  • 3
    $\begingroup$ @MishaLavrov: we can improve that to $\frac {2^N-N-1}{N-1}$ because we see at most $N-1$ new ones each step. The $-N-1$ comes because we see $N+1$ at the start without moving. Presumably we see where we are, though the problem does not say so. It is still higher than this because we will see the same vertex more than once. $\endgroup$ – Ross Millikan Nov 12 '18 at 21:22
  • 1
    $\begingroup$ @RossMillikan it doesn't matter whether or not we see the vertex we are at. For all vertices that are not the starting vertex, we must see them before we reach them, and the starting vertex will be seen after the first step. $\endgroup$ – vrugtehagel Nov 20 '18 at 10:49
  • 3
    $\begingroup$ There are a couple of ambiguities that could use some edits to clarify them. First, in the title you ask for "minimum distance required" but in the question body you ask for "the function that gives the total number of vertices seen after $M$ steps." Also, in the example you gave, are there $3$ steps or $4$ steps? That is, is "Step $0$" (merely starting on a vertex, not having moved yet) counted as a step? $\endgroup$ – David K Nov 20 '18 at 20:00
4
+50
$\begingroup$

This is just an upper bound but I'm posting it as an answer since it's too long for a comment.

I will build a sequence $p_n$ of paths that allow you to see all the vertexes of the dimension $n$ hypercube.

Let's consider the dimension $n+2$ hypercube, whose vertexes we can represent by a binary sequence $(b_1,...,b_{n+2})$.

We start our path by going through all the vertexes $(b_1,...,b_n,0,0)$. We know we can do that in exactly $2^n$ steps. At this point we have also "seen" all the vertexes $(b_1,...,b_n,1,0)$ and $(b_1,...,b_n,0,1)$, so all that's left are the vertexes $(b_1,...,b_n,1,1)$, which form a dimension $n$ hypercube. It takes us one extra step to reach that dimension $n$ hypercube, and $p_n$ steps to see all of its vertexes.

A path constructed in this way will see all the vertexes in :

$$ |p_{n+2}| = |p_n| + 2^n+1 $$

We also have trivially $|p_1| = 1$ and $|p_2|$ = 2, so we get an upper bound of:

$$ |p_{2k}| = \sum_{i=1}^{k-1}2^{2i}+k+1 $$

$$ |p_{2k+1}| = \sum_{i=0}^{k-1}2^{2i+1}+k+1 $$

You can get even better results by considering $(b_1,...,b_n,0,0,0)$ etc (we get $|p_{n+3}| = 2^{n+1} + 2$). Someone might be able to generalize it.

$\endgroup$
  • $\begingroup$ To actually reach one of the vertices of the hypercube $(b_1,...,b_n,1,1)$ from the last-visited vertex of $(b_1,...,b_n,0,0)$ requires two steps. On the other hand, you count the question's "Step 0" as a step, so all you need to do is take one step to reach a vertex adjacent to the remaining hypercube, and then $p_n$ steps to "see" all of that hypercube, so the recursion seems correct although I found the reasoning a bit confusing. $\endgroup$ – David K Nov 20 '18 at 19:18
  • $\begingroup$ You're right, that's what I meant but I wasn't sure how to phrase it. $\endgroup$ – Rch Nov 20 '18 at 19:51
  • $\begingroup$ The generalization is this: Choose any $1\le j\le n-1$ and let $p$ be a path along the $j$-dimensional hypercube such that all points are seen. Let $N(p,i)$ be how many new points are seen on the $i$-th step of $p$. If $M_n$ is the minimal steps to see all points on an $n$-dimensional hypercube then $$M_n\le \sum_{i=1}^{|p|}\min(2^{n-j},\; N(p,i)M_{n-j}).$$ (Here $M_n$ counts the starting point as a step.) $\endgroup$ – Will Fisher Nov 28 '18 at 2:32
  • $\begingroup$ This for example gives $M_n\le \sqrt{2^n M_{n-j}M_j}$. $\endgroup$ – Will Fisher Nov 28 '18 at 3:40
4
$\begingroup$

This is not anything like a complete answer, but here is a refinement of the upper bound of $f(M)$ (and therefore the lower bound of $m$) when $N \geq 2.$

(Note: I am counting only steps from one vertex to another; I do not count starting at a vertex as a "step". If you want to count the number of vertices visited, including the starting vertex, add $1$ to my count.)

For simplicity, I'll assume we "see" the vertex we're currently on. As pointed out in comments under the question, that doesn't really matter for $M > 0,$ because the vertices "seen" up to that point will necessarily include the one we just came from, but I wanted my formulas to agree with the example in the question, which seems to imply $f(0) = 4$ when $N = 3.$

In general, then, $f(0) = N + 1.$

After one step, the vertices we have "seen" at either the start or end of this step cover exactly $2n$ of the vertices of the hypercube. Therefore $f(1) = 2N.$

At the end of any other step, we "see" $N$ vertices (not including the one where the step ended), but one of these is the vertex we just came from, which was already "seen" at the start of the previous step (if not earlier).

Moreover, no matter where the previous step came from, the last two steps traverse two sides of one of the two-dimensional square faces of the hypercube, and the fourth vertex of that square is "seen" by both the starting vertex of the next-to-last step and the ending vertex of the last step.

So there are at least two previously-"seen" vertices among the $N$ vertices "seen" at the end of the last step, and that step contributes at most $N - 2$ new vertices. That is, when $M \geq 2$ we have the recursion $$f(M) \leq f(M - 1) + N - 2.$$

From these facts, we can deduce that when $M \geq 2,$ then $$f(M) \leq 2N + (N - 2)(M - 1).$$

It follows that $$M \geq 1 + \frac{f(M) - 2N}{N - 2}.$$ If $m$ is the minimum value of $M$ such that $f(M) = 2^N,$ then $$ m \geq 1 + \frac{2^N - 2N}{N - 2}.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.