Square $ABCD$ is divided into $n^2$ equal small squares by lines parallel to its sides.A spider starts from $A$ and moving only rightward or upwards,tries to reach $C$.Every "movement" of the spider consists of $k$ steps rightward and $m$ steps upwards or $m$ steps rightward and $k$ steps upwards(it can follow any possible order for the steps of each "movement").The spider completes $l$ "movements" and afterwards it moves without limitation (it still moves rightwards and upwards only).If $n=m\cdot l$,find the number of the possible paths the spider can follow to reach $C$.Note that $n,m,k,l\in \mathbb{N^{*}}$ with $k<m$.
Problem
Source: Greek TST 2014-Pr.4
Tags: binomial coefficients, combinatorics unsolved, combinatorics
JBL
16.08.2014 07:47
What sort of answer is expected? It's easy to write down the answer as a sum involving binomial coefficients, but I doubt very much the sum can be evaluated in general.
john111111
16.08.2014 12:56
Hello, during the contest the contestants were informed to present the answer in their proof as a sum,so you are probably right.
JBL
16.08.2014 17:38
In that case, the spider chooses a path as follows: first, the spider picks a value of $a$ in $[0,\ell]$. Then the spider chooses one of the $\binom{\ell}{a}$ ways to make $a$ moves of the form $(m,k)$ and $\ell-a$ of the form $(k,m)$. Finally, the spider finds itself with $\ell(m-k)$ remaining steps to make, of which $a(m-k)$ must be up. Thus, the answer is $\sum_a \binom{\ell}{a}\binom{\ell(m-k)}{a(m-k)}$. This sum is easy to evaluate when $d:=m-k=0,1$ but already at 2 I don't think there is a nice closed form. (It is also the coefficient of $x^{d\ell}$ in $(1+x^d)^\ell(1+x)^{d\ell}$, and probably can be rewritten lots of other ways, too.)
gavrilos
16.08.2014 21:08
Right.However there is a mistake,probably due to my incomplete descritpion of the problem.I didn't mention that the spider can follow any possible order for the $m+k$ steps of each of the $l$ "movements". Consequently the result is what you have found multiplied by $\binom{m+k}{m}^l$. Excuse me for forgeting to provide this information.I will edit my initial post.