Difference between revisions of "1990 OIM Problems/Problem 1"

Revision as of 01:14, 23 December 2023

Let $f$ be a function defined in the set of integers greater or equal to zero such that:

(i) If $n=2^j-1$ , for all $n=0, 1, 2, \cdots,$ then $f(n)=0$

(ii) If $n \ne 2^j-1$ , for all $n=0, 1, 2, \cdots,$ then $f(n+1)=f(n)-1$

a. Prove that for all integer $n$ , greater or equal to zero, there exist an integer $k$ grater than zero such that $f(n)+n=2^k-1$

b. Calculate $f(2^{1990})$ .

~translated into English by Tomas Diaz. ~orders@tomasdiaz.com

Part a.

$f(2^j-1)=0$ , $f(2^j)=-1$ , $f(2^j+1)=-2$ , and so on..

So we pick a range where $f(n)\ne 0$ which is $2^j-1<2^j+b<2^{j+1}-1$ where $b$ is a non-negative integer.

Therefore, $2^j\le2^j+b\le2^{j+1}-2$ which provides the range for $b$ as: $0\le b \le 2^{j+1}-2-2^j$

~Tomas Diaz. orders@tomasdiaz.com

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

@@ Line 14: / Line 14: @@
 == Solution ==
-{{solution}}
+'''Part a.'''
+<math>f(2^j-1)=0</math>, <math>f(2^j)=-1</math>, <math>f(2^j+1)=-2</math>, and so on..
+So we pick a range where <math>f(n)\ne 0</math> which is  <math>2^j-1<2^j+b<2^{j+1}-1</math> where <math>b</math> is a non-negative integer.
+Therefore, <math>2^j\le2^j+b\le2^{j+1}-2</math> which provides the range for <math>b</math> as: <math>0\le b \le 2^{j+1}-2-2^j</math>
+~Tomas Diaz. orders@tomasdiaz.com
+{{Alternate solutions}}
 == See also ==
 https://www.oma.org.ar/enunciados/ibe5.htm