How many numbers are there for a $16*16$ matrix

Question

Consider all matrixes with $1,0$ if all the numbers are $1$ we define $S=1$ and if all the numbers are $0$ then $S=0$ if non of them happened then we divide it into $4$,$2^{n-1}*2^{n-1}$ matrixes and find the $S$ of every part let the amounts calculated from top left to down right be $d_1,d_2,d_3,d_4$ then the $S$ of original matrix is $\overline{2d_1d_2d_3d_4}$ How many numbers such $S$ can we have for different $16*16$ matrixes?

It is obvious that every matrix has only $1$ number defined like above according to the answer that I got in the book we have to prove we don't have two matrixes that have same numbers but I can't do that.

edit:We may use induction but I am not sure for small matrixes you can check that you can decode the number.So if we could divide every number such $S$ into four parts in a unique way we are done.But I am not sure if we could do that.

Puzzling SE copy:https://puzzling.stackexchange.com/questions/54584/how-many-numbers-are-there-for-a-1616-matrix

AOPS copy:https://artofproblemsolving.com/community/q1h1502306p8883764

Answer 1

This is a compression algorithm. It is designed for black and white images where you will have large areas that are the same color. You start with a $2^n \times 2^n$ matrix of $1$s and $0$s with $0$ being black and $1$ being white. You ask the question: is the matrix all the same color? If yes, you output $0$ or $1$ to reflect the common color. If no, you output $2$ and divide the matrix into a $2 \times 2$ set of submatrices. Then you apply the same algorithm to the submatrices. I think it is not hard to say each matrix generates a unique number.

There is not a unique decoding from numbers to matrices because there is nothing in the algorithm to give the size of the matrix. The simple way to see this is to take the string $1$, which could represent any $2^n \times 2^n$ matrix of all $1$s. If we were given the size of the matrix there would be no problem. Every string will have a minimum size which is $2$ to the power of the number of $2$s in a chain in the string. This assumes that there is one $2 \times 2$ square somewhere that has different entries, so the cutting into submatrices terminates at $1 \times 1$ at least once.

Once you have the size of the target matrix, you just need to use the fact that no two matrices of the same size will generate the same string. There are $16^2=256$ entries in a $16 \times 16$ matrix. If you have $2$ choices for each entry, there are $2^{256}=115792089237316195423570985008687907853269984665640564039457584007913129639936$ such matrices, so there are that many codes. If you follow the decoding in Mees de Vries' answer you will get the smallest matrix that will generate the number. You can replace all the entries in the matrix with a block of size $2^k \times 2^k$ to get another matrix that would generate the same number.

Answer 2

You can intuitively find the inverse to your mapping easily: then making it formal is just figuring out the language. Let me do a $4\times 4$ example.

You are given the number $210211100$. You simply start at the beginning. You see that the first digit is 2, which means that the four numbers that follow are going to describe the four sub-matrices, top left to bottom right. The first of these is a 1, which means that the top left submatrix has all 1s. So our situation is $$ \begin{pmatrix} 1 & 1 & * & *\\ 1 & 1 & * & *\\ * & * & * & *\\ * & * & * & * \end{pmatrix}. $$ Then follows a 0, so the top right submatrix is all zeroes. The situation is $$ \begin{pmatrix} 1 & 1 & 0 & 0\\ 1 & 1 & 0 & 0\\ * & * & * & *\\ * & * & * & * \end{pmatrix}. $$ The next digit is a 2, which means the next submatrix does not consist of all zeroes or all ones, but is instead given by the next four numbers in our number. The first of those is a 1, which means that the top left submatrix of our bottom left submatrix is all ones. (In fact, it is a single 1, since this is a $1 \times 1$ submatrix.) $$ \begin{pmatrix} 1 & 1 & 0 & 0\\ 1 & 1 & 0 & 0\\ 1 & * & * & *\\ * & * & * & * \end{pmatrix}. $$ The next three digits are $110$, which gives the rest of the entries in the bottom left submatrix in a similar way. $$ \begin{pmatrix} 1 & 1 & 0 & 0\\ 1 & 1 & 0 & 0\\ 1 & 1 & * & *\\ 1 & 0 & * & * \end{pmatrix}. $$ Finally, the final digit of our number is a 0, which means that the bottom right submatrix is once again all zeroes. $$ \begin{pmatrix} 1 & 1 & 0 & 0\\ 1 & 1 & 0 & 0\\ 1 & 1 & 0 & 0\\ 1 & 0 & 0 & 0 \end{pmatrix}. $$ Can you now decode $2200100211011$ into a $4 \times 4$ matrix? Do you see why different matrices have different numbers? Can you prove it formally?

Answer 3

Do I have it right that you're asking for combinations of binary place holders (bph)?

$$f(256 \text{bph}) = 2f(64 \text{bph})f(64 \text{bph})f(64 \text{bph})f(64 \text{bph})$$

where

$$f(64\text{bph}) = 2f(16\text{bph})f(16\text{bph})f(16\text{bph})f(16\text{bph})$$

where

$$f(16\text{bph})=2f(4\text{bph})f(4\text{bph})f(4\text{bph})f(4\text{bph})$$

where

$$f(4\text{bph})=2f(1\text{bph})f(1\text{bph})f(1\text{bph})f(1\text{bph})$$

where $f(1\text{bph})$ could be either $0$ or $1$, so since $f(1\text{bph})$ can only occur in two ways, that's $2^1$, but for each of the four slots thats $(2^1)^4=2^4$ ways for $f(4\text{bph})$ to occur, but what if the $4\text{bph}$'s are all $0$'s/$1$'s, then that's minus $2$, giving a total number of ways $f(4\text{bph})$ can occur to be $2^4-2$, but you've taken two possibilities, i.e., $20000$ and $21111$, and added $0$ and $1$, so it's back to $2^4$.

Then move up to $f(16\text{bph})$. This can happen $(2^4)^4$ ways minus the two instances where all four $f(4\text{bph})$s are $0/1$-padded, but $0$ and $1$ are added, so $(2^4)^4$.

Then move up to $f(64\text{bph})$. This can happen $((2^4)^4)^4$ ways minus the two instances where all four $f(16\text{bph})$s are $0/1$-padded, but $0$ and $1$ are added, so $((2^4)^4)^4$.

Then move up to $f(256\text{bph})$. This can happen $(((2^4)^4)^4)^4$ ways minus the two instances where all four $f(64\text{bph})$s are $0/1$-padded, but $0$ and $1$ are added, so $(((2^4)^4)^4)^4$.

So, there are

_{115792089237316195423570985008687907853269984665640564039457584007913129639936}

ways.

More specifically if $X$ is a $2^n \times 2^n$ matrix with $0,1$ as entries, and $f$ is a function such that $f(X)=1$ if all the elements are $1$, $f(X)=0$ if all the elements are $0$, and $f(X)=\overline{2f(A)f(B)f(C)f(D)}$ otherwise, where $A, B, C, D$ are 4 smaller $2^{n-1} \times 2^{n-1}$ matrices, and "$\overline{2f(A)f(B)f(C)f(D)}$" represents the joining (possibly recursively) of digits, then the number of elements, $|\mathscr{S}|$, in the range, $\mathscr{S}$, of $f(X)$ for $n=4$ is as follows:

$$|\mathscr{S}|=(((2^4)^4)^4)^4$$

Answer 4

We shall consider a number $S$ (which, in fact is a ternary word) as a program for an automaton which (uniquely) recovers the $2^n\times 2^n$ matrix $M$ from $S$.

Initially we have $2^n\times 2^n$ empty table, hierarchically partitioned into canonical $2^k\times 2^k$ subtables for all $0\le k\le n$. That is the table is partitioned into four $2^{n-1}\times 2^{n-1}$ subtables exactly as you partitioned the matrix $M$ into four $2^{n-1}\times 2^{n-1}$ matrices, each of these subtables is partitioned into four $2^{n-2}\times 2^{n-2}$ subtables and so forth. These four subtables in which we have partitioned a subtable $T$ we shall call childs of $T$, and they are enumerated from top left to down right. Finally, for each canonical subtable $T$ we define its next subtable $n(T)$ as follows. In $T$ is the table then $n(T)$ is nil. Otherwise $T$ is $k$-th child of some subtable $T’$. If $k<4$ then put as $n(T)$ $k$-th child of $T’$, otherwise put $n(T)=T’$.

The automaton consecutively reads digits of $S$ and selects canonical subtables of the table, sometimes filling them with $1$’s or $0$’s, according to the following algorithm. Assume that there is selected a canonical subtable $T$ and the automaton have read a digit $d$. If $d$ is $0$ or $1$ then the automaton fill all cells of $T$ with $d$ and selects the table $n(T)$. If $n(T)$ is already completely filled then it selects $n(n(T))$ an so on, until it will select a not completely filled subtable or $n(T)$ will became nil. In the latter case the automaton finishes its work. If $d$ is $2$ then the automaton selects the first child of $T$. The construction of $S$ from $M$ imply that the automaton (uniquely) recovers the matrix $M$ from $S$. This can be seen by claim (which is proved inductively by $k$) that when the automaton have selected a $2^k\times 2^k$ canonial subtable $T$, it completely fills $T$ before selecting $n(T)$.