This blog post is incomplete and currently being written.

1. Construct a one-to-one mapping (bijection) from $[0,1]$ to $(0,1)$

$f(x)=\begin{cases}\frac12&x=0\\\frac13&x=1\\\frac1{n+3}&x=q_n\text{ (rational in }(0,1),\text{enumerated)}\\x&x\text{ irrational in }[0,1]&\end{cases}$

$f(x)=\begin{cases}\frac{1}{2},&x=0,\\\frac{1}{3},&x=1,\\\frac{1}{n+2},&x=\frac{1}{n}\text{ for }n=2,3,4,\dots,\\x,&\text{otherwise.}\end{cases}$

1. Suppose there is a black-box machine representing a polynomial function

$f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0.$

where $n$ is unknown and both the input $x$ and all coefficients $a_i$ are positive integers. Each time we input a positive integer, the machine returns $f(x)$. Design a method to recover the entire polynomial. What is the minimum number of input-output queries needed?

Solution: The idea is to interpret the polynomial value as a number written in a suitable base.

First, input $x=1$. Then the machine returns $f(1)=a_n+a_{n-1}+\cdots+a_1+a_0$. Define $B=f(1)+1$.

Since all coefficients $a_i$ are positive integers, we have $a_i \le f(1) < B$ for each coefficient $a_i$.

Next, input $x=B=f(1)+1$. The machine returns $f(B)=a_nB^n+a_{n-1}B^{n-1}+\cdots+a_1B+a_0.$

Because every coefficient satisfies $0<a_i<B$, this expression is exactly the base-$B$ representation of $f(B)$, whose digits are

$a_0,a_1,\dots,a_n.$ So we can recover the coefficients by repeatedly dividing $f(B)$ by $B$ and taking remainders: $a_0 = f(B)\bmod B$, then divide by $B$, take the next remainder to get $a_1$, and so on.

Thus two queries are enough.