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 "1982 IMO Problems/Problem 1"

(Created page with "==Problem== The function <math>f(n)</math> is defined on the positive integers and takes non-negative integer values. <math>f(2)=0,f(3)>0,f(9999)=3333</math> and for all <math...")
 
 
Line 44: Line 44:
  
  
−
== See Also == {{IMO box|year=1979|before=First Question|num-a=2}}
+
== See Also == {{IMO box|year=1982|before=First Question|num-a=2}}

Latest revision as of 22:17, 29 January 2021

Problem

The function $f(n)$ is defined on the positive integers and takes non-negative integer values. $f(2)=0,f(3)>0,f(9999)=3333$ and for all $m,n:$\[f(m+n)-f(m)-f(n)=0 \text{ or } 1.\]Determine $f(1982)$.

Solution 1

Clearly $f(1) \ge 1 \Rightarrow f(m+1) \ge f(m)+f(1) \ge f(m)+1$ so $f(9999) \ge 9999$.Contradiction!So $f(1)=0$.This forces $f(3)=1$.Hence $f(3k+3) \ge f(3k)+f(3)>f(3k)$ so the inequality $f(3)<f(6)<\cdots<f(9999)=3333$ forces $f(3k)=k \forall k \le 3333$.Now $f(3k+2) \ge k+1 \Rightarrow f(6k+4) \ge 2k+2 \Rightarrow f(12k+8) \ge 4k+4 \le f(12k+9)=4k+3$(Note:This is valid for $12k+9 \le 9999$ or $3k+2 \le 2499$).Contradiction!Hence the non-decreasing nature of $f$ gives $f(3k+1)=k$.Hence $f(n)=\lfloor\frac{n}{3}\rfloor \forall 1\le n \le 2499$.

So $f(1982)=\lfloor\frac{1982}{3}\rfloor=660$.

This solution was posted and copyrighted by sayantanchakraborty. The original thread for this problem can be found here: [1]

Solution 2

First observe that \[3333=f(9999)\geq f(9996)+f(3)\geq f(9993)+2f(3)\geq \cdots\geq 3333f(3)\]Since $f(3)$ is a positive integer, we need $f(3)=1$. Next, observe that \begin{align*} 3333=f(9999)\geq 5f(1980)+33f(3)=5f(1980)+33\quad\Longrightarrow\quad f(1980)\leq 660 \end{align*}On the other hand, $f(1980)\geq 660f(3)=660$, so combine the two inequalities we obtain $f(1980)=660$. Finally, write \[f(1982)=f(1980)+f(2)+0\vee 1=660\vee 661\]Suppose that $f(1982)=661$, then \begin{align*} 3333=f(9999)\geq 5f(1982)+29f(3)=3305+29=3334 \end{align*}a contradiction. Hence we conclude that $f(1982)=660$.

This solution was posted and copyrighted by Solumilkyu. The original thread for this problem can be found here: [2]

Solution 3

We show that $f(n) = [n/3]$ for $n <= 9999$, where [ ] denotes the integral part. We show first that $f(3) = 1$. $f(1)$ must be $0$, otherwise $f(2) - f(1) - f(1)$ would be negative. Hence $f(3) = f(2) + f(1) + 0$ or $1$ = $0$ or $1$. But we are told $f(3) > 0$, so $f(3) = 1$. It follows by induction that $f(3n) >= n$. For $f(3n+3) = f(3) + f(3n)$ + $0$ or $1 = f(3n) + 1$ or $2$. Moreover if we ever get $f(3n) > n$, then the same argument shows that $f(3m) > m$ for all $m > n$. But $f(3.3333) = 3333$, so $f(3n) = n$ for all $n <= 3333$. Now $f(3n+1) = f(3n) + f(1) + 0$ or $1$ = $n$ or $n + 1$. But $3n+1 = f(9n+3) >= f(6n+2) + f(3n+1) >= 3f(3n+1)$, so $f(3n+1) < n+1$. Hence $f(3n+1) = n.$ Similarly, $4f(3n+2) = n$. In particular $f(1982) = 660$.

This solution was posted and copyrighted by Tega. The original thread for this problem can be found here: [3]

Solution 4

Similar to solution 3.

Proof: Lemma 1: $f(mn)\geq nf(m)$ Let, $P(m,m)$ be assertion. \[f(2m) \geq 2f(m)\]Similarly,we can induct to get $f(nm)\geq nf(m)$. \[f(3m) \geq f(2m)+f(m) \geq 3f(m)\implies f(nm)\geq \underbrace{f(m(n-1))+f(m)\geq .....}_{\text{n times}}\geq nf(m)\]Lemma proved.

Then we see that, \[f(9999)\geq 3333f(3) \implies f(3)=1:f(3)>0\]Then, \[f(9999) \geq 5f(1980)+33f(3) \implies 3300 \geq 5f(1980) \implies f(1980) \leq 660\]\[f(1980) \geq 660f(3) \implies f(1980)=660\]Then we can easily get,by assertion $P(1980,2)$ \[f(1982)=660 \space or \space f(1980)=661\]Hence, $\boxed{f(1980)=660,661}$.And, we are done. $\blacksquare$

This solution was posted and copyrighted by IMO2019. The original thread for this problem can be found here: [4]


See Also

1982 IMO (Problems) • Resources
Preceded by
First Question 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 2
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1982_IMO_Problems/Problem_1&oldid=144001"