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 "2005 Indonesia MO Problems/Problem 5"

(Solution to Problem 5 -- induction rules)
 
(→‎See Also)
 
Line 61: Line 61:
 
<br>
 
<br>
 
Therefore, there is only one integer that satisfies the original equation.
 
Therefore, there is only one integer that satisfies the original equation.
 +
 +
==Solution 2==
 +
 +
Using Quotient-Remainder Theorem, let <math>m = 2005q+r</math>, where <math>q</math>, <math>r</math>, are integers and <math>0\le r< 2005</math>
 +
 +
Since <math>m - \lfloor \frac{m}{2005}\rfloor =2005</math>, <math>2005q+r- \lfloor \frac{2005q+r}{2005}\rfloor = 2005</math>.
 +
 +
This simplifies down to
 +
 +
\begin{align*}
 +
2005q+r-q&=2005\\
 +
2004q+r&=2005\\
 +
r&=2005-2004q
 +
\end{align*}
 +
 +
If <math>q\le 0</math>, then <math>r\ge 2005</math>, which violates the restriction that <math>0\le r<2005</math>.
 +
If <math>q\ge 2</math>, then <math>r< 0</math>, which again violates the restriction that <math>0\le r<2005</math>.
 +
 +
Thus, the only possible value for q is 1, and <math>r=2005-2004(1)=1</math>.
 +
 +
Solving for <math>m</math> gives <math>m = 2005q+r = 2006</math> as our only answer
  
 
==See Also==
 
==See Also==

Latest revision as of 23:40, 13 September 2024

Problem

For an arbitrary real number $x$, $\lfloor x\rfloor$ denotes the greatest integer not exceeding $x$. Prove that there is exactly one integer $m$ which satisfy $m-\left\lfloor \frac{m}{2005}\right\rfloor=2005$.

Solution

First we will show that $m = 2006$ is a solution. Then we will show that there are no other integers that are a solution.


To find the solution, note that the absolute value of $\left\lfloor \frac{m}{2005}\right\rfloor$ is usually smaller than $m$, so $m$ should be close to $2005$. Plugging in $m = 2005$ results in $m-\left\lfloor \frac{m}{2005}\right\rfloor = 2004$. Trying out $m = 2006$ results in $m-\left\lfloor \frac{m}{2005}\right\rfloor = 2005$, so that value is a solution.


To show that there are no other integers that are a solution, we will consider two cases: one where $m$ is less than $2006$ and one where $m$ is greater than $2006$.


Case 1: $m < 2006$

The highest integer $m$ that meets the conditions is $2005$, and in that condition, $m-\left\lfloor \frac{m}{2005}\right\rfloor=2004$.


Assume that $m - \left \lfloor \frac{m}{2005} \right \rfloor < 2005$. Let $m = 2005a + b$, where $a,b$ are integers and $b$ is less than $2005$.


If $b = 0$, then $m-\left\lfloor \frac{m}{2005}\right\rfloor = 2005a - \left\lfloor \frac{2005a}{2005}\right\rfloor = 2004a$. Additionally, \begin{align*} m-1-\left\lfloor \frac{m-1}{2005}\right\rfloor &= 2005a - 1 - \left\lfloor \frac{2005a - 1}{2005}\right\rfloor \\ &= 2005a - 1 - \left\lfloor \frac{2005(a-1) + 2004}{2005} \right\rfloor \\ &= 2005a - 1 - a + 1 \\ &= 2004a. \end{align*} If $b > 0$, then $m-\left\lfloor \frac{m}{2005}\right\rfloor = 2005a + b - \left\lfloor \frac{2005a+b}{2005}\right\rfloor = 2004a + b$. Additionally, \begin{align*} m-1-\left\lfloor \frac{m-1}{2005}\right\rfloor &= 2005a + b - 1 - \left\lfloor \frac{2005a + b - 1}{2005}\right\rfloor \\ &= 2005a + b - 1 - a \\ &= 2004a + b - 1. \end{align*} For both cases, $m-1-\left\lfloor \frac{m-1}{2005}\right\rfloor \le m-\left\lfloor \frac{m}{2005}\right\rfloor$, so by induction, there are no integers less than $2006$ that satisfy the equation.

Case 2: $m > 2006$

The lowest integer $m$ that meets the conditions is $2007$, and in that condition, $m-\left\lfloor \frac{m}{2005}\right\rfloor=2006$.


Assume that $m - \left \lfloor \frac{m}{2005} \right \rfloor > 2005$. Once again, let $m = 2005a + b$, where $a,b$ are integers and $b$ is less than $2005$.


If $b = 2004$, then $m-\left\lfloor \frac{m}{2005}\right\rfloor = 2005a + 2004 - \left\lfloor \frac{2005a+2004}{2005}\right\rfloor = 2004a + 2004$. Additionally, \begin{align*} m+1-\left\lfloor \frac{m+1}{2005}\right\rfloor &= 2005a + 2005 - \left\lfloor \frac{2005a +2005}{2005}\right\rfloor \\ &= 2005a + 2005 - a - 1 \\ &= 2004a + 2004 \end{align*} If $b < 2004$, then $m-\left\lfloor \frac{m}{2005}\right\rfloor = 2005a + b - \left\lfloor \frac{2005a+b}{2005}\right\rfloor = 2004a + b$. Additionally, \begin{align*} m+1-\left\lfloor \frac{m+1}{2005}\right\rfloor &= 2005a + b + 1 - \left\lfloor \frac{2005a + b + 1}{2005}\right\rfloor \\ &= 2005a + b + 1 - a \\ &= 2004a + b + 1 \end{align*} For both cases, $m+1-\left\lfloor \frac{m+1}{2005}\right\rfloor \ge m-\left\lfloor \frac{m}{2005}\right\rfloor$, so by induction, there are no integers greater than $2006$ that satisfy the equation.


Therefore, there is only one integer that satisfies the original equation.

Solution 2

Using Quotient-Remainder Theorem, let $m = 2005q+r$, where $q$, $r$, are integers and $0\le r< 2005$

Since $m - \lfloor \frac{m}{2005}\rfloor =2005$, $2005q+r- \lfloor \frac{2005q+r}{2005}\rfloor = 2005$.

This simplifies down to

\begin{align*} 2005q+r-q&=2005\\ 2004q+r&=2005\\ r&=2005-2004q \end{align*}

If $q\le 0$, then $r\ge 2005$, which violates the restriction that $0\le r<2005$. If $q\ge 2$, then $r< 0$, which again violates the restriction that $0\le r<2005$.

Thus, the only possible value for q is 1, and $r=2005-2004(1)=1$.

Solving for $m$ gives $m = 2005q+r = 2006$ as our only answer

See Also

2005 Indonesia MO (Problems)
Preceded by
Problem 4 		1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 Followed by
Problem 6
All Indonesia MO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2005_Indonesia_MO_Problems/Problem_5&oldid=227148"