Home > Problem of the Week > Archive List > Detail

 << Prev 3/18/2012 Next >>

## Always An Integer Or...

Here is another problem from the website BrainDen.com, which daily offers Brain Teasers..and they do often tease my mind. On September 7, 2011, it posed the following problem.

Is [(2n-1)(2n-2)(2n-22)(2n-23)···(2n-2n-1)] ÷ n! an integer? Why or why not?

One point of clarification...the poser was basically asking...is it an integer for all natural numbers n?

Source: BrainDen.com, 9/7/2011

Hint: Try some valuies of n...

For n = 2, [(22-1)(22-21] ÷ 2! = ?

Now try n = 3, 4, 5...Is there a pattern?

If not, what is another way to attack the problem?

Solution Commentary: This problem is troublesome, as a pattern of "yes" is initially established for n = 1, 2, 3, ....10. Then, trouble arises, as n = 11 leads to a non-integer.

Why?

When the problem was posed, user "thoughtfulfellow" responded with a good analysis: "Reversed order of numerator and factored out 2's to get:
2(n-1)*(2-1)*2(n-2)*(22-1)....22*(2(n-2)-1)*2*(2(n-1)-1)*(2n-1).

=2(n2-n)*1*3*7*15*31*63*127*255*511*1023*2047...(2n-1)

Factoring out the 2's from the denominator, we will have a maximum of 2(n-1) so we only need worry about the odd factors in n!.

n! with 2's factored out =1*3*5*3*7*9*5*11 ....

If n=11, then 11 must be a factor of the numerator for the results to be an integer but this is not the case so this does not always result in an integer."

Nice thoughts, "Thoughtfulfellow"!