The first of these will be the question of what "y=n mod x" looks like when (in contrast to the question of the riddle) x is kept fixed and n goes from x2 to infinity. The answer is that this is a periodic function of period x that looks like a series of diagonal lines: it starts from 0, rises linearly to x-1 and then drops sharply back to 0 and starts over again.
As before, we will consider this not as a function, but rather as a set of points in R2. For brevity, subsets of R2 will be named here "shapes".
What happens when we scale the y-axis down by a factor of x and the x-axis down by a factor of x2? The period length becomes 1/x instead of x and the amplitude becomes a constant 1 instead of x. We will continue to consider these scaled-down axes throughout what follows. The scaled coordinates will be denoted (x'y'), so as not to be confused with the original x and y.
Consider what happens to this shape if we choose progressively larger values of x. The diagonal lines become increasingly vertical and closer together. They also become more cohesive, in the sense that each is composed of an increasing number of points (x). The limit, when x approaches infinity, is simply the infinite-length rectangle bounded by 0≤y'≤1 and x'≥1.
In what follows, we will consider subsets of the original shape, where in every period of length x we will pick only those points satisfying that their y value is less than some threshold, which will be a function, f(x) of x. In the limit, when x approaches infinity, this clearly translates to the area under the scaled-down version of f (which will be denoted f').
In the original question, we filter out all points that are not local minima. This means that we are interested only in points that satisfy both of the following two conditions:
The function n mod x has a period length of x. The function n mod (x-1) has period length x-1. The filtering criterion therefore has period length x(x-1). Our definition of f allows f to only receive one value in each segment of length x, so f is a function that can take on at most x-1 distinct values. Let us consider what these are. We will examine the first period, with n values ranging from x2 to x(2x-1).
In the first interval, x2≤n<x(x+1), the functions begin, at n=x2 with n mod x=0 and n mod (x-1)=1. This is a difference of 1 in favor of the second function, so n mod x<n mod (x-1) is satisfied. From this point on, this inequality continues to hold (because both functions rise at the same constant rate) until n=x(x+1)-2, after which n mod (x-1) drops to zero. The value of n mod x at this point is x-2, making this the first value of f.
On the second interval, the difference between the two functions is increased by one, for which reason the second value of f is x-3. On the third interval, the same thing is repeated, causing f to drop to x-4, and so on. One can continue the same analysis again and again, with the value of f dropping by one at each iteration until the x-1'th iteration (the last iteration before the function cycles back to its first value), where f reaches 0.
Scaling this down, the function f' becomes a function going down linearly from (1,(x-2)/x) to ((2x-1)/x,0) and then repeating this cyclically. When x is taken to infinity, this converges to the function floor(x')+1-x'.
Exactly the same analysis can be made if we consider only the second criterion: n mod x < n mod (x+1). This leads to the function x'+1-ceil(x').
Superimposing both restrictions we get the function
| f'(x')= | abs(x'-round(x')) | if x' ≠ round(x') |
| 1 | otherwise |
that is the effective f' function that is in effect when both restrictions are used. For a fully rigorous analysis, the cases where x' is an integer should be examined more closely. Such analysis (not done here) shows that because of the difference in period lengths affecting the two restrictions (x(x-1) vs. x(x+1)) this is, indeed, the correct answer.
The area inscribed under this function is the limit of where all local minima of the function n mod x will be. Explicitly, we are referring to the shape S'={(x',y') | x'≥1 ; 0≤y'≤f'(x')}, with f' as above. (Note the use of "≤" and not "<" here. In the limit, equality is reached.)
This, however, is the answer to a different question than the question of the riddle. In this question, we kept x fixed and considered the value of the function n mod x over all n, and later considered the limit of this as x goes to infinity. In the actual riddle, n is kept fixed, and we consider the function as a function of x, later taking n to infinity. (This is true everywhere, except in the logic of how we picked "local minima". In the discussion above, the local minima were picked by the same criterion as in the actual riddle.) Also, even though both questions use a normalization over the results, they don't use the same normalization. Let us begin by fixing this latter problem.
In the actual riddle, the y-axis held values of (n mod x)/sqrt(n). In the analysis above, however, we calculated y'=(n mod x)/x. In the actual riddle, the x-axis held values of x/sqrt(n). In the analysis above, we calculated x'=n/x2. In order to use the same normalization in both questions, let us define a new normalization: x''=1/sqrt(x'); y''=y'*x''.
Note that because the move from (x',y') to (x'',y'') is topology preserving in 0<x''≤1, the transformation of the limit is the same as the limit of the transformations in this region. (This is one of the many wonderful properties of the definition of limit used in this question.) Transforming the definition of S' to the new coordinates we get S''={(x'',y'') | 0<x''≤1 ; 0≤y''≤f''(x'')}, with
| f''(x'')= | x''*abs(1/x''2-round(1/x''2)) | if 1/x''2 ≠ round(1/x''2) |
| x'' | otherwise |
In order to reach the final answer, however, we also need to add point (0,0) to this set. In (0,0) the topological argument breaks down, but we know it must be part of the limit because under our definition of convergence, the limit must always be a closed set.
So, now we have the answer to a question that is very similar to our question, but isn't exactly the same. Both questions consider a mapping g(x,n)=(x/sqrt(n),(n mod x)/sqrt(n)). (Which we previously dubbed (x'',y'').)
Both consider the set S={g(x,n) | x2≤n and n mod x < n mod (x-1), n mod (x+1)}.
The riddle asks for the set of limits of all converging sequences of elements in S wherein n tends to infinity. The question we answered gives the answer to the same question, but for sequences where x tends to infinity.
If the convergence is to some x''=x/sqrt(n)>0, this ratio guarantees that both conditions are always the same: if n tends to infinity then so does x and vice versa. For the case x''=0, we will use the closure argument, as before.
In either case, the answer to this question and to the question of the riddle must be the same. The solution is therefore that the set that the values converge to is defined by S''+{(0,0)}.
Q.E.D.
Interestingly, the outline of this shape is not composed of straight lines.
Note:
The term "local minimum" is ill-defined at the boundary, where
x2≤n<(x+1)2. The analysis
above assumes, for example, that (n,x)=(1000997,1000) is
a local minimum because n mod x < n mod x-1,
n mod x+1, ignoring the fact that x+1 is out of the scope
of the original function, being greater than the square root of n.
If we were to not include such minima, the subset of S'' that is {(1,y'') | 0<y''≤1} should be removed from the solution. This is, perhaps, the more natural way to treat the definition of local minimum, but, in any case, both solutions were accepted as correct answers to the riddle.
Bonus question:
For the bonus question this month we provide a less rigorous analysis. Readers
are welcomed to complete this.
First, let us re-consider the original problem of simple minima. What values of x can result in n mod x being a local minimum?
We want n mod x < n mod (x-1), n mod (x+1).
Note that for any s and t, s mod t={s/t}*t, where {s} is defined by s-floor(s).
Let us now divide n mod x, n mod (x-1) and n mod (x+1) by x. We get:
(n mod x)/x = {n/x}
(n mod (x-1))/x =
{n/x+n/x2+n/(x2(x-1))} - {n/(x-1)}/x
(n mod (x+1))/x =
{n/x-n/x2+n/(x2(x+1))} + {n/(x+1)}/x
Suppose that we want to observe the behavior of the limit at some point x''. x''=x/sqrt(n), so we're really looking for the behavior of local minima in points where the ratio between x and sqrt(n) is approximately the constant value x''. Let us say that its exact value in one of these observations is C. The equations above become
{n/x}
{n/x+1/C2+1/C2(x-1))} - D1
{n/x-1/C2+1/C2(x+1))} + D2
where both D1 and D2 are smaller than 1/(C*sqrt(n)). For large enough values of x and n, most parts of these equations disappear, leaving only
{n/x}
{n/x+1/C2}
{n/x-1/C2}
For the point to be a minimum, {n/x}<{1/C2}<1-{n/x} meaning at the limit that our criterion for local minimality is {n/x}<{1/x''2}<1-{n/x}
This is (up to the approximations made) the same solution as above. Now, however, using the same technique we can approach minima of minima. The difference between two consecutive points is 1/C2, so for us to get twice into the region where {n/x} is small enough we need to go roughly C2 steps. The value round(C2)/C2 therefore gives us the change from one minimum to another, meaning also the value under which {n/x} should drop for us to have a minimum of minima.
The analysis can be repeated, to analyze what happens for minima of minima of minima.