Let $n$ be a positive integer. In a coordinate grid, a path from $(0,0)$ to $(2n,2n)$ consists of $4n$ consecutive unit steps $(1,0)$ or $(0,1)$. Prove that the number of paths that divide the square with vertices $(0,0),(2n,0),(2n,2n),(0,2n)$ into 2 regions with even areas is $$\frac{{4n \choose 2n} + {2n \choose n}}{2}$$
Problem
Source: BxMO 2024 P2
Tags: combinatorics
Tintarn
27.04.2024 16:11
What does "equal regions" mean? For $n=1$, it seems that only two of the six paths give equal regions (while four paths, which is the claimed result, give two regions both of even area).
beansenthusiast505
27.04.2024 16:17
*corrected it was supposed to be 2 regions of even area, also regions with area 0 are counted
Tintarn
27.04.2024 16:55
Nice problem!
Since there are $\binom{4n}{2n}$ paths in total, the claim is equivalent to saying that there are $\binom{2n}{n}$ more paths which separate the square in two even regions than those with two odd regions.
Clearly, there are exactly $\binom{2n}{n}$ paths with all straight segments being of even length, and they separate the square into two even regions.
So it suffices to consider those path with at least one odd segment and show that exactly half of them give two even regions.
But here we can just give an explicit bijection: For such a path with two even regions, we consider the last odd segment and swap the two steps at the start of this segment. This makes this segment even (possibly zero), but the next segment odd (and changes the area by one, hence changes its parity). By this observation, we can reconstruct the move uniquely from this result, and hence obtain a bijection as desired.
sami1618
29.04.2024 00:42
would be much harder if they did not give the answer