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 "1968 IMO Problems/Problem 2"
 
(5 intermediate revisions by 2 users not shown)
Line 2: Line 2:
  
 
Find all natural numbers <math>x</math> such that the product of their digits (in decimal notation) is equal to <math>x^2 - 10x - 22</math>.
 
Find all natural numbers <math>x</math> such that the product of their digits (in decimal notation) is equal to <math>x^2 - 10x - 22</math>.
 +
 +
==Video Solution (in Chinese) ==
 +
 +
https://youtu.be/M2OfNZcUgSI
  
 
==Solution 1==
 
==Solution 1==
Line 53: Line 57:
  
 
<math> \blacksquare</math>
 
<math> \blacksquare</math>
 +
 +
 +
==Remarks (added by pf02, August 2024)==
 +
 +
Solutions 2 and 3 are not satisfactory.  In fact, they can
 +
not be called solutions, since they make statements which
 +
are not proven.  Specifically:
 +
 +
In Solution 2, the author writes "It is pretty obvious that <math>x</math>
 +
cannot be three digits or more, because then <math>x^2 - 10x - 22</math> is
 +
way too big."  This is intuitively true, but not obvious at all.
 +
As a crucial step in the solution, it should be proven.  Later,
 +
the author states
 +
 +
"<math>(10a + b + 2)(10a + b - 12) \ge \cdots = 100(a^2 - a) + 24</math>.
 +
It is therefore clear that <math>a</math> must be either <math>0</math> or <math>1</math>".
 +
 +
First, the last term should be <math>-24</math> instead of <math>24</math>.  Either
 +
way, the conclusion about <math>a</math> is not clear at all. As a second
 +
crucial step in the solution, it should be proven.
 +
 +
In Solution 3, the notation and writing are very confusing.
 +
However, a diligent reader can make sense of them.  But in
 +
this solution as well, there are statements which beg for
 +
a proof.  The first such statement is
 +
 +
"<math>a^2 \not\equiv 2\ (mod\ 3), a^2 \not\equiv 2\ (mod\ 5),
 +
a^2 \not\equiv 5\ (mod\ 7)</math> which means <math>3, 5, 7</math> don't
 +
divide <math>(x - 5)^2 - 47 = y</math>".
 +
 +
(When writing <math>a^2</math> the author means the square of an
 +
arbitrary natural number, not the square of the number<math>a</math>
 +
used in the line above this statement.)  Neither the modulo
 +
statements, nor the conclusion are obvious; proofs should
 +
be given.  The second unproven statement is
 +
 +
"<math>2^a + 47 = (x - 5)^2</math>.  It is easy to see that <math>a</math> has one
 +
solution and that is <math>2</math>. (Prove it by contradiction.)"
 +
 +
(The author means "the equation has a unique solution for <math>a</math>".)
 +
The conclusion about the uniqueness of <math>a</math> is not easy to see,
 +
and as a crucial step in the solution, it should be proven.
 +
 +
Below, I will give corrected, complete, and somewhat simplified
 +
versions of these two solutions.
 +
 +
 +
==Solution 2 (corrected and complete)==
 +
 +
Let the decimal expansion of <math>x</math> be <math>\overline{d_1d_2d_3\dots d_n}</math>,
 +
where <math>d_i</math> are base-10 digits.  Let us prove first that <math>n \le 2</math>.
 +
 +
Using <math>x^2 - 10x -22 = (x - 5)^2 - 47</math> and the fact that this expression
 +
equals the product <math>d_1d_2d_3 \dots d_n</math> we have that <math>(x - 5)^2 - 47 \le 9^n</math>.
 +
Since <math>x</math> has <math>n</math> digits, we also have
 +
<math>(x - 5)^2 - 47 \ge (10^{n - 1} - 5)^2 - 47</math>.  Thus, we have
 +
<math>9^n \ge (10^{n - 1} - 5)^2 - 47</math>.  We will show that this can not be true
 +
for <math>n \ge 3</math>.
 +
 +
Divide by <math>9^{n - 1}</math>, rearrange factors and terms, and get
 +
<math>\left[\left(\frac{10}{3}\right)^{n - 1} - \frac{5}{3^{n - 1}}\right]^2 \le
 +
9 + \frac{47}{9^{n - 1}} < 10</math>.  Again using <math>n \ge 3</math>, we get
 +
<math>\left(\frac{10}{3}\right)^{n - 1} < \sqrt{10} + \frac{5}{3^{n - 1}} < 5</math>.
 +
This is false for <math>n \ge 3</math>, so <math>n =</math> the number of digits of <math>x</math> can not
 +
be more than <math>2</math>.
 +
 +
Let then <math>x = 10a + b</math>, with <math>0 \le a, b \le 9</math> the digits of <math>x</math>.  We have
 +
<math>x^2 - 10x - 22 = ab \le 81</math>.  By solving the quadratic equation
 +
<math>x^2 - 10x - 103 = 0</math> we see that the inequality is true when <math>0 \le x \le 16</math>.
 +
 +
At this point, we could simply check which of the numbers <math>x = 0, 1, \dots, 16</math>
 +
has the product of its digits equal to <math>x^2 - 10x -22</math>.  It would turn out that
 +
<math>x = 12</math> is the only one.  But we can take a short cut by writing
 +
<math>(10a + b)^2 - 10(10a + b) - 22 = ab</math>. and using that <math>a = 0</math> or <math>a = 1</math>.
 +
In the case <math>a = 0</math> we get the equation <math>b^2 - 10b - 22 = 0</math> in <math>b</math>
 +
which has no integer solutions.  In the case <math>a = 1</math> we get the equation
 +
<math>b^2 + 9b - 22 = 0</math> in <math>b</math>, which has solutions <math>-11</math> and <math>2</math>.  Since <math>b</math>
 +
is a digit, <math>b = 2</math> is the only acceptable solution, so <math>x = 12</math>.
 +
 +
 +
==Solution 3 (corrected and complete)==
 +
 +
Let <math>y = x^2 - 10x - 22</math>.  Since <math>y</math> is a product of digits, the only
 +
prime factors of <math>y</math> can be <math>2, 3, 5, 7</math>.  Write <math>y = (x - 5)^2 - 47</math>.
 +
 +
Note that if <math>A</math> is a natural number then <math>A^2 \equiv 0</math> or <math>1\ (mod\ 3)</math>.
 +
Indeed, <math>A = 3k</math> or <math>A = 3k + 1</math> or <math>A = 3k + 2</math> for some <math>k</math>.  By writing
 +
out <math>A^2</math> the statement follows immediately.  Then
 +
<math>(x - 5)^2 - 47 \equiv 1</math> or <math>2\ (mod\ 3)</math>, so <math>3</math> can not be a factor of <math>y</math>.
 +
 +
Similarly, if <math>A</math> is a natural number then <math>A^2 \equiv 0, 1</math> or <math>4\ (mod\ 5)</math>.
 +
Then <math>(x - 5)^2 - 47 \equiv 3, 4</math> or <math>2\ (mod\ 5)</math>, so <math>5</math> can not be a factor
 +
of <math>y</math>.
 +
 +
And finally if <math>A</math> is a natural number then
 +
<math>A^2 \equiv 0, 1, 2</math> or <math>4\ (mod\ 7)</math>.
 +
Then <math>(x - 5)^2 - 47 \equiv 2, 3, 4</math> or <math>6\ (mod\ 7)</math>, so <math>7</math> can not be a
 +
factor of <math>y</math>.
 +
 +
The only possible prime factor of <math>y</math> is <math>2</math>.  So <math>2^z = (x - 5)^2 - 47</math>
 +
for some <math>z \ge 0</math>.  Write this as <math>2^z -2 = (x - 5)^2 - 49</math>, or
 +
<math>2(2^{z - 1} - 1) = (x - 12)(x + 2)</math>.
 +
 +
Clearly <math>z = 0</math> is not acceptable because the equation in <math>x</math> has no
 +
integer solutions.
 +
 +
If <math>z > 1</math> the left hand side is divisible by <math>2</math>, but not by <math>4</math>.  The right
 +
hand side is not divisible by <math>2</math> if <math>x</math> is odd, and is divisible by <math>4</math> if
 +
<math>x</math> is even.  So <math>z > 1</math> yields no solutions.
 +
 +
If <math>z = 1</math>, the equation becomes <math>x^2 - 10x - 24 = 0</math> which has solutions
 +
<math>-2, 12</math>.  The only acceptable solution is <math>x = 12</math>.
 +
  
 
==See Also==
 
==See Also==
  
 
{{IMO box|year=1968|num-b=1|num-a=3}}
 
{{IMO box|year=1968|num-b=1|num-a=3}}
−
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=361673&sid=6798c42a2ab57f3ca82ffba974ed589c#p361673 Discussion on AoPS/MathLinks]
 
  
 
[[Category:Olympiad Number Theory Problems]]
 
[[Category:Olympiad Number Theory Problems]]

Latest revision as of 18:26, 15 November 2024

Problem

Find all natural numbers $x$ such that the product of their digits (in decimal notation) is equal to $x^2 - 10x - 22$.

Video Solution (in Chinese)

https://youtu.be/M2OfNZcUgSI

Solution 1

Let the decimal expansion of $x$ be $\overline{d_1d_2d_3\dots d_n}$, where $d_i$ are base-10 digits. We then have that $x\geq d_1\cdot 10^{n-1}$. However, the product of the digits of $x$ is $d_1d_2d_3\dots d_n\leq d_1\cdot 10\cdot 10\dots 10=d_1\cdot 10^{n-1}$, with equality only when $x$ is a one-digit integer. Therefore the product of the digits of $x$ is always at most $x$, with equality only when $x$ is a base-10 digit. This implies that $x^2-10x-22\leq x$, so $x^2-11x-22\leq 0$. Every natural number from 1 to 12 satisfies this inequality, so we only need to check these possibilities. It is easy to rule out 1 through 11, since $x^2-10x-22<0$ for those values. However, $12^2-10\cdot 12-22=2$, which is the product of the digits of 12. Therefore $\boxed{12}$ is the only natural number with the desired properties. $\blacksquare$

Solution 2(SFFT)

It is pretty obvious that $x$ cannot be three digits or more, because then $x^2 - 10x - 22$ is way too big.

Write $x = 10a + b$ where $a$ and $b$ are digits satisfying $0 \leq a, b < 10$. Then, we can use SFFT: \[(10a + b)^2 - 10(10a + b) - 22 = ab\] \[(10a + b)^2 - 10(10a + b) - 24 = ab - 2\] \[(10a + b + 2)(10a + b - 12) = ab - 2.\] We have \[(10a + b + 2)(10a + b - 12) \geq (10a + 2)(10a - 12) = 100a^2 - 100a + 24 = 100(a^2 - a) + 24.\] It is therefore clear that $a$ must be either $0$ or $1$. We can then split into two cases:

$\mathbf{a = 0:}$

We have $(b + 2)(b - 12) = -2$ or $b^2 - 10b - 22 = 0$, which is only satisfied when $b = -2$ or $12$.

$\mathbf{a = 1:}$

We have $(b + 12)(b - 2) = b - 2$. This is only satisfied when $b = 2$, or $b + 12 = 0$. Therefore, $b = 2$, and so $x = \boxed{12}.\square$

~mathboy100

Solution 3

Let, $x^2-10x-22=y$

$\implies x^2-10+25-47=y$

$\implies (x-5)^2=47+y$

Now note that, if $p$ is a prime such that $p|y$ then $7\geq p$.

That means, $y=2^a*3^b*5^c*7^d$

But, $a^2 \not\equiv 2 (mod3), a^2 \not\equiv 2 (mod5), a^2 \not\equiv 5 (mod7)$ which means $3,5,7$ don't divivde $(x-5)^2-47=y.$

So, $y=2^a$ and $y+17=2^a+47=(x-5)^2$

It is easy to see that $a$ has one solution and that is $2.$( Prove it by contradiction)

So, $(x-5)^2=47+2=49$

$\implies x=12$

$\blacksquare$


Remarks (added by pf02, August 2024)

Solutions 2 and 3 are not satisfactory. In fact, they can not be called solutions, since they make statements which are not proven. Specifically:

In Solution 2, the author writes "It is pretty obvious that $x$ cannot be three digits or more, because then $x^2 - 10x - 22$ is way too big." This is intuitively true, but not obvious at all. As a crucial step in the solution, it should be proven. Later, the author states

"$(10a + b + 2)(10a + b - 12) \ge \cdots = 100(a^2 - a) + 24$. It is therefore clear that $a$ must be either $0$ or $1$".

First, the last term should be $-24$ instead of $24$. Either way, the conclusion about $a$ is not clear at all. As a second crucial step in the solution, it should be proven.

In Solution 3, the notation and writing are very confusing. However, a diligent reader can make sense of them. But in this solution as well, there are statements which beg for a proof. The first such statement is

"$a^2 \not\equiv 2\ (mod\ 3), a^2 \not\equiv 2\ (mod\ 5), a^2 \not\equiv 5\ (mod\ 7)$ which means $3, 5, 7$ don't divide $(x - 5)^2 - 47 = y$".

(When writing $a^2$ the author means the square of an arbitrary natural number, not the square of the number$a$ used in the line above this statement.) Neither the modulo statements, nor the conclusion are obvious; proofs should be given. The second unproven statement is

"$2^a + 47 = (x - 5)^2$. It is easy to see that $a$ has one solution and that is $2$. (Prove it by contradiction.)"

(The author means "the equation has a unique solution for $a$".) The conclusion about the uniqueness of $a$ is not easy to see, and as a crucial step in the solution, it should be proven.

Below, I will give corrected, complete, and somewhat simplified versions of these two solutions.


Solution 2 (corrected and complete)

Let the decimal expansion of $x$ be $\overline{d_1d_2d_3\dots d_n}$, where $d_i$ are base-10 digits. Let us prove first that $n \le 2$.

Using $x^2 - 10x -22 = (x - 5)^2 - 47$ and the fact that this expression equals the product $d_1d_2d_3 \dots d_n$ we have that $(x - 5)^2 - 47 \le 9^n$. Since $x$ has $n$ digits, we also have $(x - 5)^2 - 47 \ge (10^{n - 1} - 5)^2 - 47$. Thus, we have $9^n \ge (10^{n - 1} - 5)^2 - 47$. We will show that this can not be true for $n \ge 3$.

Divide by $9^{n - 1}$, rearrange factors and terms, and get $\left[\left(\frac{10}{3}\right)^{n - 1} - \frac{5}{3^{n - 1}}\right]^2 \le 9 + \frac{47}{9^{n - 1}} < 10$. Again using $n \ge 3$, we get $\left(\frac{10}{3}\right)^{n - 1} < \sqrt{10} + \frac{5}{3^{n - 1}} < 5$. This is false for $n \ge 3$, so $n =$ the number of digits of $x$ can not be more than $2$.

Let then $x = 10a + b$, with $0 \le a, b \le 9$ the digits of $x$. We have $x^2 - 10x - 22 = ab \le 81$. By solving the quadratic equation $x^2 - 10x - 103 = 0$ we see that the inequality is true when $0 \le x \le 16$.

At this point, we could simply check which of the numbers $x = 0, 1, \dots, 16$ has the product of its digits equal to $x^2 - 10x -22$. It would turn out that $x = 12$ is the only one. But we can take a short cut by writing $(10a + b)^2 - 10(10a + b) - 22 = ab$. and using that $a = 0$ or $a = 1$. In the case $a = 0$ we get the equation $b^2 - 10b - 22 = 0$ in $b$ which has no integer solutions. In the case $a = 1$ we get the equation $b^2 + 9b - 22 = 0$ in $b$, which has solutions $-11$ and $2$. Since $b$ is a digit, $b = 2$ is the only acceptable solution, so $x = 12$.


Solution 3 (corrected and complete)

Let $y = x^2 - 10x - 22$. Since $y$ is a product of digits, the only prime factors of $y$ can be $2, 3, 5, 7$. Write $y = (x - 5)^2 - 47$.

Note that if $A$ is a natural number then $A^2 \equiv 0$ or $1\ (mod\ 3)$. Indeed, $A = 3k$ or $A = 3k + 1$ or $A = 3k + 2$ for some $k$. By writing out $A^2$ the statement follows immediately. Then $(x - 5)^2 - 47 \equiv 1$ or $2\ (mod\ 3)$, so $3$ can not be a factor of $y$.

Similarly, if $A$ is a natural number then $A^2 \equiv 0, 1$ or $4\ (mod\ 5)$. Then $(x - 5)^2 - 47 \equiv 3, 4$ or $2\ (mod\ 5)$, so $5$ can not be a factor of $y$.

And finally if $A$ is a natural number then $A^2 \equiv 0, 1, 2$ or $4\ (mod\ 7)$. Then $(x - 5)^2 - 47 \equiv 2, 3, 4$ or $6\ (mod\ 7)$, so $7$ can not be a factor of $y$.

The only possible prime factor of $y$ is $2$. So $2^z = (x - 5)^2 - 47$ for some $z \ge 0$. Write this as $2^z -2 = (x - 5)^2 - 49$, or $2(2^{z - 1} - 1) = (x - 12)(x + 2)$.

Clearly $z = 0$ is not acceptable because the equation in $x$ has no integer solutions.

If $z > 1$ the left hand side is divisible by $2$, but not by $4$. The right hand side is not divisible by $2$ if $x$ is odd, and is divisible by $4$ if $x$ is even. So $z > 1$ yields no solutions.

If $z = 1$, the equation becomes $x^2 - 10x - 24 = 0$ which has solutions $-2, 12$. The only acceptable solution is $x = 12$.


See Also

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