Combinatorics and Graph Theory

1707 Submissions

[1] viXra:1707.0298 [pdf] submitted on 2017-07-23 11:06:26

The nxnxn Dots Problem Optimal Solution

Authors: Marco Ripà
Comments: This is a revised version of the paper published in 2016 on Notes on Number Theory and Discrete Mathematics (ISSN 1310-5132), Volume 22, Number 2 (Pages 36—43).

We provide an optimal strategy to solve the n X n X n points problem inside the box, considering only 90° turns, and at the same time a pattern able to drastically lower down the known upper bound. We use a very simple spiral frame, especially if compared to the previous plane by plane approach, that significantly reduces the number of straight lines connected at their end-points necessary to join all the n^3 dots. In the end, we combine the square spiral frame with the rectangular spiral pattern in the most profitable way, in order to minimize the difference between the upper and the lower bound, proving that it is ≤ 0.5 ∙ n ∙ (n + 3), for any n > 1.
Category: Combinatorics and Graph Theory