4
$\begingroup$

Given a $12\times12$ grid with a hole of $4\times4$ in its middle, how many short paths (right or up only) are there from $(0,0)$ to $(12,12)$.

I tried using inclusion-exclusion by counting the number of paths that go through at least one point inside the hole, then count the paths that go through at least 2 points in the hole etc. but so far I got lost. Would appreciate any (perhaps simpler) suggestions to try solve this.

Thanks

$\endgroup$
2
  • 3
    $\begingroup$ Is this a $12\times12$ grid or a $13\times13$ grid? If the latter, which lattice points are disallowed? $\endgroup$ – almagest May 10 '16 at 16:20
  • $\begingroup$ (0,0) is the bottom left corner and (12,12) is the top right. Disallowed are the 3*3 points inside the (4,4) (8,8) square. $\endgroup$ – Ron May 10 '16 at 16:44
2
$\begingroup$

Possible hint: the path must go through exactly one of the points on the diagonal line joining the top left to the lower right corner of the grid. Count those for the points not in the hole.

$\endgroup$
3
  • $\begingroup$ But couldn't the path go through more than exactly one of the points on the diagonal line joining the corners of the grid (any path starting with up right up right for ex.)? $\endgroup$ – Ron May 10 '16 at 16:41
  • $\begingroup$ @Ron I mean the other diagonal. I will edit my answer. $\endgroup$ – Ethan Bolker May 10 '16 at 16:47
  • $\begingroup$ Oh, I think I got it! so I take 2n choose n then I subtract the sum of the possibilities to go through each of the 3 central points on that diagonal. $\endgroup$ – Ron May 10 '16 at 16:57
0
$\begingroup$

We need a way of grouping the paths into disjoint sets. Let $N_i$ be the number through the point $(i,12-i)$ for $i=0,1,2,3,4,8,9,10,11,12$.

We have $N_i={12\choose i}^2$, so the total number of paths is $2\left({12\choose0}^2+{12\choose1}^2+{12\choose2}^2+{12\choose3}^2+{12\choose4}^2\right)=595852$.

$\endgroup$
3
  • $\begingroup$ I do not completely understand the formula for your term $N_i$. For each $i, i=0,1,2,3,4$ you draw $i$ '$x$'-coordinates for an 'up' movement from a universe of $13-(4-i)$. Therefore I would expect $N_i = {9+i \choose i}^2$ to hold. Could you be so kind to explain? (any coordinate set for a given $i$ determines the path; I do follow your reasoning for the square and the doubling due to the problem symmetries). $\endgroup$ – collapsar May 10 '16 at 18:43
  • $\begingroup$ For any given $i$ we have to traverse two rectangles one after the other. Each is $i\times(12-i)$. So for each one we have 12 moves, $i$ of which are in one direction, the remainder in the other. To take the simplest case: for $i=0$, we have to make 12 vertical moves (1 possibility) followed by 12 horizontal moves (1 possiblity), total $1^2$ possibilities. $\endgroup$ – almagest May 10 '16 at 18:49
  • $\begingroup$ Got the error in my reasoning (drawing without repetition while in fact the '$x$'-coordinates for the up move may repeat). thank you. $\endgroup$ – collapsar May 10 '16 at 19:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.