IMC 2004, Day 2, Problem 6
For define matrices and as follows: and for every
Denote the sum of all elements of a matrix by . Prove that for every .
Original from the official PDF
![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−1 A n−1 A n−1 A n = and B n = . A n−1 B n−1 A n−1 0 Denote the sum of all elements of a matrix M by S(M ). Prove that S(A n k−1 ) = S(A k n−1 ) for every n, k ≥ 1. [20 points]](/archive/imc/imc-2004-d2-p6.png)
This transcription was compared symbol by symbol with the original, but not yet by a person.
Work for at least 45 minutes before opening the solution.
Official solution
Solution. The quantity has a special combinatorical meaning. Consider an table filled with 0's and 1's such that no contains only 1's. Denote the number of such fillings by . The filling of each row of the table corresponds to some integer ranging from 0 to written in base 2. equals to the number of k-tuples of integers such that every two consecutive integers correspond to the filling of table without squares filled with 1's.
Consider binary expansions of integers and and . There are two cases:
-
If then and can be consecutive iff and can be consequtive.
-
If then and can be consecutive iff and and can be consecutive.
Hence and can be consecutive iff -th entry of is 1. Denoting this entry by , the sum counts the possible fillings. Therefore .
The the obvious statement completes the proof.
Transcribed from the official solutions, page 3. This transcription has not been checked a second time; if in doubt, look at the original.
Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.
How did it go?
Moves you mark come back sooner in triage.