Problem of the Week 1238

Change of Base

Solution

Note that f is not well-defined at the dyadic rationals; 1/2 is both 0.100... and 0.0111... The first gives 1/10, while the second gives 1/90. But the set of such points is countable and their f-values do not affect the integral. The function is continuous at all other points and so the Riemann integral exists. Or one can use the classic theorem that any monotonic function is Riemann integrable, and f is monotonic regardless of the choice one makes at the dyadic rationals.

I received more solutions than for any problem in the last 20 years! And the solutions were varied, which was nice. A couple of incorrect solutions were received. Correct proofs were sent by Joseph DeVincentis, Ross Millikan, Ken Schilling, David Broadhurst, David Stigant, John Snyder, John Guilford, Laszlo Liptak, Patrick LoPresti, John Duncan, Stephen Morris, Ken Leone, Barry Cox, Patrick Fitzsimmons, Dan Dima, Dave Ehren, Alberto Monteiro, and Japheth Wood.

Solution 1. By symmetry, the integrals of f(x) and f(1 − x) are equal. Ignoring the dyadic rationals, f(x) + f(1 − x) equals 0.11111..., or 1/9. So twice the requested integral is 1/9 and the answer is 1/18.

Solution 2. Work in base 10: We seek the expected value of a random variable with an nth digit to the right of the decimal point that is 0 or 1 with equal probability. The nth digit contributes 1/2 10^-n to the expected value for a total expected value of

Ross Millikan expressed Solution 2 succinctly as: "I make it 1/18. Half the length of (0, 1) has a 1 in the tenths place, giving an integral of 1/20. Half the length has a 1 in the hundredths place, giving an integral of 1/200. Summing the series gives 1/18." Or by John Guilford: "Among the numbers summed for the integration, each binary digit takes the value 0 half the time and 1 half the time. Thus, the expected value and the desired integral is 1/2 (0.1111... (decimal)) or 1/18."

Solution 3 (John Duncan; Stephen Morris). Extend the definition of f to all reals. We have f(2x) = 10 f(x) and so

So

But f(1 + x) = 1 + f(x) for 0 ≤ x ≤ 1, so ...

... and the answer is 1/18.

Solution 4 (David Stigant). The area we want can be divided in half horizontally. The right half (x > 1/2) contains the box (1/2 < x < 1 by 0 < y < 1/10). The remaining area can be divided into four vertical strips, the second and fourth of which contain boxes which are 1/4 × 1/100. The remaining areas can be divided into 8 strips, the even parts containing 1/8 × 1/1000 boxes, etc. At level k, there are 2^{(k − 1)} boxes which are (.5)^k × (.1)^k, so the area is:

The proofs generalize to: If f is defined by transforming a base b number to a base d number where 2 ≤ b ≤ d, then the integral of f is (b − 1)/(2 (d − 1)).

Jim Tilley observes that 3/4 is unusual because f(3/4) is 11/100 by the digit expansion, but if one writes 3 in binary, and the same for 4, and then divides, one gets 11/100, the same result. This is not true for, say, 1/3, since f(1/3) is 1/99, and not 1/11.

One then wonders: For which rationals p/q is it true that the f-value is the same with either definition? Answer: When q is a power of 2. The point here is that 3/4 is a bad number to use as an example in the problem statement, and I have changed it to 1/3 in this archival version.

[Back to Problem 1238]

© Copyright 2017 Stan Wagon. Reproduced with permission.