This is what I did: Basically, all that matters is the multiset of x-coordinates and the multiset y-coordinates, because we can switch y-coordinates arbitrarily. Then, I used a "balls and sticks" argument to arrive at an answer of $\dbinom{m+n-1}{n-1}^2$.

How I couldn't get the second part for 3 hours?

Whats multiset I did it with sum of elements in rows/columns and did balls and sticks too, but my sol was weird

I used the fact that the row sums and column sums of the grid are invariant under stone moves. My proof was somewhat messy though

Yay same

I got the invariant but what was the rest of the sol?

alex31415 wrote: This is what I did: Basically, all that matters is the multiset of x-coordinates and the multiset y-coordinates, because we can switch y-coordinates arbitrarily. Then, I used a "balls and sticks" argument to arrive at an answer of $\dbinom{m+n-1}{n-1}^2$. Is that the same as stars and bars?

champion999 wrote: alex31415 wrote: This is what I did: Basically, all that matters is the multiset of x-coordinates and the multiset y-coordinates, because we can switch y-coordinates arbitrarily. Then, I used a "balls and sticks" argument to arrive at an answer of $\dbinom{m+n-1}{n-1}^2$. Is that the same as stars and bars? Yes

mssmath wrote: I got the invariant but what was the rest of the sol? if the row and column totals are the same, prove that they are equivalent just go row by row

Hmm, I got the right answer, but I couldn't prove that you could switch any two with the same multiset. I proved using a "greedy"-ish algorithm that for each multiset of $x$- and $y$-coordinates, there exists at least one piling.

Spent 2 hours trying to prove induction on n and m before realizing the invariants of the row and columns under stone moves.

I got ${m+n-1\choose m}^2$ as well. @alex31415: I don't think you should say multiset, though. Each row and column should be equal in both pilings, and order matters, so if you don't call it a function, I think you should say a tuple. I tried to fill in all the gaps in my proof, mostly by choosing extremes, but I'm not completely sure so 5-7. And I did choose $n$ to be the least in part of my solution so I guess you can kind of say it's induction (yes, I proved the base case), but it might be redundant, although I'm pretty sure it works.

#4 was IMO a much easier and less dumby problem that #1. Took about 1 min to solve... Solution below:

Wait darn What do you think I'll get for doing everything right but saying the final answer was m+n-1 choose m-1 squared instead of choose m.

Probably 5 or 6, the last part isn't really a key part of the solution.

tim9099xxzz wrote: What do you think I'll get for doing everything right but saying the final answer was m+n-1 choose m-1 squared instead of choose m. If they think it's just a typo, you might get 7. Let's hope so.

alex31415 wrote: $\dbinom{m+n-1}{n-1}^2$. darn I solved this but didn't know how to prove it

Wait those are equivalent by Pascal right?

pad wrote: If $d_{i'j'}>0$, then $S$ decreases by 4, and if $d_{i'j'}<0$, then $S$ decreases by 2. How did you get this? I got that $S$ decreases by 0 in both cases -- because essentially, within the rectangle you are performing the stone move on, the total number of stones will stay the same.

too lazy to provide a full solution, but here's a rough sketch: The claim is that two pilings are equivalent if and only if the number of stones in each column and row is the same (meaning that the number of stones in column $n$ of the first piling is the same as the number of stones in column $n$ of the second, and similarly for rows). The proof is just to perform $n$ groups of moves so that the $i$th group of moves makes the $i$th row match up. Then stars and bars (after noting that any two $n$-tuples of nonnegative integers that sum to $m$ will work) gives $\binom{m+n-1}{m}^2$.

We claim that the answer is $${{m+n-1} \choose {m}} ^2.$$ Main Claim: two configurations are equivalent if and only if they have the same row sums and the same column sums. The "only if" part is due to the fact that any move keeps the row sums and column sums invariant. For the "if" part, we use induction. For the base case $n=2$, this is clearly true as we can just repeat moves in one direction until we get the desired configuration. We then consider two $n+1$ by $n+1$ grids that have the same row sums and column sums. We will try to "solve" the first grid, i.e. make it the same as the second through a sequence of moves. We can first solve the last row by swapping stones within that row and considering pairs. Similarly, we can then solve the last column. Now, the two $n+1$ by $n+1$ grids have the same last row and same last column. Since the row sums and column sums are still equal, this means that the remaining $n$ by $n$ that we haven't solved yet also has the same row sums and column sums in the two grids. Therefore, by induction, if we can solve $n$ then we can also solve $n+1$, which shows the claim. Therefore, the answer is simply the number of different $2n$-tuples of row sums and column sums that we could have, which by stars and bars is $${{m+n-1} \choose {m}} ^2.$$

Here's a quite elegant solution: Let the top row be row $1$ and the leftmost column be column $1$. We claim that the answer is $\boxed{\binom{m+n-1}{n-1}^2}$. To prove this, we introduce some lemmas: Lemma 1: Define an inversion to be a pair of stones on the squares $(x_1,y_1)$ and $(x_2,y_2)$ such that $x_1 < x_2$ and $y_2 < y_1$. For every piling of stones, we can do operations on it to ensure there are zero inversions left. Proof. Let $I$ be the number of inversions. If $I>0$, choose an inversion with stones $a$ and $b$ on the squares $(x_1,y_1)$ and $(x_2,y_2)$ such that $x_1 < x_2$ and $y_2 < y_1$. Let $R$ be the rectangle of squares with corners $(x_1,y_1)$ and $(x_2,y_2)$, $S$ be the set of squares outside $R$. After performing an operation on these squares, the inversion count between each square in $S$ and $a$ or $b$ remains invariant. Details are omitted, but this can be shown by checking some (very simple) cases. Moreover, there used to be at least one inversion between $R$ and $a$ or $b$, but now there are no longer any inversions. Thus, $I$ decreases after this operation. Repeating this process, $I$ will eventually become zero. $\blacksquare$ Lemma 2: Define a path piling to be a piling where the stones trace a path that only goes down and right. The problem reduces to counting the number of non-equivalent path pilings. Proof. Any piling with zero inversions must trace a path going down and right. Because we can convert all pilings into a path piling, non-equivalent pilings must make non-equivalent path pilings. $\blacksquare$ Lemma 3: The number of stones in each row and column remains invariant over all operations. Proof. Trivial. (Just look at the changes each operation makes to the counts of the respective rows and columns). $\blacksquare$ Lemma 4: Suppose we allocate $a_i$ stones to row $i$ and $b_i$ stones to column $i$, such that $m=\sum_{i=1}^n a_i = \sum_{i=1}^n b_i$. Then there is exactly one path piling satisfying this. Proof. We design an algorithm that generates the unique path piling. Consider $(1,1)$. It must have $\min(a_1, b_1)$ stones because if it has less, then there must be other stones in row $1$ and column $1$, creating an inversion. After placing $\min(a_1, b_1)$ stones, row $1$ and/or column $1$ is full, so we can fill the rest of the row/column with zeros. Now, subtract $\min(a_1, b_1)$ from $a_1$ and $b_1$ and repeat this step with the top-left undetermined square. Eventually, only $(n,n)$ is undetermined. But then, $a_n=b_n$ because $m=\sum_{i=1}^n a_i = \sum_{i=1}^n b_i$. So after filling $(n,n)$, we have constructed the unique path piling satisfying the conditions. $\blacksquare$ Thus, the answer is simply the number of ways to generate sequences $a$ and $b$, which by stars and bars is $\boxed{\binom{m+n-1}{n-1}^2}$.

What I consider interesting about this problem is that beyond the first (satisfying but pretty standard fare?) observation concerning invariance of row and column sums up to equivalency, the actual proof comprises two other disjoint parts (equal multisets imply equivalency, and all pairs of multisets are attainable) that are hard to both catch, but individually are quite straightforward to prove. Seems like the type of problem that a student would hate to solve (in particular, argue rigorously) but a teacher would love to assign to the student. Nonetheless, I suppose it's good that such a problem exists :')

We claim that the answer is $\binom{m+n-1}{n-1}^2$ Let the grid have rows labeled $1,2,...,n$ and columns labeled similarly. Let the set of $x$-coordinate values be denoted by $X={x_{1},x_{2},...,x_{m}}$ and the $y$-coordinate values be denoted similarly. We claim that any configuration of $m$ points from $X$ and $Y$ can be achieved from any other configuration defined similarly. To see this, repeatedly swap two coordinates until the configuration maps onto the other. Now we have to calculate the number of ways for set $X$, which is $\binom{m+n-1}{n-1}^2$.

Proof: It doesn't matter how the stones were initially put into the squares of each column, since one distribution can always be swapped into another through some sequence of stone moves. So once we fix how many stones are distributed into each of the columns, we fix the column arrangements. We show that after we also fix how many stones are in each row, we have unique arrangements. It is obvious that any fixed distribution of stones leads to at least 1 arrangement. We prove the other direction via induction. Induction: Base case is 2x2, which can be completed by swapping the stones in the 2 columns until you get what you wanted. If an N by N grid works, then N+1 by N+1 grid also works because we can always fix the (N+1)th column and (N+1)th row in some set of moves, then it becomes NxN grid left to do. Once we have proved that all such distributions of stones into rows and columns produce unique grids, we use stars and bars to find how many ways are there to distribute m stones into n row/columns. By stars and bars, each of them is $${{m+n-1} \choose {n-1}}$$. So we find the answer for the problem to be $${{m+n-1} \choose {m}} ^2.$$ $$

Answer is ${m+n-1 \choose n-1}^2$. The point is that labeling the sum of the number of stones on every row and every column uniquely fixes the configuration. The proof of one direction is by induction on an $m \times n$ grid on the value of $m+n$. Suppose we have a grid $G$ of stones and we want to get to a grid $G'$ with the same signature. If there exists a row or column in $G$ identical to that on $G'$, we can delete those rows and induct down. Now assume otherwise. Consider any row $R$; we will describe an operation that decreases the number of stones in that row that are out of place. To do so, consider a square $s$ in $R$ that has less stones than $G$ than $G'$. Then, there is a square in the column through $s$ that has stones in it. We may perform the stone move on that square and any square in $R$ that has more stones in $G$, which works. To show that such a configuration exists for every multiset, we can induct again. If there is a row or column with no stones, remove that row or column. Otherwise, pick the row or column with the minimal number of stones $r_1$; we are always able to place the stones in such a way that none of the column sums are violated (otherwise, $nc_i \leq r_1$ for every single column sum $c_i$, which is obviously impossible.) Now remove that row and induct down.

Let $r_i$ denote the number of stones in the $i$th row, and $c_j$ the number of stones in the $j$th column. $r_i$ and $c_j$ are constant since a stone swap removes and adds one stone to each row and column. Furthermore, $\sum r_i = \sum c_j = n$ Then, by stars and bars, there is $\binom{n+m-1}{m}^2$ possible tuples $(r_1, \dots, r_n, c_1, \dots, c_n)$. It remains to show that each tuple, or signature exists, and that same signatures imply equivalent pilings. Consider each piling as a set of $m$ pairs of coordinates $(x, y)$. Then a swap is equivalent to switching $y$ coordinates. This swap allows arbitrary permutations of the $y$ coordinates and the second claim is shown. Furthermore, any tuple can be constructed through pairing $x$ coordinates from $c_k$ and $y$ coordinates from $r_i$.

Another really nice question. Let the number of stones in each row be $a_1,a_2,...,a_n$ and let that in each column be $b_1,b_2,...,b_n$. Let $S=(a_1,a_2,...,a_n,b_1,b_2,...,b_n)$ Note that for any move, S is invariant. Using a greedy algorithm, we can show that any 2 stone positions with identical $S$ are equivalent. This is because the number of positions where they differ always decrease with each stone move, but since this number is non negative and integer, it will eventually reach 0. We also use an algorithm to prove that there exist a valid position for every set $S$ by construction. So the number of non equivalent stone positions is the same as the number of possible set $S$, which is ${m+n-1 \choose n-1}$ Full proof here: https://infinityintegral.substack.com/p/usajmo-2015-contest-review

The answer is : $\boxed{\binom{m+n-1}{n-1}^2}$. DEFINITION: 'family of permutation' : two permutations are said to be in the same family iff they have same number of stones in corresponding rows and columns. Proof: Observe that the number of stones in a row and column is invariant. so we just need to fix the these two numbers and we are done. By stars and bars we have that the number of ways to do so in rows is $\binom{m+n-1}{n-1}$ same for the columns. so the answer is their product i.e $\binom{m+n-1}{n-1}^2$. Now observe that what we are doing is just transpositions, so all permutations can be obtained by just using these. Explicitly if we are given two arrangements of the same family then we can use transposes to make the first $n-1$ columns identical, this also makes the all rows excluding the last cell identical. but after doing this the last column has to be fixed due to the family condition and hence the two are the same. i.e two permutations of the same family are identical. $QED$

Sketch: Observe that the number of stones in each row and column is invariant. So we are essentially counting the number of tuples of non-negative integers $(R_1, R_2 \dots R_n, C_1, C_2 \dots C_n)$ such that $\sum_{i=1}^{n}R_i = \sum_{i-1}^{n} C_i = m$. There are $\binom{n-1+m}{n-1}^2$ solutions to this. Proving that any two grids with the same tuple are reachable from one another and also showing all tuples are achieved by some grid can be done through some standard greedy algorithms.

Notice that each row sum and each column sum is invariant, so we claim the answer is \[\begin{array}{r} r_1+r_2+\ldots+r_n = m \\ c_1+c_2+\ldots+c_n = m \end{array} \implies \boxed{\binom{m+n-1}{m}^2}.\] To show this characterization works, it suffices to prove: Each $(r_i)$ and $(c_i)$ gives a valid configuration: We can fix each square starting from the top square and working from left to right then top to bottom in the top $(n-1) \times (n-1)$ grid, noting that the final squares are fixed. Set each square to the lower amount of the rocks left in its row and its column. Two configurations with the same $(r_i),(c_i)$ pairs are equivalent: We again use the same order of fixing squares in the top $(n-1) \times (n-1)$ grid as before. $\blacksquare$

We claim the answer is $\boxed{\binom{m+n-1}{m}^2}$. Observe that each stone move doesn't change the amount of stones in each row or each collumn. Therefore the number of stones in each row or collumn is invariant. So two configurations are not equivalent if they differ in the amount of stones in any collumn or any row. Claim: For any two configurations with the same number of stones in each row or collumn there exists a sequence of stone moves that sends the first configuration to the second configuration. Proof: The key is to consider making moves to the first configuration and considering $$\sum_{\text{squares}} | \text{amount of stones in square in current config} - \text{amount of stones in this square in config 2}|. $$Observe that if this sum is $0$ we have achieved the same config. But if we haven't achieved this configuration There must exist a square that has more squares than it should have. Then there must exist has less squares than it should have in the same row and collumn as the square that has more squares than it should have that we picked. We can operate on the rectangle containing these three squares, to give a stone to the squares which don't have as much squares as they need. This will either decrease our sum by $2$, or $4$. However this means that eventually after so many moves of this type occur the sum will be $0$. Which means our claim is true. $\square$ Now to finish oberve that by stars and bars there are $\binom{n+m-1}{m}$ ways to chose the sums of the collumns and the rows. Therefore our answer is indeed $\boxed{\binom{n+m-1}{m}^2}$.