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 "1994 OIM Problems/Problem 1"

(Created page with "== Problem == A natural number <math>n</math> is said to be "''sensible''" if there exists an integer <math>r</math>, with <math>1<r<n-1</math>, such that the representation o...")
 
Line 7: Line 7:
  
 
== Solution ==
 
== Solution ==
−
{{solution}}
+
Lemma:
 +
Every number that can be expressed as
 +
<cmath>  b \cdot \frac{r^d-1}{r-1} , b < r </cmath>
 +
Is a "''sensible''" number as it can be expressed as <math>b\cdots b _ r</math>, where there are <math>d</math> <math>r’s</math>
  
 +
Part <math>1:</math> Let us prove that <math>1993</math> cannot be expressed as such.
 +
Notice that <math>1993</math> is a prime, which means that <math>b = 1</math> as it cannot be <math>1993</math> or else <math>r > 1994</math>.
 +
Therefore, we need to prove that there does not exist <math>d,r</math> such that
 +
<cmath> \frac{r^d-1}{r-1} =1993 </cmath>
 +
Assume on the contrary, there exists such <math>d,r</math>. Then we have
 +
<cmath> r^d - 1 = 1993r - 1993 \implies r^d = 1993r - 1992</cmath>
 +
Notice that taking mod<math>(r)</math> results in <math> r \mid 1992</math>.
 +
Notice plugging in some small values, <math>r = 2,3,4,6,8,12,24</math>, they don’t work
 +
<math>1992 \cdot 2 - 1992 = 1994 \neq 2^d</math>
 +
And similarly.
 +
So the next smallest value of <math>r</math> is <math>83</math>, implying that <math>d < 3</math> because
 +
<cmath>\text{when} \hspace{0.2cm} r \geq 45, r^3 > 1993r -1992</cmath>
 +
As <math>r^3</math> grows faster than <math>1992r</math> when <math>r > \sqrt{1992} \implies r \geq 45</math> and when <math>r = 45, 45^3 = 91125 > 87693 = 1993 \cdot 45 - 1992</math>
 +
 +
So <math>d = 1,2</math>
 +
 +
If <math>d = 1,</math> then <math>1992(r-1) = 0 \implies r = 1</math>, which is not true because <math>r>1</math>.
 +
If <math>d = 2,</math> then <math>(r-1)(r-1992) = 0 \implies r = 1,1992</math>, which is not true because <math>1<r<1992</math>
 +
So there is no solution.
 +
 +
Part <math>2: </math> Let us show that <math>1994</math> is sensible.
 +
<math>1994 = 2 \cdot 997 = 2\cdot (996 + 1) = 22_{996}</math>
 +
 +
Comment: any composite number other than <math>p^2</math>, where <math>p</math> is a prime is sensible as <math>n \cdot r = n \cdot (1 + (r-1)) = nn_{r-1}</math>
 +
E.g <math>69 = 3\cdot 23 = 33_{22}</math>
 +
~Archieguan
 
== See also ==
 
== See also ==
 
https://www.oma.org.ar/enunciados/ibe9.htm
 
https://www.oma.org.ar/enunciados/ibe9.htm

Revision as of 21:29, 22 October 2024

Problem

A natural number $n$ is said to be "sensible" if there exists an integer $r$, with $1<r<n-1$, such that the representation of $n$ in base $r$ has all its digits equal. For example, 62 and 15 are "sensible", since 62 is 222 in base 5 and 15 is 33 in base 4.

Prove that 1993 is NOT "sensible" but 1994 is.

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

Solution

Lemma: Every number that can be expressed as \[b \cdot \frac{r^d-1}{r-1} , b < r\] Is a "sensible" number as it can be expressed as $b\cdots b _ r$, where there are $d$ $r’s$

Part $1:$ Let us prove that $1993$ cannot be expressed as such. Notice that $1993$ is a prime, which means that $b = 1$ as it cannot be $1993$ or else $r > 1994$. Therefore, we need to prove that there does not exist $d,r$ such that \[\frac{r^d-1}{r-1} =1993\] Assume on the contrary, there exists such $d,r$. Then we have \[r^d - 1 = 1993r - 1993 \implies r^d = 1993r - 1992\] Notice that taking mod$(r)$ results in $r \mid 1992$. Notice plugging in some small values, $r = 2,3,4,6,8,12,24$, they don’t work $1992 \cdot 2 - 1992 = 1994 \neq 2^d$ And similarly. So the next smallest value of $r$ is $83$, implying that $d < 3$ because \[\text{when} \hspace{0.2cm} r \geq 45, r^3 > 1993r -1992\] As $r^3$ grows faster than $1992r$ when $r > \sqrt{1992} \implies r \geq 45$ and when $r = 45, 45^3 = 91125 > 87693 = 1993 \cdot 45 - 1992$

So $d = 1,2$

If $d = 1,$ then $1992(r-1) = 0 \implies r = 1$, which is not true because $r>1$. If $d = 2,$ then $(r-1)(r-1992) = 0 \implies r = 1,1992$, which is not true because $1<r<1992$ So there is no solution.

Part $2:$ Let us show that $1994$ is sensible. $1994 = 2 \cdot 997 = 2\cdot (996 + 1) = 22_{996}$

Comment: any composite number other than $p^2$, where $p$ is a prime is sensible as $n \cdot r = n \cdot (1 + (r-1)) = nn_{r-1}$ E.g $69 = 3\cdot 23 = 33_{22}$ ~Archieguan

See also

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

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