A rabbit initially stands at the position $0$, and repeatedly jumps on the real line. In each jump, the rabbit can jump to any position corresponds to an integer but it cannot stand still. Let $N(a)$ be the number of ways to jump with a total distance of $2019$ and stop at the position $a$. Determine all integers $a$ such that $N(a)$ is odd.
Problem
Source: 2019 Thailand Mathematical Olympiad P4
Tags: combinatorics
MarkBcc168
22.05.2019 13:58
Solution 1 (Generating Function, MarkBcc168): Consider the quantity
$$T = (x+x^2+x^3+...)+(y+y^2+y^3+...) = \frac{x}{1-x}+\frac{y}{1-y}$$and define generating functions
$$F(x,y) = 1+T+T^2+...$$It's clear that the coefficient of $x^ay^b$ in $F$ equals to the number of ways to jump with a total distance of $a+b$ and arrive at position $a-b$. (i.e. variable $x$ corresponds to positive jumps and variable $y$ corresponds to negative jumps).
Now we evaluate $F(x,y)$ in $\pmod 2$. To do this, let $G(x,y) = 1-T+T^2-T^3+...$ so that $G\equiv F\pmod 2$ and
$$G(x,y) = \frac{1}{1+T} = \frac{1}{1+\frac{x}{1-x}+\frac{y}{1-y}} = \frac{(1-x)(1-y)}{1-xy}$$Thus, we have
$$G(x,y) = (1-x-y+xy)(1+(xy)+(xy)^2+(xy)^3+...)$$It's clear that all odd coefficients are in form $x^ny^{n+1}$ and $x^{n+1}y^n$, which corresponds to $N(1)$ and $N(-1)$. Thus the answer is $\boxed{\{1,-1\}}$.
Solution 2 (Combinatorial, Official): Encode each positive jump by the corresponding number of $\texttt{+}$ and encode each negative jump by the corresponding number of $\texttt{-}$. We also seperate each jump by $\texttt{|}$. For instance,
$$\texttt{++|+++|---}\implies 0\stackrel{+2}{\longrightarrow} 2\stackrel{+3}{\longrightarrow} 5\stackrel{-3}{\longrightarrow} 2.$$Clearly, in $N(a)$, we must have $\frac{2019+a}{2}$ $\texttt{+}$'s and $\frac{2019-a}{2}$ $\texttt{-}$'s. We also note that a $\texttt{|}$ must be inserted between $\texttt{+-}$.
Now, fix a sequence consisting many $\texttt{+}$ and $\texttt{-}$. Call a sequence \emph{bad} if and only if there are odd number of ways to insert $\texttt{|}$.
Claim: The only bad sequences are $\texttt{+-+-+...+}$ and $\texttt{-+-+-...-}$.
Proof: If $m,n$ denote the number of consecutive $\texttt{++}$ and $\texttt{--}$ respectively. Then clearly the number of ways to insert $\texttt{|}$ is precisely $2^{m+n}$. Thus the sequence is bad if and only if there are no $\texttt{++}$ and $\texttt{--}$ at all so we are done.
The two bad sequences correspond to $N(1)$ and $N(-1)$ thus the answer is $\{1,-1\}$.
Pathological
23.05.2019 01:31
Alternatively, we could let $N(a, b)$ be the number of ways to jump a total distance of $a$ forwards and $b$ backwards. Then, it's clear that $N(0, 0) = 1$ and $N(a, b) = N(a-1, b) + N(a-2, b) + \cdots + N(0, b) + N(a,b -1) + N(a, b-2) + \cdots + N(a, 0)$ when $a+b \ge 1$ (use casework on what the first jump is). If we take this recursion mod $2$, it's easy to show by induction that $N(a, b)$ is odd if and only if $a = b = 0$ or $|a-b| = 1.$ This immediately implies that in our problem, since only $N(1008, 1009)$ and $N(1009, 1008)$ are odd, we have that our answers are $\{1008 - 1009, 1009 - 1008\} = \{-1, 1\}.$