Minimum distance required to travel to "see" all points on a hypercube

Question

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

Answer 1

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.

Answer 2

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}.$$