uniolympiads Ελληνικά

IMC 2004, Day 2, Problem 6

For n≥0n \ge 0 define matrices AnA_n and BnB_n as follows: A0=B0=(1)A_0 = B_0 = (1) and for every n>0n > 0

An=(An−1An−1An−1Bn−1) and Bn=(An−1An−1An−10).A_n = \begin{pmatrix} A_{n-1} & A_{n-1} \\ A_{n-1} & B_{n-1} \end{pmatrix} \text{ and } B_n = \begin{pmatrix} A_{n-1} & A_{n-1} \\ A_{n-1} & 0 \end{pmatrix}.

Denote the sum of all elements of a matrix MM by S(M)S(M). Prove that S(Ank−1)=S(Akn−1)S(A_n^{k-1}) = S(A_k^{n-1}) for every n,k≥1n, k \ge 1.

Original from the official PDF6. 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]

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Solution. The quantity S(Ank−1)S(A_n^{k-1}) has a special combinatorical meaning. Consider an n×kn \times k table filled with 0's and 1's such that no 2×22 \times 2 contains only 1's. Denote the number of such fillings by FnkF_{nk}. The filling of each row of the table corresponds to some integer ranging from 0 to 2n−12^n - 1 written in base 2. FnkF_{nk} equals to the number of k-tuples of integers such that every two consecutive integers correspond to the filling of n×2n \times 2 table without 2×22 \times 2 squares filled with 1's.

Consider binary expansions of integers ii and jj inin−1…i1‾\overline{i_n i_{n-1} \ldots i_1} and jnjn−1…j1‾\overline{j_n j_{n-1} \ldots j_1}. There are two cases:

  1. If injn=0i_n j_n = 0 then ii and jj can be consecutive iff in−1…i1‾\overline{i_{n-1} \ldots i_1} and jn−1…j1‾\overline{j_{n-1} \ldots j_1} can be consequtive.

  2. If in=jn=1i_n = j_n = 1 then ii and jj can be consecutive iff in−1jn−1=0i_{n-1} j_{n-1} = 0 and in−2…i1‾\overline{i_{n-2} \ldots i_1} and jn−2…j1‾\overline{j_{n-2} \ldots j_1} can be consecutive.

Hence ii and jj can be consecutive iff (i+1,j+1)(i+1, j+1)-th entry of AnA_n is 1. Denoting this entry by ai,ja_{i,j}, the sum S(Ank−1)=∑i1=02n−1⋯∑ik=02n−1ai1i2ai2i3⋯aik−1ikS(A_n^{k-1}) = \sum_{i_1=0}^{2^n-1} \cdots \sum_{i_k=0}^{2^n-1} a_{i_1i_2} a_{i_2i_3} \cdots a_{i_{k-1}i_k} counts the possible fillings. Therefore Fnk=S(Ank−1)F_{nk} = S(A_n^{k-1}).

The the obvious statement Fnk=FknF_{nk} = F_{kn} 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?