まず、左上と右下を以下のように埋めます。

0000X
000X1
00X11
0X111
X1111

そして、X の部分に \(0,1\) を交互に入れると条件を満たします。証明として、「\(0\) になった \(X\) から左上のどこかへのパスの個数の和」と「\(1\) になった \(X\) から右下のどこかへのパスの個数の和」が等しいことが言えればよいです。

\(1\) 回も動かないことを許容すると、マス \((i,N-i+1)\) から右下のどこかへのパスの個数は \(\sum_{a=0}^{i-1} \sum_{b=0}^{N-i} \binom{a+b}{a}\) となります。「\(0,1\) を \(i-1,N-i\) 個以下選んで並び替える方法の個数は？」という問題になりますが、この問題の答えは「\(0,1\) を \(i,N-i+1\) 個好きに並べてから同じ値からなるブロックを後ろから \(2\) 個取り除く」という対応によって \(\binom{N+1}{i} - 1\) であることが分かります。(\(-1\) は 000011 と 110000 の区別がつかないことを考慮した分です。)

よって、\(1\) 回も動かないパスを除くことでマス \((i,N-i+1)\)から右下のどこかへのパスの個数は \(\binom{N+1}{i} - 2\) となります。また、\((i,N-i+1)\) から左上のどこかへのパスの個数もこの値に等しいです。

\(f(0) = f(1)\) を示します。\(N\) が偶数の時は自明なので、\(N\) が奇数の時を考えます。基本的には \(\binom{N+1}{i}\) の \(i\) が偶数、奇数の部分を分け合っているため値が等しくなります。\(i=0,N+1\) の部分がないため偶数側が \(2\) 少なくなり、その後、\(-2\) 部分が奇数の方が \(1\) 回多く引かれるため結局打ち消しあい \(f(0) = f(1)\) が証明出来ました。