33

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!$ ?

Rand al'Thor
  • 116,845
  • 28
  • 322
  • 627
ThomasL
  • 12,167
  • 3
  • 24
  • 100
  • 1
    Great puzzle! Encouraging some brain work rather than calculator work, and it's not hard with a few simple tricks. – Rand al'Thor Nov 06 '21 at 20:37
  • 3
    @ 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. –  Nov 06 '21 at 21:07

2 Answers2

40

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$.

Rand al'Thor
  • 116,845
  • 28
  • 322
  • 627
21

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$.

AxiomaticSystem
  • 9,864
  • 16
  • 38