Using your Head is Permitted

October 2009 riddle

This month's riddle comes from Yuval Filmus and Avinoam Braverman.

Suppose you want to find the factors of a number, n. An easy way to do this is to go over all x on the interval [2,floor(sqrt(n))] and to calculate for each x the value of the function y(x)=n mod x. Specifically, we are interested in finding the x values in which y(x) equals zero.

Because y(x) receives only non-negative values, every zero should be a local minimum. For simplicity, let us consider only those points that are strict local minima, meaning those points satisfying that y(x) is smaller than both y(x-1) and y(x+1). We do this by taking all (x,y) pairs and removing from them all pairs that do not represent local minima of the function.

We are left with a set of (x,y) tuples where x and y are both bounded on the interval [0,sqrt(n)]. Let us scale this down to [0,1] by dividing both axes by sqrt(n). This month's question is about the set of tuples that results from this operation.

The question is: what does it converge to, when n tends to infinity?

To be mathematically precise, we are asking here about convergence in the upper Vietoris topology. The meaning of this is as follows: The limit, S, of an infinite sequence of sets, {S0, S1,...}, under the upper Vietoris topology, is the set of all a for which there exists an infinite sequence of integers, {i0, i1,...}, diverging to infinity, and an infinite sequence {a0, a1,...} converging to a, with an in Sin for every natural n.

For brevity, we refer to "convergence" and to "limit" without specifying the topological space each time.

NB - We will only accept this month solutions in which the description of the limit set is exact.

As a bonus question, you are welcomed to consider also what is the limit, if we repeat the filter operation for a second time: instead of looking at local minima, we look in the bonus question only at local minima of local minima.

List of solvers:

Itsik Horovitz (31 October 20:00)

Elegant and original solutions can be submitted to the puzzlemaster at Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.


To solution

Back to main page