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$

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