Vintik and Shpuntik return from a fairytale land and solve a problem in the world of ordinary mathematics
Now that the reward promised by the respected @vvvphoenix in the original article has found its hero here, we can consider the real way to solve the problem, and at the same time see how beautiful pictures and smart words lead us away from the real solution to the problem.
In fact, I haven't changed my mind and the previous article:
Vintik and Shpuntik master quantum computing
deserves the highest rating, because it is an article, not a mathematical work. But I still suggest trying to consider one of the mathematical methods for solving the problem that is considered there only as an introduction to the main topic in more detail.
There is a book that is widely known in narrow circles
The Leprechauns of Software Engineering
about how myths are created in the IT industry. This book says that mistakes in an article with beautiful pictures and formulas bring much more harm to the industry, because looking at a beautiful wrapper, people are more inclined to believe in the quality of the content.
Beautiful terms
Let's start by looking at the beautiful name of the task, arrangement of non-beating rooks (meaning on the field of a square matrix). Agree, it sounds beautiful and even romantic, only we must determine purely mathematically what this means, but for some reason the mathematical definition is not given anywhere. After all, from the point of view of mathematics, it is important to calculate that the rooks do not beat each other when placed on the field, how to do this? It is very simple, if you write ones in the cells-cells of the rooks' location, and zeros in the free cells, then if the sum calculated for each column and row does not exceed one, this means that the rooks are positioned in such a way that they do not beat each other.
Another remarkable term, which the author of the previous article quite rightly cites, is matrix permanent. The term sounds so scientific and even I would say aristocratic, that we involuntarily become imbued with absolute trust in everything that the author will write next, that is, such terms greatly contribute to turning off the reader's critical perception (of course, I am only describing my perception, but I think to some extent this happens to many, but certainly not to everyone).
So, it is precisely with this most respected permanent that the first, perhaps not quite an error, but an inaccuracy nevertheless not admissible for mathematical constructions is connected. The author suggests that we look for the permanent of the matrix, although within the framework of our task we should look for the number of terms in the permanent.
It is easy to see that the number of terms in the permanent of a 3×3 matrix is 6:
And this is the number of possible arrangements of non-beating rooks on a 3×3 board.
Permission Matrix
And here we come to another important definition from a mathematical point of view, necessary for solving this problem, the fact is that we will have to work with two types of matrices (and who said that the problem is simple?), let's call them the resolution matrix and the decision matrix.
The resolution matrix is a matrix in which the cells in which a rook CAN be placed are marked with ones, i.e. one can place one in the solution matrix. And the solution matrix is a matrix with rooks placed (also with ones, but indicating the selected rook position from those allowed by the resolution matrix).
It is easy to see that for an arbitrary square identity matrix of dimension N in which all cells are allowed, the number of rook arrangements is determined by the simple factorial of N (N!).
Analysis of the minimal ternary variant
And with this knowledge we move on to the analysis of the matrix of the problem compiled by the author in his telegram:
First, it should be noted that this is precisely a resolution matrix, and the task is to find the number of unique solution matrices. The solution matrix in this case will be a matrix with ones placed in dark cells such that for all its columns and rows the sum of the elements in them must also be equal to one.
Here it is necessary to clarify that if the sum in at least one column or row is equal to zero, this means that there was no rook there and such a matrix is NOT a solution, since the correspondence must be ensured for all rows of numbers without exception with one missing digit.
Now those who have had at least some dealings with calculations and matrix analysis should remember that matrix analysis is largely related to the rearrangement of rows or columns in a matrix and the first thing we should do is try to rearrange, for example, the rows so as to see some regularity in the arrangement of units in the resolution matrix. Such regularity can help us understand the method of calculating the unique arrangements that interest us.
We can transform our matrix, for example, like this:
It can be assumed that the number of unique arrangements in one of the highlighted squares will help us understand how to calculate the number of arrangements in the full matrix, so at least it is worth trying to do this exercise manually. For example, like this:
Here is an example of manual arrangement from top to bottom. We see (know) that the choice of the position of one rook prohibits the use of allowed cells in the corresponding column (black lines) and row, so it is easy to calculate that there are only 6 (six!) options for filling the three upper rows, with each of which only 2 (two!) options for filling the three middle rows can be joined. The values in the last three rows are uniquely determined by the distribution in the upper six. In total, there are only 6 * 2 = 12 options for arrangement in this segment of the matrix!
Once we have decided on the selected position in the last three lines, we have only two options to set the value in the right adjacent matrix, which has only three allowed cells, that is, for each of the 12 options there are 2 options on the right that control the columns of the central 9×9 segment.
And it turns out that we have only one option to set the value in the lower adjacent matrix, which also has only three allowed cells, that is, 12 options from the upper segment uniquely determine the only free row out of three in the central 9×9 segment.
The following image shows how the prohibitions from the upper left segment are propagated to the middle segment via the lower and right adjacent segments of the upper left segment.
Thus, the transition to the central segment gives us a multiplication of the arrangement options two times two times, which results in 12 * 2 * 2 = 48 arrangement options in a 18×18 matrix, and then everything becomes deterministic since the maximum number of possible prohibitions is distributed, that is, there remains one deterministic option specified by one of the 48 options selected above.
Conclusion
I do not exclude that I made a mistake somewhere, so check. But I am almost sure that there is no mistake for the first segment 9×9 and therefore the total number of options cannot go very far from the number 12 and therefore the result announced in the previous article
calculations for N=3 (27×27 matrix) in python take about an hour and give 10,752
seems extremely doubtful to me, especially suspicious is the number 7 in the factorization of this result, which does not seem to have a source in the numbers of the initial conditions of the problem. I think no one has included in the Python program at least a check that all the sums of the rows and columns of each of the 10,752 variants of arrangements give units. Not to mention a check for the uniqueness of the arrangements.
To be honest, I don’t really like solving such problems, which in my opinion have absolutely no practical meaning, but I don’t like observing POSSIBLY incorrect solutions to mathematical problems even more, so I decided to develop and share the reasons for my doubts with the audience.
