60-odd years of moscow mathematical

−1
+ 0 · 2
−2
+ 1 · 2
−3
.
Next, Yaglom said that, more generally, a number system is a method to express numbers with the help
of a certain “basis” u
1
, u
2
, . . . , u
k
, . . . as follows:
N = a
1
· u
1
+ a
2
· u
2
+ . . . + a
k
· u
k
+ . . . ,
(∗)
where the basis need not necessarily be the sequence of powers of a fixed number q and where the k-th
“digit” a
k
does not exceed a
k
/a
k−1
.
For instance, take for a basis the sequence of factorials, i.e., take u
k+1
= (k + 1)u
k
, u
0
= 1. Then any
number N is expressed in the form (∗), where the k-th “digit” a
k
does not exceed k = a
k
/a
k−1
, for example
1000 = 1 · 720 + 2 · 120 + 1 · 24 + 2 · 6 + 2 · 2 + 0 · 1 = 121220
F a
.
The Fibonacci number system is another example. Its basis is of the form
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, . . .
(i.e., u
k+2
= u
k+1
+ u
k
), . . .
With respect to this system, any digit is either 0 or 1, as in the binary one, but here no two 1’s can
stand in a row
1
, e.g.
100 = 1 · 89 + 0 · 55 + 0 · 34 + 0 · 21 + 0 · 13 + 1 · 8 + 0 · 5 + 1 · 3 + 0 · 2 + 0 · 1 = 1000010100
F ib
.
Exercise. 1) How to pass from one number system to another?
2) Write the multiplication table for the above systems.
3)
∗
How to express fractions in the Fibonacci system?
Then Yaglom used the binary system to discuss possible victories and defeats in Nim. Together with
the audience they derived the rule:
A position (a, b, c) is a losing one if all sums of digits of all numbers a, b and c in the binary system
corresponding to the same position are even.
The lecture ended with an analysis in terms of the Fibonacci system of another game, zh`ı sh´ı zi (reads
”tsin shi tsi”) which in Chinese means throwing stones; its Western name is Withoff’s game. Zh`ı sh´ı zi
differs from Nim in that its board has two rows; a player can shift with every move either one chip (to any
place) or one can simultaneously shift both chips by the same distance, cf. Fig. L5.
Figure 5. (Fig.L5)
Yaglom proved that a position (a, b), where a < b, loses if a
F ib
ends with an even number of zeros and
b
F ib
= a0
F ib
.
Here is a sketch of a proof.
Positions ([nτ
2
], [nτ
2
]), where n = 1, 2, . . . and τ ≈ 1.618 . . . is the positive root of the quadratic equation x
2
= x + 1, win.
Proof is based on the following lemma.
Lemma. Let X, Y be positive irrational numbers such that
1
X
+
1
Y
= 1.
(∗)
Then every positive integer can be uniquely represented as either [
k
X
] or [