MathDB
Problems
Contests
National and Regional Contests
Belgium Contests
Flanders Math Olympiad
1991 Flanders Math Olympiad
4
4
Part of
1991 Flanders Math Olympiad
Problems
(1)
Flanders 4 (1991)
Source:
9/7/2003
A word of length
n
n
n
that consists only of the digits
0
0
0
and
1
1
1
, is called a bit-string of length
n
n
n
. (For example,
000
000
000
and
01101
01101
01101
are bit-strings of length 3 and 5.) Consider the sequence
s
(
1
)
,
s
(
2
)
,
.
.
.
s(1), s(2), ...
s
(
1
)
,
s
(
2
)
,
...
of bit-strings of length
n
>
1
n > 1
n
>
1
which is obtained as follows : (1)
s
(
1
)
s(1)
s
(
1
)
is the bit-string
00...01
00...01
00...01
, consisting of
n
−
1
n - 1
n
−
1
zeros and a
1
1
1
; (2)
s
(
k
+
1
)
s(k+1)
s
(
k
+
1
)
is obtained as follows : (a) Remove the digit on the left of
s
(
k
)
s(k)
s
(
k
)
. This gives a bit-string
t
t
t
of length
n
−
1
n - 1
n
−
1
. (b) Examine whether the bit-string
t
1
t1
t
1
(length
n
n
n
, adding a
1
1
1
after
t
t
t
) is already in
{
s
(
1
)
,
s
(
2
)
,
.
.
.
,
s
(
k
)
}
\{s(1), s(2), ..., s(k)\}
{
s
(
1
)
,
s
(
2
)
,
...
,
s
(
k
)}
. If this is the not case, then
s
(
k
+
1
)
=
t
1
s(k+1) = t1
s
(
k
+
1
)
=
t
1
. If this is the case then
s
(
k
+
1
)
=
t
0
s(k+1) = t0
s
(
k
+
1
)
=
t
0
. For example, if
n
=
3
n = 3
n
=
3
we get :
s
(
1
)
=
001
→
s
(
2
)
=
011
→
s
(
3
)
=
111
→
s
(
4
)
=
110
→
s
(
5
)
=
101
s(1) = 001 \rightarrow s(2) = 011 \rightarrow s(3) = 111 \rightarrow s(4) = 110 \rightarrow s(5) = 101
s
(
1
)
=
001
→
s
(
2
)
=
011
→
s
(
3
)
=
111
→
s
(
4
)
=
110
→
s
(
5
)
=
101
→
s
(
6
)
=
010
→
s
(
7
)
=
100
→
s
(
8
)
=
000
→
s
(
9
)
=
001
→
.
.
.
\rightarrow s(6) = 010 \rightarrow s(7) = 100 \rightarrow s(8) = 000 \rightarrow s(9) = 001 \rightarrow ...
→
s
(
6
)
=
010
→
s
(
7
)
=
100
→
s
(
8
)
=
000
→
s
(
9
)
=
001
→
...
Suppose
N
=
2
n
N = 2^n
N
=
2
n
. Prove that the bit-strings
s
(
1
)
,
s
(
2
)
,
.
.
.
,
s
(
N
)
s(1), s(2), ..., s(N)
s
(
1
)
,
s
(
2
)
,
...
,
s
(
N
)
of length
n
n
n
are all different.
algebra solved
algebra