I don't have any idea how to even begin with this..

Let $K$ be the product of all factors $(b-a)$ (not necessarily distinct) where $a$ and $b$ are integers satisfying $1\le a < b \le 20$. Find the greatest positive integer $n$ such that $2^n$ divides $K$.

Can someone give a lead? A solution is also welcome...

  • 4
    $\begingroup$ $K = 19^1 \cdot 18^2 \cdot 17^3 \cdot \cdots$ $\endgroup$ – Fabio Somenzi Dec 24 '16 at 7:58
  • $\begingroup$ To start with, how many pairs $(a,b)$ with $b-a$ divisible by $2$? (I get $90.$) Then, how many divisible by $4$? by $ 8$? by $ 16$? $\endgroup$ – bof Dec 24 '16 at 7:58

How many of those factors $b-a$ are divisible by $2$? That means $a$ and $b$ are both odd or both even, so the number is $\binom{10}2+\binom{10}2=90.$

How many are divisible by $4$? Take both $a$ and $b$ from one of the sets $\{1,5,9,13,17\}$ or $\{2,6,10,14,18\}$ or $\{3,7,11,15,19\}$ or $\{4,8,12,16,20\},$ so the number is $4\cdot\binom52=40.$

How many are divisible by $8$? Pick $a$ and $b$ from one of the sets $\{1,9,17\}$ or $\{2,10,18\}$ or $\{3,11,19\}$ or $\{4,12,20\}$ or $\{5,13\}$ or $\{6,14\}$ or $\{7,15\}$ or $\{8,16\},$ so the number is $4\cdot\binom32+4\cdot\binom22=16.$

There are $4$ factors divisible by $16$ and none divisible by $32,$ so the final answer is $90+40+16+4=\boxed{150}.$


Hint: In general, there are $20-n$ pairs of integers $(a, b)$ that differ by $n$ because we can let $b$ be any integer from $n+1$ to $20$ and set $a$ equal to $b-n$. Thus, the product is $(1^{19})(2^{18})\cdots(19^1)$ (or alternatively, $19! \cdot 18! \cdots 1!$.).

When we count the number of factors of $2$, we have $4$ groups, factors that are divisible by $2$ at least once, twice, three times and four times. For those numbers, take the exponent corresponding to each one of them, add them case by case and then totally add them. Hope it helps.


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.