## Sunday, October 5, 2014

### Closed Under Means

Here's a nice little problem from the 13th All Soviet Union Mathematics Olympiad.
Given a set of real numbers $$S$$ containing 0 and 1 that's closed under finite means, show that it contains all rational numbers in the interval $$\left[0,1\right]$$.
This isn't a difficult problem, but there's a particularly nice solution.

First observe that if $$x\in S$$ then both $$\frac{x}{4}$$ and $$\frac{3x}{4}$$ are in $$S$$; average $$\{0,x\}$$ to get $$\frac{x}{2}$$, average $$\{0, \frac{x}{2}\}$$ to get $$\frac{x}{4}$$, average $$\{\frac{x}{2}, x\}$$ to get $$\frac{3x}{4}$$.

We could show any rational number $$\frac{m}{n}$$ with $$1\leq m < n$$ is in $$S$$ if we had $$n$$ distinct elements from $$S$$ that summed to $$m$$. Let's exhibit one.

Start with an array with $$m$$ 1s on the left, $$n-m$$ 0s on the right. Repeatedly replace adjacent $$x,y$$ values with $$\frac{3(x+y)}{4}, \frac{(x+y)}{4}$$, where either $$x=1,y\neq1$$ or $$x\neq 0, y=0$$, until there is one 0 and one 1 left. We can do this in exactly $$n-2$$ steps, each resulting number is guaranteed to be in $$S$$ by the above note, and each number is guaranteed to be distinct by construction!

Examples:

$$\frac{1}{3}: \left[1,0,0\right] \to \left[\frac{3}{4},\frac{1}{4},0\right]$$

$$\frac{2}{5}: \left[1,1,0,0,0\right] \to \left[1,\frac{3}{4},\frac{1}{4},0,0\right] \to \left[1,\frac{3}{4},\frac{3}{16},\frac{1}{16},0\right]$$