Difference between revisions of "1990 OIM Problems/Problem 1"
(Created page with "== Problem == Let <math>f</math> be a function defined in the set of integers greater or equal to zero such that: (i) If <math>n=2^j-1</math>, for all <math>n=0, 1, 2, \cdots...") |
|||
| (2 intermediate revisions by the same user not shown) | |||
| Line 9: | Line 9: | ||
<cmath>f(n)+n=2^k-1</cmath> | <cmath>f(n)+n=2^k-1</cmath> | ||
| − | b. Calculate <math>f(2^1990)</math>. | + | b. Calculate <math>f(2^{1990})</math>. |
~translated into English by Tomas Diaz. ~orders@tomasdiaz.com | ~translated into English by Tomas Diaz. ~orders@tomasdiaz.com | ||
== 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 
be a function defined in the set of integers greater or equal to zero such that:
(i) If 
, for all 
then 
(ii) If 
, for all then 
a. Prove that for all integer 
, greater or equal to zero, there exist an integer 
grater than zero such that
![\[f(n)+n=2^k-1\]](http://latex.artofproblemsolving.com/e/3/4/e343172b4175bc61591e8fc2ab0e4a43b4d36323.png)
b. Calculate 
.
~translated into English by Tomas Diaz. ~orders@tomasdiaz.com
Solution
Part a.
, 
, 
, and so on..
So we pick a range where 
which is 
where 
is a non-negative integer.
Therefore, 
which provides the range for as: 
In that range, this gives 
When , 
which proves the equality since 
.
When , 
which also proves the equality since .
Part b.
- 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.
