6. For n ≥ 0 define matrices A n and B n as follows: A 0 = B 0 = (1) and for every n > 0
A n−1 A n−1A n =
and B n =
.
A n−1 B n−1A n−1 0
Denote the sum of all elements of a matrix M by S(M ). Prove that S(A k−1 n ) = S(A n−1 k ) for every n, k ≥ 1.
[20 points]
Solution. The quantity S(A k−1 n ) has a special combinatorical meaning. Consider an n × k table filled with
0’s and 1’s such that no 2 × 2 contains only 1’s. Denote the number of such fillings by F nk . The filling of
each row of the table corresponds to some integer ranging from 0 to 2 n − 1 written in base 2. F nk equals
to the number of k-tuples of integers such that every two consecutive integers correspond to the filling of
n × 2 table without 2 × 2 squares filled with 1’s.
Consider binary expansions of integers i and j i n i n−1 . . . i 1 and j n j n−1 . . . j 1 . There are two cases:
Bạn đang xem 6. - Đề thi Olympic sinh viên thế giới năm 2004
