An $n\times n$ square ($n$ is a positive integer) consists of $n^2$ unit squares.A $\emph{monotonous path}$ in this square is a path of length $2n$ beginning in the left lower corner of the square,ending in its right upper corner and going along the sides of unit squares. For each $k$, $0\leq k\leq 2n-1$, let $S_k$ be the set of all the monotonous paths such that the number of unit squares lying below the path leaves remainder $k$ upon division by $2n-1$.Prove that all $S_k$ contain equal number of elements.
Problem
Source: Tuymaada 2021 Senior P4
Tags: counting problem, combinatorics
29.07.2021 04:15
by "left corner" do you mean "left down corner" or "left up corner"?
29.07.2021 14:54
gnoka wrote: by "left corner" do you mean "left down corner" or "left up corner"? I fixed it
29.07.2021 17:01
Are you sure about the statement? Because $\binom{2n}{n}$ is not necessarily divisible by $2n-1$. Edit: It is, I proved it. But writing $0\le k<2n-1$ seems more appropriate.
29.07.2021 17:06
I am writing the statement word for word from the original paper.The problem could be wrong,as the problems from this year were very poorly chosen.
29.07.2021 18:58
Sketch proof follows. Each path is equivalent to a choice of $n$ distinct integers $X\subset\{0,1,\ldots,2n-1\}$, representing the moves (counting 0-up) at which the path makes its vertical steps. The area under the path is easily seen to be a function of $n$ minus $\sum X$. So we need to prove the equidistribution property that random $n$-element subsets of $\{0,1,\ldots,2n-1\}$ have equally-likely sums modulo $2n-1$. A path/subset $X$ is either of "type 1" ($2n-1\in X$), or of "type 2" ($2n-1\notin X$). In fact we'll associate each path to the $n!$ vectors obtained by permuting the $n$ elements in the path; this obviously doesn't affect the equidistribution property we're looking for. From now on, it's vectors, not subsets. Consider just "type 2" vectors for the time being. The space of all $\tfrac{(2n-1)!}{(n-1)!}$ of these can be partitioned into collections of size $2n-1$ where in each collection the vectors differ only by multiples of $(1,1,\ldots,1)$. Each such multiple adds $n$ to the sum modulo $2n-1$; but since $\gcd(n,2n-1)=1$ and there are $2n-1$ multiples, that means each collection satisfies the equidistribution property. Thus "type 2" vectors are equidistributed. "Type 1" is equidistributed for similar reasons, relying this time on $\gcd(n-1,2n-1)=1\qquad\blacksquare$