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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

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

%d bloggers like this: