1
$\begingroup$

In the annual meeting of the International Conference of Puzzle Scenarios, each of $100$ people in a room is given a different number from the set $\{1!,2!,3!,...,99!,100!\}$. One person leaves the room, and the other $99$ multiply their numbers together and find that the product is a perfect square.

$51!$ was absolutely sure that $50!$ didn't leave the room at all.

Which number is missing from the product?

$\endgroup$
  • 2
    $\begingroup$ The only number k in {1,...,100} such that 1! 2! ... 100! / k! is a perfect square is 50. $\endgroup$ – Reiner Martin Apr 9 '18 at 15:00
  • $\begingroup$ @ReinerMartin Indeed! $\endgroup$ – NMister Apr 9 '18 at 15:00
  • 4
    $\begingroup$ So is this a trick question somehow, as 50 did not leave the room (sorry, I am absolutely new to this 'Puzzling' site, so I might not know how this works)? $\endgroup$ – Reiner Martin Apr 9 '18 at 15:04
  • 1
    $\begingroup$ Perhaps you should provide a hint? $\endgroup$ – Mike Earnest Apr 11 '18 at 15:07
  • 1
    $\begingroup$ @NMister Can you confirm that this puzzle has got a solution that we didn't find already? $\endgroup$ – xhienne Apr 18 '18 at 9:02
10
$\begingroup$

Here is a proof of Reiner Martin's comment that only 50! can be removed. Let X = 1! • 2! • ... • 100!.

  • The prime factorization of X contains the prime 53 an even number (48) of times. Removing any number 53 or more would make this odd, which is impossible for a perfect square.

  • The prime factorization of X contains the prime 47 an odd number (59) of times. Removing any number less than 47 would make the product still be odd, impossible.

  • The prime factorization of X contains the prime 17 an even number of times. Removing either 51! or 52! would remove 3 occurrences of 17, leaving an odd number of 17s.

  • The prime factorization of X contains the prime 2 an odd number of times. Removing 47!, 48! or 49! would remove an even number of occurrences of 2, leaving an odd number of 2s.

As we can see, the only option is to remove 50!, which indeed works.

$\endgroup$
4
$\begingroup$

Since Mike Earnest's excellent answer contradicts what 51! asserted, let us read the question from another angle: "Which number is missing from the product?" may actually mean:

What number did they forget to multiply?

The only possibility for the product being a square is if 50! left the room which cannot be true. That means they forgot to take 50! into account in their product.

What number left the room then? Well, that must be 1

$\endgroup$
1
$\begingroup$

Since it seems that the only possible mathematical solution is not the correct one

we have to rely on lateral thinking.

Short after the numbers were given to the $100$ people, $49!$ and $50!$ switched their numbers. The person who leaves the room is in fact the one holding the $50!$ number, but it's not the one which it was given to.

So when the other $99$ multiply their numbers, the result is a square root since the number $50!$ is missing, and $51!$ says that $50!$ didn't left the room because he can see the person, but doesn't know that he is now holding the $49!$ number.

$\endgroup$
0
$\begingroup$

50!

because

51! is a compulsive liar (sorry this is a strange answer perhaps, but I put it up just to check that this is not the required answer)

$\endgroup$
0
$\begingroup$

Another lateral thinking solution

they did not know who has the which number, and got an overflow when making their calculations (e.g. using insufficient bitwidth of the integer operands).

Explanations

Since factorials are divisible by very large powers of two (e.g. $100!$ is divisible by $2^{97}$), and the result will be enormously large (about $10^{6784}$ or so, if multiplying all 100 factorials), it's easy to get an overflow which will be zero (when using standard binary integer arithmetics, which actually works modulo $2^w$, where $w$ is the bitwidth). Of course, 0 is a perfect square.
If the people didn't know who has got the which number, the only source for the $51!$-person's certainty will be the fact that he/she left the room himself/herself, which makes the answer $51!$.

$\endgroup$
-1
$\begingroup$

Two answers are

$49!$ and $48!$

Here is how it works:

The product of all the factorials is $2^{99} \times 3^{98} \times \dots\times 99^2 \times 100$. This is a square iff the same number with the powers reduced modulo 2 is a square. Reducing the powers modulo 2 gives $2 \times 4 \times \dots \times 100 = 2(1 \times 2 \times \dots \times 50) = 2 \times 50!$. Therefore if we divide the original number by $49!$ and reduce the powers modulo 2 as above we would get $\frac{2 \times 50!}{49!} = 2 \times 50 = 100$, a square. Moreover, dividing the original number by $48!$ and reducing the powers modulo 2 gives $2 \times 49 \times 50 = 4900$, also square.

$\endgroup$
  • 5
    $\begingroup$ $2 \times 4 \times \ldots \times 100 = 2^{50} 50!$ not $2 \times 50!$ $\endgroup$ – hexomino Apr 9 '18 at 15:31
  • $\begingroup$ @hexomino Darn! $\endgroup$ – Statman Apr 9 '18 at 15:36

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.