33
$\begingroup$

When calculating $42!=42\cdot41\cdot...\cdot2\cdot1$ the result is $42! = 140500611775287989854x14260624y511569936384z00000000$
However three digits have been replaced by $x$, $y$, and $z$.

Can you find $x$, $y$ and $z$ without recalculating $42!$ ?

$\endgroup$
2
  • 1
    $\begingroup$ Great puzzle! Encouraging some brain work rather than calculator work, and it's not hard with a few simple tricks. $\endgroup$ Commented Nov 6, 2021 at 20:37
  • 3
    $\begingroup$ @ Rand al'Thor This problem is well and truly a cookie cutter problem for all people who dabble in a little bit of number theory or have experience in contest math. $\endgroup$
    – user58783
    Commented Nov 6, 2021 at 21:07

2 Answers 2

40
$\begingroup$

Certainly I can find $z$ easily:

by calculating the number of powers of $2$ and of $5$ present in the factorisation of $42!$.

This can be done easily using Legendre's formula: the number of powers of a prime $p$ in $N!$ is exactly $\sum_{k=1}^{\infty}\lfloor\frac{N}{p^k}\rfloor$ (this is a finite sum since the summands are all zero for large enough $k$). With $N=42$ and $p=2$, this number is $21+10+5+2+1=39$; with $N=42$ and $p=5$, it is $8+1=9$.

So $42!$ is a multiple of $10^9$, which means $z=0$.

To find $x$ and $y$, it's simply a matter of

solving two simultaneous equations, by considering the fact that $42!$ is a multiple of both $9$ and $11$ and what this implies in terms of digit sums and alternating sums.

Since it's a multiple of $9$, the digit sum ($1+4+0+5+0+0+6+1+1+\cdots$) must be $0$ modulo $9$, which means $x+y+2$ must be $0$ mod $9$, so $x+y$ must be either $7$ or $16$ (it can't be higher since they're single digits).

Since it's a multiple of $11$, the alternating digit sum ($1-4+0-5+0-0+6-1+1+\cdots$) must be $0$ modulo $11$, which means $-x+y-1\equiv0$ modulo $11$, so $x=y-1$.

Therefore, the final answer is $x=3$ and $y=4$.

$\endgroup$
4
  • 1
    $\begingroup$ I knew I'd get beaten to the punch on a question like this, take my +1. $\endgroup$ Commented Nov 6, 2021 at 20:38
  • $\begingroup$ @AxiomaticSystem +1 to you too :-) $\endgroup$ Commented Nov 6, 2021 at 21:20
  • $\begingroup$ That name is Legendre's formula. $\endgroup$
    – aschepler
    Commented Nov 7, 2021 at 20:29
  • $\begingroup$ @aschepler Thanks! I felt like it might involve one of the L-guys (Legendre or Lagrange), but I couldn't bring it to mind. $\endgroup$ Commented Nov 8, 2021 at 5:12
21
$\begingroup$

First of all,

$z = 0$, because $42!$ has nine factors of five - eight from multiples of five, and a ninth because $25$ counts double - and many more factors of two, meaning it's divisible by $10^9$.
Then, realize that $42!$ is divisible by $99$. We can use a version of casting out [ninety-]nines to determine what x and y should be, and we get $10y+x+848 \equiv 0 \text{ mod } 99$, so $10y+x = 43$ or $x=3,y=4$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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