Posts

Showing posts from October, 2014

A Strange Recursive Relation, Automatic

Hofstadter mentions the following recursive relation in his great book "Gödel, Escher, Bach": \begin{align} g(0) &= 0;\\ g(n) &= n-g(g(n-1)). \end{align} I claim that $$g(n) = \left\lfloor \phi\cdot (n+1) \right\rfloor$$, where $$\phi = \frac{-1+\sqrt{5}}{2}$$, and I'll show this using a technique that makes proving many identities of this type nearly automatic.

Let $$\phi\cdot n = \left\lfloor \phi\cdot n \right\rfloor + e$$, where $$0 < e < 1$$ as $$\phi$$ is irrational, nor can $$e = 1-\phi$$, and note that $$\phi$$ satisfies $${\phi}^2 + \phi - 1 = 0$$. Some algebra gives \[
\begin{align}
n-\left\lfloor \left( \left\lfloor \phi\cdot n \right\rfloor + 1 \right) \cdot \phi \right\rfloor
&= n-\left\lfloor \left( n\cdot \phi - e + 1 \right) \cdot \phi \right\rfloor \\
&= n-\left\lfloor n\cdot {\phi}^2 - e\cdot \phi + \phi \right\rfloor \\
&= n-\left\lfloor n\cdot \left(1-\phi\right) - e\cdot \phi + \phi \right\rfloor \\
&= n-n-…

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 o…