Maths Olympiad Prep

Library / /35 of 115

Combinatorics Difficulty 7.0 National olympiad, round 2 Find the answer

Problem
Steve is piling m1m\geq 1 indistinguishable stones on the squares of an n×nn\times n grid. Each square can have an arbitrarily high pile of stones. After he finished piling his stones in some manner, he can then perform stone moves, defined as follows. Consider any four grid squares, which are corners of a rectangle, i.e. in positions (i,k),(i,l),(j,k),(j,l)(i, k), (i, l), (j, k), (j, l) for some 1i,j,k,ln1\leq i, j, k, l\leq n , such that i<ji<j and k<lk<l . A stone move consists of either removing one stone from each of (i,k)(i, k) and (j,l)(j, l) and moving them to (i,l)(i, l) and (j,k)(j, k) respectively,j or removing one stone from each of (i,l)(i, l) and (j,k)(j, k) and moving them to (i,k)(i, k) and (j,l)(j, l) respectively.
Two ways of piling the stones are equivalent if they can be obtained from one another by a sequence of stone moves.
How many different non-equivalent ways can Steve pile the stones on the grid?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let the number of stones in row ii be rir_i and let the number of stones in column ii be cic_i . Since there are mm stones, we must have i=1nri=i=1nci=m\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m
Lemma 1: If any 22 pilings are equivalent, then rir_i and cic_i are the same in both pilings i\forall i .
Proof: We suppose the contrary. Note that rir_i and cic_i remain invariant after each move, therefore, if any of the rir_i or cic_i are different, they will remain different.
Lemma 2: Any 22 pilings with the same rir_i and cic_i i\forall i are equivalent.
Proof: Suppose piling 1 and piling 2 not the same piling. Call a stone in piling 1 wrong if the stone occupies a position such that there are more stones in that position in piling 1 than piling 2. Similarly define a wrong stone in piling 2. Let a wrong stone be at (a,b)(a, b) in piling 1. Since cbc_b is the same for both pilings, we must have a wrong stone in piling 2 at column b, say at (c,b)(c, b) , such that cac\not = a . Similarly, we must have a wrong stone in piling 1 at row c, say at (c,d)(c, d) where dbd \not = b . Clearly, making the move (a,b);(c,d)    (c,b);(a,d)(a,b);(c,d) \implies (c,b);(a,d) in piling 1 decreases the number of wrong stones in piling 1. Therefore, the number of wrong stones in piling 1 must eventually be 00 after a sequence of moves, so piling 1 and piling 2 are equivalent.
Lemma 3: Given the sequences gig_i and hih_i such that i=1ngi=i=1nhi=m\sum_{i=1}^n g_i=\sum_{i=1}^n h_i=m and gi,hi0ig_i, h_i\geq 0 \forall i , there is always a piling that satisfies ri=gir_i=g_i and ci=hic_i=h_i i\forall i .
Proof: We take the lowest ii , jj , such that gi,hj>0g_i, h_j >0 and place a stone at (i,j)(i, j) , then we subtract gig_i and hjh_j by 11 each, until gig_i and hih_i become 00 i\forall i , which will happen when mm stones are placed, because i=1ngi\sum_{i=1}^n g_i and i=1nhi\sum_{i=1}^n h_i are both initially mm and decrease by 11 after each stone is placed. Note that in this process ri+gir_i+g_i and ci+hic_i+h_i remains invariant, thus, the final piling satisfies the conditions above.
By the above lemmas, the number of ways to pile is simply the number of ways to choose the sequences rir_i and cic_i such that i=1nri=i=1nci=m\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m and ri,ci0ir_i, c_i \geq 0 \forall i . By stars and bars, the number of ways is (n+m1m)2\binom{n+m-1}{m}^{2} .
Solution by Shaddoll

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.