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"
(→‎Solution)
Line 10: Line 10:
 
Every number that can be expressed as
 
Every number that can be expressed as
 
<cmath>  b \cdot \frac{r^d-1}{r-1} , b < r </cmath>
 
<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>
+
Is a "''sensible''" number as it can be expressed as <math>b\cdots b _ r</math>, where there are <math>d</math> <math>b’s</math>
  
 
Part <math>1:</math> Let us prove that <math>1993</math> cannot be expressed as such.
 
Part <math>1:</math> Let us prove that <math>1993</math> cannot be expressed as such.
Line 38: Line 38:
 
E.g <math>69 = 3\cdot 23 = 33_{22}</math>
 
E.g <math>69 = 3\cdot 23 = 33_{22}</math>
 
~Archieguan
 
~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$ $b’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=230376"