0
$\begingroup$

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?

  • 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}$"?2012-04-15
  • 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.2012-04-15
  • 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"?2012-04-15
  • 0
    @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$.2012-04-15
  • 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 1