0
$\begingroup$

A couple of years ago, I constructively solved (inside the $AABB$ $[0,3]$ X $[0,3]$ X ... X $[0,3]$) the $k$-dimensional generalization of the infamous Nine-Dot Problem by S. Loyd (see Cyclopedia of puzzles, p. 301 (1914)), which asks to find the minimum link covering trail (i.e., a polygonal chain of minimum size) that visits all the $3^k$ points of the set $G_{3,k}:=${$0,1, 2$} X {$0,1, 2$}} X ... X {$0,1, 2$} in $R^k$.

Unfortunately, I was not able to achieve the same result with the following couple of $3D$ and $4D$ foundamental grids: $G_{4,3}:=${$0,1, 2, 3$} X {$0,1, 2, 3$}} X {$0,1, 2, 3$} and $G_{2,4}:=${$0,1$} X {$0,1$} X {$0,1$} X {$0,1$}.

In 2013, it has been proved by Keszegh that the minimum link covering trail for $G_{n,2}$ has size $2*(n-1)$ for any $n>2$ and it is also known that the minimum link covering trail for $G_{2,3}$ has size $6$ (i.e., we can join the $8$ vertices of any cube with a polygonal chain of size $6$, even under the additional constraint of using only line segments of the same length).

It follows that the solution for $G_{2,4}$ have to be at most equal to $13$. On the other hand, years ago, I proved that the minimum link covering trail for $G_{4,3}$ has size between $21$ and $23$.

Is it possible to improve any of the provided bounds for these tricky thinking outside the box brain teasers?

$\endgroup$
4

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.