Elwyn--->*Alvin P.S sorry

RegulusB-8 wrote: Elwyn--->*Alvin The official problem says Elwyn

Anyone solved this during the contest ??

I managed to prove the following claim in the contest (but couldn't find a way to prove that we can make all entries nonnegative): We can get from a table to another table by a sequence of moves iff for every rook set the sums of the numbers written on its squares for both tables are equal.

Nersik.883 wrote: Anyone solved this during the contest ?? one guy from our team

I missed this in-contest, but solved it shortly afterwards. Nice Problem WLOG there is some rook-set whose sum is 0. WLOG this is the diagonal from top left to bottom right. First, we repeatedly alter the $i'$th row and $n'$th column, till the above diagonal holds only 0s. Now, define $S_{ij}$ as follows. Consider each sequence with distinct terms $i = a_1, a_2, \cdots, a_m = j$, and take the minimum value of $A_{a_1,a_2} + A_{a_2,a_3} + \cdots + A_{a_{n-1},a_n}$. Over here $A_{ij}$ denotes the value in the $i'$th row and $j'$th column. Claim: $A_{ij} \geq S_{ij}$ Proof: Follows from the definition. Pick the sequence $a_1 = i, a_2 = j$ Claim: $A_{a_1,a_2} + A_{a_2,a_3} + \cdots + A_{a_m,a_1} \geq 0$ Proof: Observe that $(a_1, a_2), (a_2,a_3), \cdots (a_m,a_1), (x,x)\forall x \neq a_k$ forms a rook-set. Since $A_xx = 0$, the conclusion follows. Claim: $S_{ij} + S_{jk} \ge S_{ik}$ Proof: Consider the sequence which attains minimum value for the $S_{jk}$ part, and append it to the sequence for the $S_{ij}$ part. By the above claim, we observe that repeating elements cannot possibly lower the value of $S_{jk}$. i.e. we should get rid of the part between repeated elements for smallest value of $S_{ik}$ Now we will decrease the $i'$th row by $x_i$ and increase the $i'$th column by $x_i$. We greedily choose the values of $x_i$, starting from an arbitrary value of $x_1$ Assume $x_1, \cdots, x_{m-1}$ have been picked. We Choose $x_m$ so that $x_k+S_{mk} \geq x_m$ and $x_m + S_{km} \geq x_k$ for all possible $k$. Suppose FTSOC that $x_j + S_{mj} < x_i - S_{im}$ for some $i,j$. We would then have $x_i - x_j > S_{im} + S_{mj} > S_{ij}$ which is a contradiction. We would have prevented this while picking $x_i, x_j$. This means that we can sucessfully pick the values like this. We now claim that we're done. $A_{ij}$ decreased by $x_i$ and increased by $x_j$. So it now holds the value $x_j - x_i + A_{ij} \geq -S_{ij} + A_{ij} \geq 0$

BlackFlower wrote: Nersik.883 wrote: Anyone solved this during the contest ?? one guy from our team Where are you from

Inshaallahgoldmedal wrote: BlackFlower wrote: Nersik.883 wrote: Anyone solved this during the contest ?? one guy from our team Where are you from wrong solution

If we impose an additional condition that all numbers on the board sum to zero, I have a solution, so that at the end all numbers become zero. The thing is, it's not easy to reduce the general case to this special case. E.g. we can't just subtract everything by the same amount for example, because maybe $n-1$ rook sets add to zero but the last rook set is positive. So when you subtract everything by the same amount, the rook-set condition is no longer fulfilled. Or maybe at the end, only one cell is positive and the rest is zero. Anyhow if all numbers on the board sum to zero, that means all rook sets also sum to zero. We prove using induction. $2 \times 2$ is easy to solve. Now, pick a cell that is zero (or make one cell zero), and reorder columns/rows so that this is bottom right ($A_{n,n} = 0$). Consider submatrix $B$ comprising the first $(n-1)\times(n-1)$ cells. All rook sets in $B$ would also extend to a rook set in $A$ by adding $A_{n,n}$. So this rook set would sum up to zero too. Therefore, the $B$ satisfies the problem condition, and it can be made all zero by a series of actions. Note that all actions do not affect $A_{n,n}$, but will affect $A_{i,n}, A_{n,i}$ for $i < n$. Then suppose $A_{1,n} = x$, we claim that $A_{i,n} = x , A_{n,i} = -x \forall i < n$. Proof: Any action does not change rook set condition specified in the problem. So all rook sets in $A$ still have to sum up to zero. Then this is a rook set: $\{ (i,n), (n,i) \} \cup \{ (j,j) | j \neq i,n \}$. Therefore $A_{i,n} = - A_{n,i} \forall i< n$ And this is also a rook set: $\{ (n,2), (2,1), (1,n) \} \cup \{ (j,j) | j \neq 1,2,n \}$ Therefore $A_{n,2} = -x, A_{2,n} = x$ and so on. So the claim is proven. Lastly, we perform the action on cell $(n,n)$ to make everything zero.

Equation overload! Makes you wonder why a problem with $n^2$ degrees of freedom is bound by $n!$ expressions. $\rule{25cm}{2pt}$ $\textbf{Conventions preamble.}$ Here we define some subjects we can operate on, what the properties of those subjects are, and how they relate to each other (and to other subjects, too!) Subjects: Define a cell $C_i, 1 \leq i \leq n^2$ with $i = ak+b, 0 \leq a \leq n-1, 1 \leq b \leq n$ to denote the cell in the $(a+1)^{th}$ row and $b^{th}$ column. Define a move $(i,j,a)$, where $0 \leq i,j \leq n; i,j \in \mathbb{N}$ and $a \in \mathbb{R}$, to represent the action of adding the real number $a$ to the row $r_i$ and substracting $a$ from the column $c_j$. Define a $PC$ (particular configuration of cells) to be a random $n^2-$tuple which corresponds to a distribution of numbers in the table, and Define a rook set $RS_i$, $1 \leq i \leq n!$ similar to the problem. Relations: A cell $\textit{belongs}$ to a rook set if it is one of the $n$ cells forming the rook set. The $\textit{rook-set characteristic}$ of a $PC$ to be the $n!-$tuple $(v(RS_1),v(RS_2),\ldots, v(RS_{n!}))$ (Definition of $v$, or value, is at $\textit{properties}$.) An $n!-$tuple $(t_1,t_2,\ldots,t_{n!})$ is $\textit{characteristically formable}$ by the $PC$ $(u_1,u_2,\ldots,u_{n^2})$ if that $PC$'s rook set values $(v(RS_1),\ldots,v(RS_{n!})) = (t_1,\ldots,t_{n!})$. Properties: The $\textit{value}$ of a rook set $RS_i$ to be the sum of $n$ cells which $\textit{belong}$ to it. Moreover, say a rook set is $\textit{positive}$ if its value is positive. Define a $\textit{negative}$ and $\textit{zero}$ rook set the same way. A cell $C_i$ is $\textit{rook-wise positive}$ if $\forall RS_j$ so that $C_i$ $\textit{belongs}$ to $RS_j$ implies $RS_j$ $\textit{positive}$. A $PC$ is $\textit{rook-set good}$ if $v(RS_i) \geq 0, \, \forall 1 \leq i \leq n!$, and a $PC$ is $\textit{entirely good}$ if $C_i \geq 0, \, \forall 1 \leq i \leq n^2$. One other important thing: out of any rook set $RS_k$, it is possible to form a bipartite graph with $n$ vertices on both compartments $A$ and $B$; and that graph is a perfect matching, given that an edge is formed between $A_i \in V(A)$ and $B_j \in V(B)$ iff the cell $C_{(i-1)n+j}$ belongs to the rook-set $RS_k$. With that already established beforehand (hopefully they aren't too contrived, and there are no double meanings) we now proceed to the Main Claim. $\color{magenta} \rule{25cm}{2pt}$ $\color{magenta} \textbf{Main Claim: Inversely entirely good.}$ If a characteristically formable $n!-$tuple $(t_1,t_2,\ldots,t_{n!})$ is rook-set good, then there is an entirely good $PC$ with exactly the same values. To prove that, we use a simpler one: $\color{red} \rule{25cm}{1pt}$ $\color{red} \textbf{Sub-Claim: Not all impure.}$ Say a positive rook set is formed by $n$ cells $C_{i_1},\ldots,C_{i_n}$. If the $PC$ corresponding to it is rook-set good, then some cell $C_{i_j}$ is rook-wise positive. (a guarantee for all $(n-1)!$ rook sets to be positive!) $\color{red} \textbf{Sub-Claim Proof.}$ Basically Hall's Theorem. If all $n$ cells are $\textbf{not}$ rook-wise positive, then each cell must belong to one rook set which is zero (they cannot be negative due to the $PC$'s property.) Summing the value of those zero rook sets, we can obtain $n$ perfect matchings when the $n$ bipartite graphs corresponding to those rook sets are unified ($\textbf{duplicate edges/cells are permitted}$). Removing the initially positive rook set, by Hall's applied $n-1$ times, we can pull out another $n-1$ perfect matching which corresponds to $n-1$ rook sets. However, the sum of values of the second family of rook sets must be positive, a contradiction (to the zero sum obtained by summing the zero rook sets.) $\blacksquare$ $\color{red} \rule{25cm}{1pt}$ $\color{magenta} \textbf{Main Claim Proof.}$ Construct the entirely good $PC$ inductively. Start with a $PC_0' = (0,0,\ldots,0)$ and $RS|C_0$ (rook-set characteristic 0) $= (t_1,t_2,\ldots,t_n)$. Assume after the $i^{th}$ step of the construction not all numbers in $RS|C_i$ is zero (here we always keep $RS|C_i$ to be rook-set good.) To construct $PC_{i+1}'$ and $RS|C_{i+1}$ from their $i$ counterparts, pick a random rook-set with positive value. Among its $n$ cells, there exists one $C$ in the $i^{th}$ row and $j^{th}$ column which is rook-wise positive --- so that all other rook sets it belongs to is positive. Now pick \[ \left(C_{(i-1)n+j} \in PC_{i+1}'\right) = \left(C_{(i-1)n+j} \in PC_i' \right)+ \min\{v((n-1)! \, \, \text{rook sets the cell belongs to})\} \]and keep the remaining cells unchanged. Note that after this process, $RS|C_{i+1}$ is still a rook-set good characteristic, with at least one more $\textit{zero}$ rook set. So, this process will end, and the end product $PC$ is the one we're looking for. $\blacksquare$ $\blacksquare$ $\color{green} \rule{25cm}{2pt}$ $\color{green} \textbf{Final Algorithm.}$ The most obvious part of this Solution. We now return back to tackle the problem. $\color{green} \textbf{Step 1.}$ If a $PC$ has rook-set characteristic $(0,0,\ldots,0)$ then we can perform some moves to it so the $PC$ will turn into $(0,0,\ldots,0)$. $\color{green} \textbf{Proof 1.}$ Induct as in post $\#11$. To simplify it: $n=1,2$ easy. For $n = k+1$, fix the bottom right cell to be $0$, and perform some moves so that the top-left $(k) \times (k)$ cells are all zero (by induction.) Since the rook-set characteristic is invariant, all cells in row $n$ have the same value $a$ (except for the bottom-right cell), and all cells in column $n$ have the same value $-a$ (except, again, for the bottom-right cell). Perform the move $(n,n,-a)$ FTW. $\color{green} \textbf{Step 2.}$ General case. $\color{green} \textbf{Proof 2.}$ Consider a rook-wise good $PC_1$. By $\textbf{Main Claim}$, exists a $PC_2$ with equal rook-wise characteristic. Let $PC_3$ be the particular configuration that we get when substracting (cell-by-cell) $PC_1$ with $PC_2$. Notice that $PC_3$ have rook-set characteristic all zero. By $\color{green} \textbf{Step 1}$, there exists a sequence of moves that transforms $PC_3$ to $(0,0,\ldots,0)$. Then, this sequence of moves will also transform $PC_1$ to $PC_2$ by simple arithmetic. We are done. $\blacksquare$ $\blacksquare$ $\blacksquare$

ok this is basically about the linear space of matrices $\mathbb{R}^{n\times n}$ with inner product $\langle A,B \rangle= tr (A^{T}B)$ , call the initial matrix $A$ First lemma : the vector subspace of matrices elwyn can add to $A$ is the same as , the vector subspace of matrices where all rook sets sum to $0$ both being equal to vector space $V\subset \mathbb{R}^{n\times n}$ of all matrices of the form : $$\begin{pmatrix} x_1+y_1 & x_1+y_2 & ... & x_1+y_n \\ x_2+y_1& x_2+y_2 & ... & x_2+y_n \\ & &... & \\ x_n+y_1 & x_n+y_2 & ... & x_n+y_n \end{pmatrix}$$Where $x_1+...+x_n=y_1+...+y_n=0$ Proof:The first part is straightforward , for the second part set $$x_i=\frac{a_{i1}+...+a_{in}}{n} , y_j=\frac{a_{1j}+...+a_{nj}}{n}$$and then for the matrix with entries $a_{ij}-x_i-y_j$ every rook set,row , column has zero sum and from that deduce that it is identically zero. Lemma2: The orthogonal complement of $V$ is the space of all matrices whose all rows and columns sum to the same number , the proof is straightforward. Lemma3: Every doubly stochastic matrix $P$ whose all elements are positive and all rows and columns add up to $1$ can be expressed as a convex combination of permutation matrices and we have that $ \langle P,A \rangle\ge 0$. Proof: The inner product of a permutation matrix and $A$ is the sum of some rook set and thus positive . To express $P$ as a positive sum of permutation matrices we repeatedly find a rook set of positive entries and then subtract the corresponding permutation matrix multiplied with a suitable constant and then rescale to get a doubly stochastic matrix with more zeroes. So we just need a doubly stochastic matrix to contain a rook set of nonnegative elements which is basically a perfect matching of rows and columns whose common cell contains a positive number. For that we use the matching theorem ,let rows $r_1,r_2,...,r_k$ share nonzero elements with columns $c_1,c_2,...,c_l$ the $k$ rows have total sum $k$ thus the $l$ columns have total sum at least $k$ and thus $l\ge k$ (I later found out that this is a well known theorem). Ok so the problem is about proving that there is some matrix $D\in \mathbb{R}_{+}^{n\times n}$ such that $A-D\in V$ For the sake of contradiction suppose that the convex sets $$(A-\mathbb{R}_{+}^{n\times n} )\cap V=\emptyset $$are disjoint . . Ok let $\mathbb{R}_{+}^{n\times n}=K\cup L$ be where $K=\{ D\in \mathbb{R}_{+}^{n\times n} , \sum (D)\le \sum (A)+1\}$ ($\sum$ stands for the sum of all entries). The set $A-K$ is compact and therefore has a positive distance from $V$ therefore we can safely move the entire set $A-\mathbb{R}_{+}^{n\times n}$ slightly by adding a perturbation matrix $\delta$ whose elements are positive such that $A+\delta-K$ is disjoint from $V$ and $\sum (\delta)<1$ thus $\sum (A+\delta-D)<0$ for every $D\in L$ and then $A+\delta-L$ and $V$ are also disjoint and so $$A+\delta -\mathbb{R}_{+}^{n\times n}\cap V=\emptyset $$are disjoint . Now the hyperplane separation theorem gives us a matrix $U$ such that $$\langle U, D_1 \rangle \le \langle U, D_2 \rangle$$for every $D_1\in A+\delta -\mathbb{R}_{+}^{n\times n}$ , $D_2\in V$. Since $V$ is a vector space we should have that $\langle U, D_2 \rangle=0$ and $U$ is in the orthogonal complement of $V$(see lemma 2). Furthermore if there was a negative entrie in $U$ we could choose a matrix in $\mathbb{R}_{+}^{n\times n}$ whose corresponding entrie is massive and the rest zero and $\langle U,D_1 \rangle \le 0$ wouldn't hold . Therefore $U$ has nonnegative entries and from all the above we may assume that $U$ is doubly stochastic and we get that $\langle U,A+\delta \rangle\le 0$ , $\langle U , A \rangle <0$ a contradiction.