3
$\begingroup$

I have taken the 12th problem of this pdf, do you know any way to resolve it without using brute force?

Simply I have to replace '*' of this multiplication below with correct digits, in order to have the factors corrected.

$$\begin{alignedat}{2}*&*4&&\,\times{}\\ &**&&={}\\\hline 44&*4&& \end{alignedat} $$

Each '*' can be a different digit.

$\endgroup$
14
  • $\begingroup$ what "without using only attempts" is supposed to mean $\endgroup$
    – Abr001am
    Feb 20, 2016 at 15:57
  • $\begingroup$ If there are any methods to solve it a part of brute force. $\endgroup$
    – untitled
    Feb 20, 2016 at 16:01
  • $\begingroup$ of course there is $\endgroup$
    – Abr001am
    Feb 20, 2016 at 16:04
  • 1
    $\begingroup$ The two-digit number ends in 1 or 6, and is less than 45. There are seven options, which isn't too brutish. $\endgroup$
    – Empy2
    Feb 20, 2016 at 16:04
  • 2
    $\begingroup$ factor all numbers of the form 44*4 $\endgroup$
    – JMP
    Feb 20, 2016 at 16:09

4 Answers 4

4
$\begingroup$

The most straightforward way I can think of is to consider all ten possibilities for the * in 44*4, factor each into primes, and see which ones have prime factors that can recombine into a two-digit number and a three-digit number that ends in a $4$:

$$\begin{align} 4404&=2\cdot2\cdot3\cdot367\\ 4414&=2\cdot2207\\ 4424&=2\cdot2\cdot2\cdot7\cdot79\\ 4434&=2\cdot3\cdot739\\ 4444&=2\cdot2\cdot11\cdot101\\ 4454&=2\cdot17\cdot131\\ 4464&=2\cdot2\cdot2\cdot2\cdot3\cdot3\cdot31\\ 4474&=2\cdot2237\\ 4484&=2\cdot2\cdot19\cdot59\\ 4494&=2\cdot3\cdot7\cdot107 \end{align}$$

There is more than one answer:

$4444=11\cdot404\qquad 4464=36\cdot124\qquad4494=21\cdot214$

However, this seems a bit brute-forcey. In particular, how do we know $2207$ and $2237$ are primes? If you're trying to do everything by hand (which I didn't!), you've got your work cut out for you.

$\endgroup$
3
  • $\begingroup$ I think $404*11 = 4444$ is not allowed since all 4s are originally showing (stated in the pdf if I understand spanish) $\endgroup$
    – Steve
    Feb 20, 2016 at 16:33
  • 3
    $\begingroup$ @Steve It's Italian (lol) $\endgroup$
    – untitled
    Feb 20, 2016 at 16:34
  • $\begingroup$ @BarryCipra Thanks to the comments I was calculating those factors (with a program). However I think it's a bit brute force and a bit method. Thank you $\endgroup$
    – untitled
    Feb 20, 2016 at 16:39
2
$\begingroup$
  • Hints of bruteforceless method without factorising:

$\ \ \ \ \ \ abc\ \ $

$*\ \ \ \ \ de$

$=xyzt$

1- $t=ce=4e$, returning to rule of congruence $e$ is either $1$ or $6$ whilst $r(t)=2$ the retained

2- Since $x=ad+r(y)=4$ so either ${a,d}=2,r(y)=0$ or $a=1$ and $d={1,2,3}$ or vice versa with $r(y)$ is respectively {3,2,1}

3- Sine $ae+bd=4$ starting with case $e=1$

$a+bd+r(z)=4+r(y)$ if $(a,d)=(2,2),r(y)=0$ then $b=1$ and $r(z)=0$ so $z=dc+be=4*2+1*1=9$ is a valid solution

$\endgroup$
5
  • $\begingroup$ Why should I start with case e = 1? $\endgroup$
    – untitled
    Feb 27, 2016 at 19:40
  • $\begingroup$ @SimoneBonato you can start with whatever value you want but keep attention to not come across a contradiction in results $\endgroup$
    – Abr001am
    Feb 27, 2016 at 19:42
  • $\begingroup$ "3- Sine ae+bd=4 starting with case e=1". However, I made the same question on Italian Yahoo Answer it.answers.yahoo.com/question/index?qid=20160220071154AAmzGjU if you want more solutions to solve the problem. $\endgroup$
    – untitled
    Feb 27, 2016 at 19:49
  • $\begingroup$ @SimoneBonato i could generate more solutions but since one single possibility is asked, i vnt gone further $\endgroup$
    – Abr001am
    Feb 27, 2016 at 19:54
  • $\begingroup$ Sorry, *methods to solve the problem $\endgroup$
    – untitled
    Feb 27, 2016 at 19:56
1
$\begingroup$

One method for this problems is to select digits for which there are relatively few possible values, and start trying to narrow down the possibilities by trial and error. The following is an attempt to do this a little more cleverly.

Let $x + 10$ represent the unknown digits on the first line, $y + 10$ the unknown digits on the second line, and $z$ the last unknown digit, so that $$ (10(x + 10) + 4)\times(y + 10) = 4404 + 10z \tag1 $$ where $0 \leq x < 90$, $0 \leq y < 90$, and $0 \leq z \leq 9$.

Equation $(1)$ implies $10(x+10)(y+10) \leq 4494$, so $(x+10)(y+10) < 500$. Since $x\geq0$ and $y\geq0$, this implies $x < 40$ and $y < 40$. But no unknown digit can be $4$, so neither $x$ nor $y$ can have $3$ as the first digit. Together, these facts imply that $x \leq 29$ and $y \leq 29$.

Multiplying $(1)$ on the left and simplifying, \begin{gather} 10xy + 100x + 104y + 1040 = 4404 + 10z, \\ 10xy + 100x + 104y = 3364 + 10z. \tag2\\ \end{gather}

Equation $(2)$ implies $4y\equiv 4 \pmod{10}$, so the last digit of $y$ is either $1$ or $6$. Also, $(10(x + 10) + 4)\times 11 < 400 \times 11 < 4404$, so $y$ cannot be $1$. We can then write $y = 5n + 6$, where $0 \leq n \leq 4$. Then \begin{gather} 10x(5n + 6) + 100x + 104(5n + 6) = 3364 + 10z, \\ 50nx + 160x + 520n + 624 = 3364 + 10z, \\ 5nx + 16x + 52n = 274 + z, \\ (5n+16)x = 274 - 52n + z. \end{gather}

At this point trial and error starts to look attractive, since there are only five possible values of $n$.

Case $n=0$. Then $16x = 274 + z$. Since $274 \equiv 2 \pmod{16}$, there is no solution for $0\leq z\leq9$.

Case $n=1$. Then $21x = 274 - 52 + z = 222 + z$. Since $222 \equiv 12 \pmod{21}$, $z=9$ and $x=231/21=11.$ This solution is $$ 214 \times 21 = 4494. $$

Case $n=2$. Then $26x = 274 - 104 + z = 170 + z$. Since $170 \equiv -12 \pmod{26}$, there is no solution for $0\leq z\leq9$.

Case $n=3$. Then $31x = 274 - 156 + z = 118 + z$. Since $118 \equiv -6 \pmod{31}$, $z=6$ and $x=124/31 = 4$. But that would mean that $*\!*\!4 = 144$ in the original equation, which we have ruled out, so there is no solution in this case.

Case $n=4$. Then $36x = 274 - 208 + z = 66 + z$. Since $66 \equiv -6 \pmod{36}$, $z=6$ and $x=72/36 = 2$. This solution is $$ 124 \times 36 = 4494. $$

I would bet on the answer $124 \times 36 = 4494$, since all the unknown digits are pairwise distinct.

Whether or not this method is easier than whittling away one value of one digit at a time is questionable, but it is surely possible to do this by hand.

$\endgroup$
1
$\begingroup$

You have $$\begin{align} (10 a + 4)b &= 4404 + 10 c \\ 10 &\leq a \leq 99 \\ 10 &\leq b \leq 99 \\ 0 &\leq c \leq 9 \end{align}$$

By brute force, there are $(99-10+1)(99-10+1)(9-0+1) = 81\,000$ cases. (Throughout, the remaining number of cases is reported in this brute force sense. This is always a gross overestimate of the amount of work we should do. For instance, we could let $b$ and $c$ iterate over their ranges and attempt to solve for $a$ for each $(b,c)$ pair. This would only require testing $900$ pairs.)

Say $b \geq 44$. Then $(10a+4)b \geq (10(10)+4)44 = 4576$, which is too large. So actually, $10 \leq b \leq 43$. Likewise, if $a \geq 45$, the product on the left is too large. So actually, $10 \leq a \leq 44$.

These simple considerations eliminate $69\,100$ cases, leaving only $11\,900$.

  • reduce modulo $5$: The reduced equation is $4 b \cong 4 \pmod{5}$, so $b$ is congruent to $1 \pmod{5}$. This eliminates about 80% of the cases, leaving $2450$. Rewrite $b = 5d+1$. The same simple considerations as above restrict $11 \leq a \leq 40$ (now only $2100$ cases), yielding $$\begin{align} (10 a + 4)(5d+1) &= 4404 + 10 c \\ 11 &\leq a \leq 40 \\ 2 &\leq d \leq 8 \\ 0 &\leq c \leq 9 \end{align}$$ (Note: this says $50ad = 4404 - 10a +10c -20d-4$, so $ad \in [77,86]$. These are immediately factorable if you know $83, 79, 43, 41, 17, ..., 2$ are prime.)
  • If $d$ is odd, it is either $3$, $5$, or $7$. This is a small set, so we handle it directly.
    • If $d=3$, we have $(10a +4)16 = 4404 + 10c$. Reducing modulo 16, this is $0 \cong 4 + 10 c \pmod{16}$, i.e. $0 \cong 2 + 5c \pmod{8}$, so $c=6$. But this requires $10+4 = 279$, which is not possible.
    • If $d=5$, reduce modulo $26$ and discover $0 \cong 10 + 10 c \pmod{26}$, i.e. $5c \cong 8 \pmod{13}$. The smallest nonnegative solution is $c=12$, so $d \neq 5$.
    • If $d=7$, the same methods show $c=6$, then $10a+4 = \frac{4464}{36} = 124$ and $a=12$ is a solution. So we have found a solution to the initial problem: $$124 \cdot 36 = 4464.$$
  • Otherwise, $d$ is even. Write it as $d = 2e$. (Now we're down to $1200$ cases.) $$\begin{align} (10 a + 4)(10e+1) &= 4404 + 10 c \\ 11 &\leq a \leq 40 \\ 1 &\leq e \leq 4 \\ 0 &\leq c \leq 9 \end{align}$$ This says $10(10 ae + a + 4e) + 4 = 10 (440 + c) + 4$. That is $$10 ae + a + 4e = 440 + c. $$ (Note that factoring the possible right-hand sides only requires primes less than $21$, so should not seem prohibitive.) Reduce modulo $2$ and find $a$ and $c$ are either even together or odd together: $a=2f+h, c=2g+h$m where $h$ is $0$ if both are even and $1$ otherwise.
    • If both are even, we consider $$\begin{align} 10 ef + f + 2e &= 220 + g \\ 6 &\leq f \leq 20 \\ 1 &\leq e \leq 4 \\ 0 &\leq g \leq 4 \end{align}$$ Modulo $2$, this says $f$ and $g$ have the same parity and we reduce to $$\begin{align} 10 ej + j + e &= 110 + k & (f \mapsto 2j, g \mapsto 2k) \\ 3 &\leq j \leq 10 \\ 1 &\leq e \leq 4 \\ 0 &\leq k \leq 2 \end{align}$$ Rewrite this as $10 ej = 110 -e-j+k$ and realize $110-e-j+k \in [96,108]$ and is divisible by $10$. This forces $ej=10$. Given their allowed ranges, either $e=1$ and $j=10$ (so that $100 +10+1 = 110+k$, so $k=1$) or $e=2$ and $j=5$ (so that $100 + 5 + 2 = 110+k$, so $k =7$, an impossibility). Unravelling our variable assignments, this gives the solution $$ 404 \cdot 11 = 4444. $$
    • Otherwise both are odd and we consider $$\begin{align} 10 ef + f + 7e &= 220 + g \\ 5 &\leq f \leq 19 \\ 1 &\leq e \leq 4 \\ 1 &\leq g \leq 4 \end{align}$$ Rewrite as $10ef = 220-7e-f+g$ to see that $10ef \in [174,212]$. Therefore $ef \in [18,19,20,21]$. (This is actually only a handful of cases to check because $1 \leq e \leq 4$.) We will find $7e+f<40$, forcing the impossibility $g<0$ in all of these cases, so the set of solutions to the original problem are the two found above.
      • $ef=18: e=1, f=18: 7e+f = 25 < 40$, so $g<0$, an impossibility.
      • $ef=18: e=2, f=9: 7e+f = 23.$
      • $ef=18: e=3, f=6: 7e+f = 27.$
      • $ef=19: e=1, f=19: 7e+f = 26.$
      • $ef=20: e=1, f=20: 7e+f = 27.$
      • $ef=20: e=2, f=10: 7e+f = 24.$
      • $ef=20: e=4, f=5: 7e+f = 33.$
      • $ef=21: e=1, f=21: 7e+f = 28.$
      • $ef=21: e=3, f=7: 7e+f = 28.$

Therefore, the solutions are $$\begin{align} 404 \cdot 11 &= 4444, \text{ and} \\ 124 \cdot 36 &= 4464. \end{align}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.