Return to Question

I recently came across this problem from USAMO 2005:

"A calculator is broken so that the only keys that still work are the $\sin$, $\cos$, $\tan$, $\arcsin$, $\arccos$ and $\arctan$ buttons. The display initially shows $0$. Given any positive rational number $q$, show that pressing some finite sequence of buttons will yield $q$. Assume that the calculator does real number calculations with infinite precision. All functions are in terms of radians."

A surprising question whose ingenious solution actually shows how to generate the square root of any rational number.

I'd like to pose the following questions related to this problem:

What is the smallest set of real functions, continuous at all points of $\mathbb{R}$, which can be applied to $0$ to yield a sequence containing all the rational numbers?

It's also interesting perhaps weaken this to allowing finite numbers of discontinuities so you can use the rational functions for example:

What is the smallest set of real functions, continuous except at a finite set of points, which can be applied to $0$ to yield a sequence containing all the rational numbers?

Note that these are slightly different questions to the one above in that we are asking not only to be able to produce any rational from $0$ but to produce all of them at some point after starting at $0$. In the case of the USAMO question you can generate a complete sequence of rationals as well as any given rational but this may not always be true. (See solution for details)

For the second question note that from the theory of continued fractions of rational numbers the functions $f(x)=1/x$, $g(x)=x+1$ will generate any given rational starting from $0$. For example since

$$\frac{355}{113} = 3+\cfrac{1}{7+\cfrac{1}{16}}$$

we have $\frac{355}{113}=g^{[3]}(f(g^{[7]}(f(g^{[16]}(0)))))$.

If we also throw in $h(x)=x-1$ we again have every inverse included hence this set of three functions will generate all rationals.

So we know that the smallest set must contain either $1$, $2$ or $3$ functions.

I recently came across this problem from USAMO 2005:

"A calculator is broken so that the only keys that still work are the $\sin$, $\cos$, $\tan$, $\arcsin$, $\arccos$ and $\arctan$ buttons. The display initially shows $0$. Given any positive rational number $q$, show that pressing some finite sequence of buttons will yield $q$. Assume that the calculator does real number calculations with infinite precision. All functions are in terms of radians."

A surprising question whose ingenious solution actually shows how to generate the square root of any rational number.

I'd like to pose the following questions related to this problem:

What is the smallest set of real functions, continuous at all points of $\mathbb{R}$, which can be applied to $0$ to yield a sequence containing all the rational numbers?

It's also interesting perhaps weaken this to allowing finite numbers of discontinuities so you can use the rational functions for example:

What is the smallest set of real functions, continuous except at a finite set of points, which can be applied to $0$ to yield a sequence containing all the rational numbers?

Note that these are slightly different questions to the one above in that we are asking not only to be able to produce any rational from $0$ but to produce all of them at some point after starting at $0$. In the case of the USAMO question you can generate a complete sequence of rationals as well as any given rational but this may not always be true. (See solution for details)

For the second question note that from the theory of continued fractions of rational numbers the functions $f(x)=1/x$, $g(x)=x+1$ will generate any given rational starting from $0$. For example since

$$\frac{355}{113} = 3+\cfrac{1}{7+\cfrac{1}{16}}$$

we have $\frac{355}{113}=g^{[3]}(f(g^{[7]}(f(g^{[16]}(0)))))$.

If we also throw in $h(x)=x-1$ we again have every inverse included hence this set of three functions will generate all rationals.

So we know that the smallest set must contain either $1$, $2$ or $3$ functions.

In fact as pregunton noted in this related question the functions $f(x)=x+1$ and $g(x)= -1/x$ generate the modular group which acts transitively on $\mathbb{Q}$ and this gives an elegant example with only two functions.

I recently came across this problem from USAMO 2005:

"A calculator is broken so that the only keys that still work are the $\sin$, $\cos$, $\tan$, $\arcsin$, $\arccos$ and $\arctan$ buttons. The display initially shows $0$. Given any positive rational number $q$, show that pressing some finite sequence of buttons will yield $q$. Assume that the calculator does real number calculations with infinite precision. All functions are in terms of radians."

A surprising question whose ingenious solution actually shows how to generate the square root of any rational number.

I'd like to pose the following questions related to this problem:

What is the smallest set of real functions, continuous at all points of $\mathbb{R}$, which can be applied to $0$ to yield a sequence containing all the rational numbers?

It's also interesting perhaps weaken this to allowing finite numbers of discontinuities so you can use the rational functions for example:

What is the smallest set of real functions, continuous except at a finite set of points, which can be applied to $0$ to yield a sequence containing all the rational numbers?

Note that these are slightly different questions to the one above in that we are asking not only to be able to produce any rational from $0$ but to produce all of them at some point after starting at $0$. In the case of the USAMO question you can generate a complete sequence of rationals as well as any given rational but this may not always be true. (See solution for details)

For the second question note that from the theory of continued fractions of rational numbers the functions $f(x)=1/x$, $g(x)=x+1$ will generate any given rational starting from $0$. For example since

$\frac{355}{113} = 3+\cfrac{1}{7+\cfrac{1}{16}}$

we have $\frac{355}{113}=g^{[3]}(f(g^{[7]}(f(g^{[16]}(0)))))$.

If we also throw in $h(x)=x-1$ we again have every inverse included hence this set of three functions will generate all rationals.

So we know that the smallest set must contain either $1$, $2$ or $3$ functions.

I recently came across this problem from USAMO 2005:

"A calculator is broken so that the only keys that still work are the $\sin$, $\cos$, $\tan$, $\arcsin$, $\arccos$ and $\arctan$ buttons. The display initially shows $0$. Given any positive rational number $q$, show that pressing some finite sequence of buttons will yield $q$. Assume that the calculator does real number calculations with infinite precision. All functions are in terms of radians."

A surprising question whose ingenious solution actually shows how to generate the square root of any rational number.

I'd like to pose the following questions related to this problem:

What is the smallest set of real functions, continuous at all points of $\mathbb{R}$, which can be applied to $0$ to yield a sequence containing all the rational numbers?

It's also interesting perhaps weaken this to allowing finite numbers of discontinuities so you can use the rational functions for example:

What is the smallest set of real functions, continuous except at a finite set of points, which can be applied to $0$ to yield a sequence containing all the rational numbers?

Note that these are slightly different questions to the one above in that we are asking not only to be able to produce any rational from $0$ but to produce all of them at some point after starting at $0$. In the case of the USAMO question you can generate a complete sequence of rationals as well as any given rational but this may not always be true. (See solution for details)

For the second question note that from the theory of continued fractions of rational numbers the functions $f(x)=1/x$, $g(x)=x+1$ will generate any given rational starting from $0$. For example since

$$\frac{355}{113} = 3+\cfrac{1}{7+\cfrac{1}{16}}$$

we have $\frac{355}{113}=g^{[3]}(f(g^{[7]}(f(g^{[16]}(0)))))$.

If we also throw in $h(x)=x-1$ we again have every inverse included hence this set of three functions will generate all rationals.

So we know that the smallest set must contain either $1$, $2$ or $3$ functions.

I recently came across this problem from USAMO 2005:

"A calculator is broken so that the only keys that still work are the $\sin$, $\cos$, $\tan$, $\arcsin$, $\arccos$ and $\arctan$ buttons. The display initially shows $0$. Given any positive rational number $q$, show that pressing some finite sequence of buttons will yield $q$. Assume that the calculator does real number calculations with infinite precision. All functions are in terms of radians."

A surprising question whose ingenious solution actually shows how to generate the square root of any rational number.

I'd like to pose the following questions related to this problem:

What is the smallest set of real functions, continuous at all points of $\mathbb{R}$, which can be applied to $0$ to yield a sequence containing all the rational numbers?

It's also interesting perhaps weaken this to allowing finite numbers of discontinuities so you can use the rational functions for example:

What is the smallest set of real functions, continuous except at a finite set of points, which can be applied to $0$ to yield a sequence containing all the rational numbers?

Note that these are slightly different questions to the one above in that we are asking not only to be able to produce any rational from $0$ but to produce all of them at some point after starting at $0$. In the case of the USAMO question you can generate a complete sequence of rationals as well as any given rational but this may not always be true. (See solution for details)

Note that from the theory of continued fractions of rational numbers the functions $f(x)=1/x$, $g(x)=x+1$ will generate any given rational starting from $0$. For example since

$\frac{355}{113} = 3+\cfrac{1}{7+\cfrac{1}{16}}$

we have $\frac{355}{113}=g^{[3]}(f(g^{[7]}(f(g^{[16]}(0)))))$.

If we also throw in $h(x)=x-1$ we again have every inverse included hence this set of three functions will generate all rationals.

So we know that the smallest set must contain either $1$, $2$ or $3$ functions.

I recently came across this problem from USAMO 2005:

"A calculator is broken so that the only keys that still work are the $\sin$, $\cos$, $\tan$, $\arcsin$, $\arccos$ and $\arctan$ buttons. The display initially shows $0$. Given any positive rational number $q$, show that pressing some finite sequence of buttons will yield $q$. Assume that the calculator does real number calculations with infinite precision. All functions are in terms of radians."

A surprising question whose ingenious solution actually shows how to generate the square root of any rational number.

I'd like to pose the following questions related to this problem:

What is the smallest set of real functions, continuous at all points of $\mathbb{R}$, which can be applied to $0$ to yield a sequence containing all the rational numbers?

It's also interesting perhaps weaken this to allowing finite numbers of discontinuities so you can use the rational functions for example:

What is the smallest set of real functions, continuous except at a finite set of points, which can be applied to $0$ to yield a sequence containing all the rational numbers?

Note that these are slightly different questions to the one above in that we are asking not only to be able to produce any rational from $0$ but to produce all of them at some point after starting at $0$. In the case of the USAMO question you can generate a complete sequence of rationals as well as any given rational but this may not always be true. (See solution for details)

For the second question note that from the theory of continued fractions of rational numbers the functions $f(x)=1/x$, $g(x)=x+1$ will generate any given rational starting from $0$. For example since

$\frac{355}{113} = 3+\cfrac{1}{7+\cfrac{1}{16}}$

we have $\frac{355}{113}=g^{[3]}(f(g^{[7]}(f(g^{[16]}(0)))))$.

If we also throw in $h(x)=x-1$ we again have every inverse included hence this set of three functions will generate all rationals.

So we know that the smallest set must contain either $1$, $2$ or $3$ functions.