Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1990 OIM Problems/Problem 1"
 
(One intermediate revision by the same user not shown)
Line 14: Line 14:
  
 
== Solution ==
 
== 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>
 +
 
 +
In that range, this gives <math>f(2^j+b)=-(b+1)</math>
 +
 
 +
When <math>n=2^j-1</math>, <math>f(n)+n=f(2^j-1)+2^j-1=0+2^j-1=2^k-1</math> which proves the equality since <math>j=k</math>.
 +
 
 +
When <math>n \ne 2^j-1</math>, <math>f(n)+n=f(2^j+b)+2^j+b=-(b+1)+2^j+b=2^j-1=2^k-1</math> which also proves the equality since <math>j=k</math>.
 +
 
 +
'''Part b.'''
 +
 
 +
<math>f(2^{1990})=f(2^{1990}-1)-1=0-1=-1</math>
 +
 
 +
* This seems to be one of the easiest problems I've seen in these types of competitions, unless I'm missing something.
 +
 
 +
~Tomas Diaz. orders@tomasdiaz.com
 +
 
 +
{{Alternate solutions}}
  
 
== See also ==
 
== See also ==
 
https://www.oma.org.ar/enunciados/ibe5.htm
 
https://www.oma.org.ar/enunciados/ibe5.htm

Latest revision as of 00:21, 23 December 2023

Problem

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

Solution

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$

In that range, this gives $f(2^j+b)=-(b+1)$

When $n=2^j-1$, $f(n)+n=f(2^j-1)+2^j-1=0+2^j-1=2^k-1$ which proves the equality since $j=k$.

When $n \ne 2^j-1$, $f(n)+n=f(2^j+b)+2^j+b=-(b+1)+2^j+b=2^j-1=2^k-1$ which also proves the equality since $j=k$.

Part b.

$f(2^{1990})=f(2^{1990}-1)-1=0-1=-1$

  • This seems to be one of the easiest problems I've seen in these types of competitions, unless I'm missing something.

~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.

See also

https://www.oma.org.ar/enunciados/ibe5.htm

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1990_OIM_Problems/Problem_1&oldid=208185"