3
$\begingroup$

I found this game https://sumplete.com/ and it was made by AI. Let's try to say mathematically what this game is about. We have $n\times n$ matrix $A$. Let $B= \{n\times n \text{ matrices, having } b_1, b_2, ..., b_n \text{ on its diagonal}\}$, $C= \{n\times n \text{ matrices, having } c_1, c_2, ..., c_n \text{ on its diagonal}\}$. In the game we need to find $n\times n$ matrix $X$ with elements from $\{0,1\}$ so that $AX \in B, A^TX^T \in C$. I think that there are a lot of questions we can ask.

For example:

  1. Does this matrix $X$ exist for any $A, B, C$? (obvious one)
  2. Is there a criteria for existence of $X$?
  3. Let all elements in all matrices have elements from $\mathbb{N}$ and an appropriate $X$ exists. Is there an algorythm for finding $X$?
  4. Let all elements in all matrices have elements from $\mathbb{Z}$ and an appropriate $X$ exists. Is there an algorythm for finding $X$? And so on... This list can be easily expanded.

I find this problem very exciting, but I don't have any ideas about significant steps that can be done here :)

$\endgroup$
3
  • 2
    $\begingroup$ A simple observation is that for the existence of $X$ it is necessary that $\sum b_i=\sum c_i$, as $\operatorname{trace}(AX)=\operatorname{trace}(XA) =\operatorname{trace}(XA)^T =\operatorname{trace}(A^T X^T)$. It looks a nice problem. $\endgroup$ Commented Mar 15, 2023 at 23:03
  • $\begingroup$ I think a first step would be to look at the two extreme cases. The one where all the coefficients of $A$ are equal to 1, and the one in which $b_i$ determines the $i$-th row of $X$ (analogous for $c_i$). An instance of the second one would be $a_{ij}=10^{i+j}$, for which it is immediate to compute the matrix $X$ if writing numbers in base $10$. The first case looks simpler than the general problem, but I guess it contains a considerable part of the difficulty $\endgroup$ Commented Mar 16, 2023 at 0:31
  • $\begingroup$ If $A = I$ clearly there isn't any solution unless all $b_i = c_i$ $\endgroup$
    – Zoe Allen
    Commented Mar 16, 2023 at 9:31

1 Answer 1

1
$\begingroup$

This game is in connection with the domain called discrete tomography.

In fact if the issue is

"being given the margins, reconstruct a possible distribution of values in the 9 boxes"

(starting or not from an initial distribution ; I am not certain I have well understood the rules).

A major issue is the non unicity due to the "linear algebra" fact that

An underdetermined system of 9 unknowns and 6 equations can be "solved" by fixing $9-6 = 3$ parameters, which can be considered as "degrees of freedom"...

... this value $3$, not surprizingly, can be interpreted as the dimension of a certain kernel, with for example this basis with 3 elements :

$$\begin{pmatrix}1&-1&0\\-1&1&0\\0&0&0\end{pmatrix}, \begin{pmatrix}1&0&-1\\0&0&0\\-1&0&1\end{pmatrix}, \begin{pmatrix}0&0&0\\0&1&-1\\0&-1&1\end{pmatrix}$$

i.e., a basis of the subspace of matrices for which all the lines and columns sum up to $0$.

Please note that the elements belong to $\mathbb{Z}$. Limitations to elements of $\mathbb{N}$ would imply another branch of mathematics, i.e. linear programming (simplex method, etc.)

In this kind of game, strategies are of a very mathematical nature. Therefore, a (suitably programmed) computer should always beat human players...

Remark : a hidden constraint is that the right margin and bottom margin must have the same sum.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .