An Interesting Problem

I recently came across a problem that I still have been working on. It goes like this:

An ocean has infinitely many islands. Every island is labeled by one of the integers {...,-3,-2,-1,0,1,2,3,...,} with no two islands having the same label and every integer being the label of some island. Two islands are connected by a bridge if their labels differ by a power of two. For instance, there is a bridge connecting island 7 and island -25.

We define the distance between two islands k₁ and k₂ to be the minimum number of bridges needed to get from k₁ to k₂. For instance, the distance between the islands 0 and 7 is 2. (You can move from island 0 to island 8, then to island 7; this is the minimum, since you can't go from 0 to 7 using just one bridge.)

1. Show that for any integer r ≥ 1, you can find two islands in the ocean at distance r from each other.
2. An infinite path in our ocean consists of an infinite set of islands I and an infinite set of bridges B, such that:
   • every island in I is connected to exactly two bridges in B,
   • for any two islands in I, you can get from one to the other using only bridges in B.
   Here is one example of an infinite path: let I be the set of all odd-numbered islands and let B be the set of bridges between islands in I whose labels differ by 2. It is easy to see that I and B satisfy both conditions for an infinite path:
   • Each island k in I is connected to exactly two bridges in B – namely, the bridges leading to islands k-2 and k+2;
   • To get from any odd-numbered island to any other using bridges in B, you start at the smaller number and keep adding 2.
   As a warm-up, can you create an infinite path with the same I as in the example above, but with a different B?
3. Is it possible to construct an infinite path in our ocean such that, for any two islands k₁, k₂ in I, the minimum number of bridges in B needed to get from k₁ to k₂ is exactly the distance between k₁ and k₂? For instance, the infinite path in our example does not have this property: it takes two bridges in B to go from island 1 to island 5 (you have to go via island 3), even though the distance between these two islands is 1 (there is a single bridge not in B that connects them to each other). If your answer is yes, give an example of sets I and B that work. If your answer is no, prove that it can't be done. 

Part (a) took me a while, but I eventually figured it out:
Let s_n = (2^(n-1))s_(n-1) + 1;  n = {0,1,2...} be a sequence of numbers. What I need to prove is that s_n has distance n from 0. I am going to do this by induction. Assume s_(n-1) has distance n-1. Then say
(2^(n-1))s_(n-1) has distance < n-1. (2^(n-1))s_(n-1) can be written as 2^(a_1) +- 2^(a_2) +- ... +- 2^(a_k), where k < n-1. Dividing by 2^(n-1) on both sides, we get s_(n-1) = 2^(a_1 + 1-n) +- 2^(a_2 + 1-n) +-...+-2^(a_k + 1-n). This shows that s_(n-1) has distance < n-1, a contradiction. Therefore
(2^(n-1))s^(n-1) must have distance >= n-1. It is easy to show that it does in fact have distance n-1. Therefore (2^(n-1))s^(n-1) + 1 must have distance n.

The next part was fairly simple-just switch the bridge from -3 to -1 to from -3 to 1, the bridge from 1 to 3 to from -1 to 3.

The third part is more complicated and I still have not cracked it yet. My gut feeling is that it would be too hard to construct such as set, and therefore there must be some way to prove that it is not correct.

Some Important Physical Formulations

First, an explanation. It might have been noticed that the general format of my last blog looked completely different than before, with larger fonts and actual mathematical expressions. That is because I used a mathematical typesetting program called Latex. Latex makes it very convenient to typeset mathematical expressions, and my previous post was heavy in that area. For this blog, I am back to regular text, but I may continue experimenting with Latex in the future.

This post will be on the concepts of the Divergence, Gradient, and Curl of a multivariable function. A multivariable function is a function that depends on more than just one variable x; it can depend on two variables, three variables, or even an infinite number of variables. If a function f is dependent on three variables, it can be denoted as f(x,y,z). A vector function is a function that inputs some value and outputs a vector. For example, a vector function F(x,y,z) can take a three dimensional point and output a three dimensional vector (a,b,c). Vector fields are used to represent the electromagnetic force at any given point, the velocity of a fluid at a given point, the acceleration of a particle at a given point, and many other situations.

The definition of the divergence of a three dimensional vector field F(x,y,z) is the sum of the partial derivative with respect to x of the x component of F plus the partial derivative with respect to y of the y component of F plus the partial derivative with respect to z of the z component of F. This may sound like a random definition, but its interpretation is vastly important. Roughly speaking, the divergence of a vector field inside a closed surface is a measure of the amount of "flux", or movement out of, the vector field. If the vector field was the velocity of a fluid, and the surface a sphere, then the divergence of the velocity of the fluid around the sphere would simply be the net amount of water flowing out of the sphere. Divergence can be applied to electromagnetics to derive Gauss's Law, which provides a very simple method of determining the amount of electric charge "flowing" through a give volume.

The gradient of a vector field F(x,y,z) is defined as the vector whose x component is the partial derivative with respect to x of the x component of F, whose y component is the partial derivative with respect to y of the y component of F, and whose z component is the partial derivative with respect to z of the z component of F.  The gradient can be thought of as a type of derivative for the function F. In fact, the direction of the gradient turns out to be the direction of maximum increase of F. A vector field is said to be "conservative" if it is path-independent. A vector field is said to be "path-independent" if a certain type of integral of the vector field only depends on the two endpoints, not the path taken in between the two points. Vector fields who are the gradient of some other vector field are always conservative. An example of a conservative vector fields in real life is the Earth's gravitational field.

The last term, and by far the most complicated to define, is the curl of a vector field F(x,y,z). Because I am not using Latex and therefore do not have a convenient way of writing mathematical expressions, I will not try to define the curl of a vector field. However, descriptions will be given as to what the curl exactly is. The curl can be thought (loosely) of as the "circulation" of a vector field around a perpendicular point-i.e. "how much" a vector field "rotates" about some reference. The curl of a vector field is also a central part of a theorem that connects integrals on a one dimensional curve to integrals confined on a two dimensional surface. Lastly, the if a vector field has a curl of (0,0,0), then the vector field is conservative.

The three terms described in this post are central to the understanding of nature and are widely used in physics. Without them, the world would be looked at through much fuzzier lens.