Problem:
Given a natural number . Define , and
for all natural numbers and , . How many ordered pairs of natural numbers are there for which is an odd number? (Dušan Đukić)
Problem:
Given a natural number . Define , and
for all natural numbers and , . How many ordered pairs of natural numbers are there for which is an odd number? (Dušan Đukić)
For let us denote . Since the remainder of upon division by 2 is equal to , the number of odd numbers among the numbers for and is equal to
It follows that the number of pairs for which is odd and is equal to .
It remains to show that for all sufficiently large . It is clear that the sequence is nonnegative and nonincreasing, so there exist and such that for all . This means that is even whenever . Suppose that and consider the smallest such that . By a simple induction we obtain for . However, if , this gives , contrary to the assumption.
Second solution (U. Dinić). Let us place tokens at the point in the coordinate plane. At each step, from each point we shall move the integer part of half of its tokens to the points and . Note that, if some row or column is nonempty at some moment, it will remain nonempty forever. Thus no token can leave the square , so the game ends after a finite number of steps.
It is not hard to see that after steps there are exactly tokens at the point . Moreover, the number is odd if after the next step exactly one token remains at the point . Since in the final position there are exactly tokens, it follows that among the terms of the sequence there are odd numbers.