Let $n $ be a positive integer. Let $f $ be a function from nonnegative integers to themselves. Let $f (0,i)=f (i,0)=0$, $f (1, 1)=n $, and $ f(i, j)= [\frac {f(i-1,j)}{2}]+ [\frac {f(i, j-1)}{2}] $ for positive integers $i, j$ such that $i*j>1$. Find the number of pairs $(i,j) $ such that $f (i, j) $ is an odd number.( $[x]$ is the floor function).
Problem
Source: Serbia National Olympiad 2016 P2
Tags: algebra, combinatorics, function, floor function
mysterious_benedict
01.04.2016 17:43
What is $j$?
aleksam
01.04.2016 17:48
A positive integer...
mysterious_benedict
01.04.2016 17:49
Oh! Thank you!
aleksam
04.04.2016 00:01
Beautiful solution (credits to Uros Dinic): Let's put $n$ objects in point $(1, 1)$, in the coordinate plane. In every second, from every point move half of objects up, half right, and if the number of objects in the point was odd, we leave one object in that point. It's easy to see why by this process we get in every point in some moment $f (i, j) $ objects, and we leave there an object iff $f (i, j) $ was odd. So, as on object can go to infinity, we had $n $ objects left somewhere in coordinate plane, so there are exactly $n $ points in which $f (i, j) $ was odd.
Aiscrim
10.01.2017 14:14
Although the previous solution is clearly more beautiful, I think that my solution is easier to find once you play with small numbers. The intuition is that the difference between the sums of two consecutive diagonals (from top-left to low-right) gives you the number of odd entries from one diagonal. To formalize, let $g(k)$ be the sum of the numbers from diagonal $k$: $$g(k)= f(k,0)+f(k-1,1)+f(k-2,2)+....+f(1,k-1)+f(0,k)$$Note that $g(k+1)=f(k+1,0)+f(0,k+1)+\displaystyle\sum\limits_{i=1}^{k} f(k+1-i,i)=\displaystyle\sum\limits_{i=1}^{k} \left ( \left \lfloor \dfrac{f(k-i,i)}{2} \right \rfloor +\left \lfloor \dfrac{f(k+1-i,i-1)}{2} \right \rfloor \right )$ so $$g(k+1)=\displaystyle\sum\limits_{i=1}^{k-1} 2 \left \lfloor \dfrac{f(k-i,i)}{2} \right \rfloor$$As $x=2\left \lfloor \dfrac{x}{2} \right \rfloor+\delta_x$, where $\delta_x=0$ if $x$ is even and $\delta_x=1$ otherwise, we infer that $g(k)-g(k+1)$ gives the number of odd integers from diagonal $k$.
$\left (g(k) \right )_{k\ge 1}$ is a decreasing sequence of nonnegative integers, hence it eventually is constant. This implies that there exists an integer $t$ such that $g(t)=g(t+1)=g(t+2)=...$ which means that there is no odd entry on column $k$ when $k\ge t$. If $h(k)=\displaystyle\sum\limits_{i=1}^{k-1} f(k-i,i)^2$, it is trivial to check that $h(k+1)<h(k)$ for $k\ge t$, so we eventually reach a diagonal full of zeroes.
, say $g(p)=0$. Clearly, $g(k)=0,\ \forall k\ge p$. Therefore, the total number of odd integers is $$\left (g(1)-g(2) \right )+(g(2)-g(3))+...+(g(p-1)-g(p))=g(1)-g(p)=f(1,1)=n$$