Maths Olympiad Prep

Library / /57 of 87

Combinatorics Difficulty 6.7 National Olympiad Prove it Serbia

Problem:

Given a natural number nn. Define f(0,j)=f(i,0)=0f(0, j)=f(i, 0)=0, f(1,1)=nf(1,1)=n and
f(i,j)=f(i1,j)2+f(i,j1)2 f(i, j)=\left\lfloor\frac{f(i-1, j)}{2}\right\rfloor+\left\lfloor\frac{f(i, j-1)}{2}\right\rfloor
for all natural numbers ii and jj, (i,j)(1,1)(i, j) \neq (1,1). How many ordered pairs of natural numbers (i,j)(i, j) are there for which f(i,j)f(i, j) is an odd number? (Dušan Đukić)

Solutions — 2

Solution 1

For m2m \geqslant 2 let us denote sm=i+j=mf(i,j)s_{m}=\sum_{i+j=m} f(i, j). Since the remainder of f(i,j)f(i, j) upon division by 2 is equal to f(i,j)2[f(i,j)2]f(i, j)-2\left[\frac{f(i, j)}{2}\right], the number of odd numbers among the numbers f(i,j)f(i, j) for i,j0i, j \geqslant 0 and i+j=mi+j=m is equal to
i+j=m(f(i,j)2[f(i,j)2])=smi+j=m([f(i1,j+1)2]+[f(i,j)2])=smsm+1 \begin{aligned} \sum_{i+j=m}\left(f(i, j)-2\left[\frac{f(i, j)}{2}\right]\right) & =s_{m}-\sum_{i+j=m}\left(\left[\frac{f(i-1, j+1)}{2}\right]+\left[\frac{f(i, j)}{2}\right]\right) \\ & =s_{m}-s_{m+1} \end{aligned}
It follows that the number of pairs (i,j)(i, j) for which f(i,j)f(i, j) is odd and i+j<mi+j<m is equal to s2sm=nsms_{2}-s_{m}=n-s_{m}.
It remains to show that sm=0s_{m}=0 for all sufficiently large mm. It is clear that the sequence sms_{m} is nonnegative and nonincreasing, so there exist NN and kk such that sm=ks_{m}=k for all mNm \geqslant N. This means that f(i,j)f(i, j) is even whenever i+jmi+j \geqslant m. Suppose that k>0k>0 and consider the smallest ii such that f(i,mi)>0f(i, m-i)>0. By a simple induction we obtain f(i,m+ri)=[f(i,mi)2r]f(i, m+r-i)=\left[\frac{f(i, m-i)}{2^{r}}\right] for r1r \geqslant 1. However, if 2rf(i,mi)<2r+12^{r} \leqslant f(i, m-i)<2^{r+1}, this gives f(i,m+ri)=1f(i, m+r-i)=1, contrary to the assumption.

Solution 2

Second solution (U. Dinić). Let us place nn tokens at the point (1,1)(1,1) in the coordinate plane. At each step, from each point (i,j)(i, j) we shall move the integer part of half of its tokens to the points (i+1,j)(i+1, j) and (i,j+1)(i, j+1). Note that, if some row or column is nonempty at some moment, it will remain nonempty forever. Thus no token can leave the square [1,n]×[1,n][1, n] \times [1, n], so the game ends after a finite number of steps.
It is not hard to see that after i+j2i+j-2 steps there are exactly f(i,j)f(i, j) tokens at the point (i,j)(i, j). Moreover, the number f(i,j)f(i, j) is odd if after the next step exactly one token remains at the point (i,j)(i, j). Since in the final position there are exactly nn tokens, it follows that among the terms of the sequence f(i,j)f(i, j) there are nn odd numbers.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from sr; metadata (topic, difficulty) added by this project.