Imagine that we can "take a step" between two integers when their difference can be written as $2^k$ where $k$ is some nonnegative integer, not necessarily positive. Define $D$ as the minimum number of steps required to travel between two integers. $D(0,9)$ is 2- we can go from 0 to 8, then to 9. Let's define sets $L$ and $Y$ where $L$ is an infinite set of specific steps between integers(let's call these specific steps "links") and $Y$ is an infinite set of specific integers smaller than $\mathbb{Z}$. Each member of $Y$ must have exactly 2 links that are members of $L$ going from and to it, and we must be able to travel between any two integers in $Y$ using links from $L$ as they are positioned. However, the minimum distance between members of $Y$ using links from $L$ must always equal $D$. For instance, say 0 and 8 are in $Y$. Then as $D(0,8)$ is 1, the link between 0 and 8 must be in $L$. Can we describe $Y$ and $L$ such that the conditions are met, or prove that the conditions cannot be met?
set of integers
-
0@MarcvanLeeuwen Could you please further explain your thought process that lead to your solution? And what do you mean by shortcut free? – 2012-04-16
1 Answers
Put $a_i=\frac{4^{i}-1}3=\sum_{j=0}^{i-1}2^{2j}$ and $b_i=-2a_i=-\sum_{j=0}^{i-1}2^{2j+1}$ for $i\in\mathbb N$. Then $Y=A\cup B$ where $ A=\{a_i\mid i\in\mathbb N\}=\{0,1,5,21,\ldots\} \text{ and } B=\{b_i\mid i\in\mathbb N\}=\{0,-2,-10,-42,\ldots\} $ does the job, almost.
Every $a_i$ is linked to $a_{i+1}$, same for $b_i$ and $b_{i+1}$, and the two sequences are joined at $a_0=b_0=0$. Looking at the binary representation of differences it seems that one cannot do better than correct all the differing bits one by one, but this is not true: for instance $-2$ and $5$ are at distance $7$ and therefore linked in $\mathbb Z$ by $-2\leftrightarrow-3\leftrightarrow5$ in only two steps.
I think this can be repaired by replacing the base $2$ in the expressions for $a_i,b_i$ by $4$ or a higher power of $2$. With $a_i=\sum_{j=0}^{i-1}4^{2j}$ and $b_i=-4a_i$ one obtains $ Y=\{\ldots,-1052,-68,-4,0,1,17,263,\ldots\}, $ which does appear to be shortcut-free.
Added. The basic idea behind this solution is that we are looking for a linear subgraph (infinite in two directions) of the graph on $\mathbf Z$ defined by the relation of differing by an integer power of two, such that the induced distance whithin the subgraph is never longer than the distance in the original graph between the two points. This requires that if we label the different edges of the subgraph by the exponent of $2$ used for the edge, then these labels should always be different: of the same power occurs twice, then one could combine them to the next power of two, and for any interval in the subgraph that contains both edges in question one could find a shorter path between its end points in the original graph, essentially be writing the difference between the end points as sum/difference of a smaller number of powers of two than are used along the path in the subgraph.
The condition of using different powers of $2$ is not sufficient though, because of "shortcuts" possible by writing the difference of the end points not as a sum of powers of two given by the bits '$1$' in the binary representation of that difference. For instance a difference of $7$ can be realised not only as $1+2+4$ (in some order), but also as a difference $8-1$, which uses fewer powers of two. To make the solution work, we need an infinite set of bit positions with the property that whenever one makes a number by putting $n$ bits $1$ in a subset of those postitions, and bits $0$ elsewhere, then the resulting number cannot be written by adding or subtracting fewer than $n$ powers of two. I suggested (though did not prove) that the set of even positions would have this property, or else in any case any sufficiently sparse infinite set of positions. If the suggestion is true, the set $ Y=\{\sum_{j=0}^{i-1}4^{2j}\mid i\in\mathbf N\} \cup\{\sum_{j=0}^{i-1}(-4)^{2j+1}\mid i\in\mathbf N\} $ would be a solution.
-
0Could you describe $Y$ further? – 2012-04-20