## Puzzle of the week [26]

Le Monde weekend puzzle for the past week (I have not peeked at the solution yet!) was quite straightforward: find those n‘s such that 2n divides n! and those n‘s for which 2n-1 divides n. Looking at the problem in the plane to Montpellier, I think that the solution is that no positive n exists such that 2n divides n! and powers of 2 are those numbers for which 2n-1 divides n.

My reasoning is

1. that the numbers with the highest potential is a power of 2,
2. that 2n-1 divides n! when n is of the form 2m, and
3. therefore that no integer n can satisfy the harder constraint.

Proving that 2n-1 divides n! when n is of the form n=2m can be done by induction: it works for n=2 and if it works for 2m, then it works for n=2m+1 by considering a separation of n! into

$(2^m)! \times (2^m+1)\cdots 2^{m+1}$

and by using the induction assumption that (2m)! can be divided by

$2^{2^m-1}.$

Recycling the dividers for the second part leads to its being divisible by

$2^{2^m}$

because the very last term in the factorial is by 2m+1, which can be divided by 2m+1… Proving that integers other than the 2m‘s cannot be divided by 2n-1 again works by an induction proof on m.

This site uses Akismet to reduce spam. Learn how your comment data is processed.