Using your Head is Permitted

August 2014 solution

The answer is that |d-u| is unbounded for every irrational x.

To see this, let us first note that the only x values that need to be considered are those in 0<x<1, because by adding or subtracting whole integers to x one doesn't change which elements get rounded up and which get rounded down.

Next, we only really need to analyse x values in 0<x<1/2, because by switching x for 1-x, every element that was previously rounded up will now be rounded down and vice versa.

In our analysis we will now use the function "modulo" extensively, so, for clarity, let us define it. For two positive real numbers, a and b, the value c=a mod b is the unique real number c in the range 0≤c<b such that if you subtract it from a the result is a multiple of b, in the sense that k=(a-c)/b is an integer. This integer, k, is referred to as a div b.

We note that we can equally consider all elements in our sequence modulo 1, for this does not change their rounding properties.

Let y be 1/2 mod x, and let us divide the range (0,1), where all elements lie, to the following sub-ranges:

D=(0,1/2-y]
M=(1/2-y,1/2+y)
U=[1/2+y,1)

Let us define k₀ to be 1/2 div x. By construction, this is a positive integer.

Consider now the elements of the sequence modulo 1. The sequence begins with exactly k₀ elements in D. These are all rounded down. Then, there may or may not be an element in M. After that, there are exactly k₀ elements in U, which are all rounded up. Then the cycle begins again. The only difference from cycle to cycle is whether or not there is an element inside M, and whether that element is rounded up or down. The M element is at most unique at each cycle. (However, as n approaches infinity, so does the total number of elements that fall into the M region.)

Let us divide the original sequence into two sub-sequences. The subsequence H₀ will be composed of all elements in D and U, whereas the T₀ subsequence will be composed of all elements in M.

For an x value in (0,1/2), in the subsequence H₀, the value of d-u ranges from 0 to k₀, going through the entire range before any new element is added to the T₀ sequence. For an x value in (1/2,1), the values range from 0 to -k₀, but, again, this entire range is covered before any new element is added to the T₀ subsequence.

Let the amplitude of a sequence be the difference between its maximal and its minimal value. Given that H₀ goes through its entire cycle before any element is added to T₀, the amplitude of the total sequence is the amplitude of H₀ (which we know to be k₀) plus the amplitude of T₀. Let us now, therefore, calculate this latter amplitude.

Let us subdivide the range (0,1) as follows:

D₁=(0,x]
D₂=(x,2x]
...
D_k₀=(1/2-y-x,1/2-y]
M=(1/2-y,1/2+y)
U_k₀=[1/2+y,1/2+y+x)
...
U₀=[1-x,1)

How far into each segment do elements of the (full) sequence fall? The first element falls x into D₁. All subsequent D's have the same offset, and if the next element falls on M, it has the same offset there as well. However, if x is larger than 2y, the sequence skips over M and lands on one of the Us, at an offset of x-2y into it. The sequence then proceeds through potentially more U segments and more D segments until reaching M again, either hitting it or skipping over it. Throughout this, the offset remains at x-2y. If this value is smaller than 2y, the sequence hits M. If not, it will skip over M, land on U, subtract a further 2y from its offset and repeat until, after some finite number of subtractions, a number smaller than 2y is reached. This number, by definition, is x mod 2y. This is the offset into M on which the sequence will ultimately land on the segment M.

Following the same logic, the next hit on M will be at an offset of 2x mod 2y, then at 3x mod 2y, etc.. In fact, if we were to re-scale M into (0,1), the sequence will be x₁, 2x₁,... (mod 1), where x₁=x/(2y) mod 1. Notably, x₁ is also an irrational.

This means that the d-u subsequence within M behaves exactly as the d-u full sequence for x₁. In particular, the two have the same amplitudes.

We can now, therefore, repeat the analysis we made with x on x₁, dividing its sequence to H₁ and T₁ subsequences. The amplitude of this sequence will be k₁=1/2 div min(x₁,1-x₁) plus whatever is the amplitude for the subsequence T₁, which, in turn, can be considered as the amplitude of the d-u values for a linear sequence based on a new irrational value, x₂, etc.. In total, the amplitude of the original sequence is bounded from below by an infinite sum of k_is, each of which is a positive integer, and so is, itself, infinite, from which we can conclude that |d-u| is unbounded.

Q.E.D.

As can be seen, the sequence of x_is relate to each other by being residues in a continuous fraction expansion of x (or, strictly speaking, of 2x). Analysing the sequence by means of continuous fractions (which Jan Fricke did) allows us to describe the d-u sequence very well, showing how quickly it diverges and how many times it hits zero along the way. These and similar follow-up questions are left for the reader.

To the best of Jan's knowledge, the problem originated from a question that was asked on the newsgroup de.sci.mathematik some years ago.

Back to riddle

Back to main page