Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
"Set of specific integers smaller than $\mathbb{Z}$" could be parsed as a set whose elements are integers that are, somehow, "smaller than $\mathbb{Z}$". Do you mean, "$Y$ is an proper infinite subset of $\mathbb{Z}$"? –  Arturo Magidin Apr 15 '12 at 5:29
1  
I think the question can be more clearly formulated as follows: given the graph on $\mathbb Z$ where there is an edge between points if their difference is a power of $2$ (including $1$), does there exist an infinite subset $Y$ of $\mathbb Z$ such that the induced subgraph is linear without endpoints (connected and every vertex has degree $2$)and the distance in the subgraph between $x,y\in Y$ is no longer than (hence equal to) their distance $D(x,y)$ in the original graph. –  Marc van Leeuwen Apr 15 '12 at 6:31
1  
I'm a little confused by a couple of things in the first sentence of the question. For $k$ real, $2^k$ is positive, so why write $|2^k|$? Also, the difference between two integers is an integer, so, if that difference is $2^k$, then $k$ can't be negative, so what is the purpose of "where $k$ is some integer, not necessarily positive"? –  Gerry Myerson Apr 15 '12 at 6:38
    
@GerryMyerson: The question states that $k$ is integer, and it could have added non-negative. The absolute value bars are indeed confusing, they should be around the difference (i.e., taking the positive difference), not around the power of $2$. –  Marc van Leeuwen Apr 15 '12 at 7:05
    
@MarcvanLeeuwen Could you please further explain your thought process that lead to your solution? And what do you mean by shortcut free? –  Ali Apr 16 '12 at 23:15

1 Answer 1

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.

share|improve this answer
    
Could you please further explain how your thought process lead to this? –  Ali Apr 16 '12 at 23:14
    
Could you describe $Y$ further? –  Ali Apr 20 '12 at 12:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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