Can you solve this problem using a finite number of queries?

The question is stated informally, using the terms "queries" and "access".

Here is how I formally interpret it:

Take any $s$ and $t$ in $(0,1)$. Let $G_{s,t}$ be the set of all continuous strictly increasing functions $g\colon[0,1]\to[0,1]$ such that the set $$E:=E_{s,t}(g):=\{x\in[0,1-s]\colon g(x+s)-g(x)<t\}$$ is nonempty. Do there exist sequences $(x_j)_{j=1}^\infty$ and $(y_j)_{j=1}^\infty$ in $[0,1]$ such that for any $g\in G_{s,t}$ there is a natural $n$ such that the following implication holds: If a function $h\colon[0,1]\to[0,1]$ is continuous and strictly increasing and for all $j\in[n]:=\{1,\dots,n\}$ we have $h(x_j)=g(x_j)$ and $h^{-1}(y_j)=g^{-1}(y_j)$, then ($h\in G_{s,t}$ and) for some $k\in[n]$ we have $x_k\in E_{s,t}(h)$?

Then the answer is yes.

Indeed, informally, let the $j$th query give us the values $g(q_j)$ and $g(q_j+s)$, where $(q_j)_{j=1}^\infty$ is an enumeration of the set of all rational numbers in the interval $[0,1-s]$. Take any $g\in G_{s,t}$, so that $E_{s,t}(g)\ne\emptyset$. Since $g$ is continuous, the set $E_{s,t}(g)\subseteq[0,1-s]$ is open in $[0,1-s]$, and hence $q_n\in E_{s,t}(g)$ for some natural $n$. So, we will find the point $q_n\in E_{s,t}(g)$ on our $n$th query.

Formally, let $(y_j)_{j=1}^\infty$ be any sequence in $[0,1]$ (it will be of no use to us). For each natural $j$, let $x_{2j-1}:=q_j$ and $x_{2j}:=q_j+s$.

Take any $g\in G_{s,t}$. Then, as noted above, $q_n\in E_{s,t}(g)$ for some natural $n$. Now, if a function $h\colon[0,1]\to[0,1]$ is continuous and strictly increasing and for all $j\in[2n]$ we have $h(x_j)=g(x_j)$ and $h^{-1}(y_j)=g^{-1}(y_j)$, then for $k=2n-1(\in[2n])$ we have $x_k=x_{2n-1}=q_n\in[0,1-s]$ and $h(x_k+s)-h(x_k)=h(x_{2n})-h(x_{2n-1})=g(x_{2n})-g(x_{2n-1})=g(q_n+s)-g(q_n)<t$ (because $q_n\in E_{s,t}(g)$), so that $x_k\in E_{s,t}(h)$ (and $h\in G_{s,t}$). Thus, the implication in question holds.

The monotonicity condition on $g$ or the knowledge of values of $g^{-1}$ was not actually needed in this proof.

Tags:

Approximation Algorithms

Real Analysis

Related

How to plot this fractal Good forcings with bad squares An intelligent ant living on a torus or sphere – Does it have a universal way to find out? Factorization of the characteristic polynomial of the adjacency matrix of a graph What are some foundational authors/papers in dynamical systems? Erroneous Wolfram result for $\sum_{k=1}^\infty (k^3 + a^3)^{-1}$, looking for correct formula Decomposing a (co)limit by decomposing the indexing diagram Complex projective manifolds are homeomorphic if homotopy equivalent Work on triply periodic minimal surfaces What can be said about a projective morphisms that admit decomposition theorem like smooth morphisms? Are there any identities for alternating binomial sums of the form $\sum_{k=0}^{n} (-1)^{k}k^{p}{n \choose k} $? In a locally presentable category, is every object (a retract of) the colimit of a chain of smaller objects?

Recent Posts