# Mozgostroje

## The Missing Square

23 Mar 2014

[]

You should be familiar with the following puzzle.

There is very similar puzzle that has some mathematical background in Fibonacci numbers. Recall Fibonacci numbers are given by $F_n = F_{n-1}+F_{n-2}, F_0 = 0, F_1=1$. A more pythonic way to write this is

In [1]:
%pylab inline
def fibo(n): return np.int32(((1 + 5**0.5)/2)**n/5**0.5+0.5)

x=np.arange(20)
print fibo(x)

Populating the interactive namespace from numpy and matplotlib
[   0    1    1    2    3    5    8   13   21   34   55   89  144  233  377
610  987 1597 2584 4181]



Now reading Concrete Mathematics (Graham et al., 1989) I discovered the following thing. Cassini's equality is given by $F_{n+1} F_{n-1}= F_n^2 +(-1)^n$. This can be proven by induction. The equality has a following interpretation. For each square whose size is a Fibonacci number $F_n$ there exists a rectangle with the same area give or take one square. The size of the rectanble is $F_{n+1} \times F_{n-1}$. We can then divide the square and the rectanble in a particular manner to fool the unwary into thinking that the areas of the two objects should be equal.

In [5]:
plt.figure(figsize=(8,12))
s=4;e=9
for N in range(s,e):
f0=fibo(N-2)
f1=fibo(N-1)
f2=fibo(N)
f3=fibo(N+1)
lw=2
plt.subplot(e-s,2,(e-N-1)*2+1)
plt.xlim([0,f2])
plt.ylim([0,f2])
ax=plt.gca()
plt.ylabel('n=%d'%N,fontsize=12)
ax.set_xticks(range(f2))
ax.set_xticklabels([])
ax.set_yticks(range(f2))
ax.set_yticklabels([])
ax.set_aspect(1)
plt.grid(linestyle='-')

plt.plot([0,f1],[f1,f0],'k',lw=lw)
plt.plot([f1,f1],[0,f2],'k',lw=lw)
plt.plot([f1,f2],[0,f2],'k',lw=lw)

plt.subplot(e-s,2,(e-N)*2)
plt.xlim([0,f3])
plt.ylim([0,f1])
ax=plt.gca()
ax.set_xticks(range(f3))
ax.set_xticklabels([])
ax.set_yticks(range(f1))
ax.set_yticklabels([])
ax.set_aspect(1)
plt.grid(linestyle='-')

plt.plot([0,f3],[f1,0],'k',lw=lw)
plt.plot([f1,f1],[0,f0],'k',lw=lw)
plt.plot([f2,f2],[f1,f1-f0],'k',lw=lw)


Let's focus on the $n=8$ row. The rectangle on right was created by reassembling the parts of the square on the left. But wait, the square on the left has area $13 \times 13 = 169$ while the rectanlge on right has area $8 \times 21 = 168$ where is the missing square?

As the $n$ decreases we start to see that the lines of the nominally identical parts do not touch in the rectangle on the right. The parts are not identical.

Rectangle with missing square with which I started this post also has some Fibonacci numbers. Unfortunately, it can't be generalized to create larger or smaller problems.