4
$\begingroup$

"How many of the numbers (200 Choose k), where k is an element of the set {0,1,2,3,4,....,200} are divisible by 3? "

Here is my thinking:

(200 Choose 0,1, and 2) are not multiples of 3 but every next combination has at least 1 multiple of 3 in the numerator therefore making the number divisible by 3. Since there are 201 numbers from 0 to 200, and 3 numbers (0,1, and 2) do not work, there are 198 numbers k.

Is this answer right and is this the right method?

$\endgroup$
  • 1
    $\begingroup$ If $k=9n+r$ , with $r\in\{0,1,2\}$ , then $200\choose k$ does NOT divide through $3$. $\endgroup$ – Lucian Dec 7 '13 at 21:17
  • 1
    $\begingroup$ You must also consider the factors of $3$ in the denominator. $\binom{200}9$ is not divisible by $3$. It’s equal to $$\frac{200\cdot199\cdot\ldots\cdot192}{9!}\;,$$ where the multiples of $3$ in the numerator are $198,195$, and $192$, while those in the denominator are $9,6$, and $3$. There are $4$ factors of $3$ in each, so there are no factors of $3$ in the binomial coefficient. $\endgroup$ – Brian M. Scott Dec 7 '13 at 21:19
  • $\begingroup$ Where did you get $k = 9n+r$ from? $\endgroup$ – user113027 Dec 7 '13 at 21:20
  • 1
    $\begingroup$ Using J I get that there are 36 $k$'s for which $\binom{200}{k}$ is not divisible by 3. They are: 0 1 2 9 10 11 27 28 29 36 37 38 81 82 83 90 91 92 108 109 110 117 118 119 162 163 164 171 172 173 189 190 191 198 199 200. I used these lines of code (respectively): 201-+/0=3|!&200x i.201 and (#~(-.@(0&=)@(3&|)@(!&200x))) i.201. $\endgroup$ – rubik Dec 7 '13 at 21:23
  • $\begingroup$ Those calculations confirm @Lucian statement. $\endgroup$ – rubik Dec 7 '13 at 21:29
2
$\begingroup$

According to Lucas' theorem, a binomial coefficient $\binom{m}{n}$ is divisible by a prime p if and only if at least one of the base p digits of n is greater than the corresponding digit of m.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

$\newcommand{\dcc}[1]{\left\lfloor#1\right\rfloor}$ We know from Legendre's theorem that the power of a prime $p$ in $n!$ is equal to $\sum_{a=1}^\infty \dcc{\frac{n}{p^a}}$. See, for example, Wikipedia, ProofWiki; you can easily find many online resources and books where this result is explained.

We are interested in the power in which the prime 3 appears in the number $\binom{200}k=\frac{200!}{(200-k)!k!}$.

The multiplicity of 3 in 200! is $$\dcc{\frac{200}3}+\dcc{\frac{200}9}+\dcc{\frac{200}{27}}+\dcc{\frac{200}{81}}.$$ We want to compare this number with $$\dcc{\frac{200-k}3}+\dcc{\frac{200-k}9}+\dcc{\frac{200-k}{27}}+\dcc{\frac{200-k}{81}} +\dcc{\frac{k}3}+\dcc{\frac{k}9}+\dcc{\frac{k}{27}}+\dcc{\frac{k}{81}},$$ which is the multiplicity in which $3$ appears in $(200-k)!k!$.

Since $\dcc a +\dcc b\le\dcc{a+b}$, we have $$ \begin{align*} \dcc{\frac{k}3}+\dcc{\frac{200-k}3} &\le \dcc{\frac{200}3}\\ \dcc{\frac{k}9}+\dcc{\frac{200-k}9} &\le \dcc{\frac{200}9}\\ \dcc{\frac{k}{27}}+\dcc{\frac{200-k}{27}} &\le \dcc{\frac{200}{27}}\\ \dcc{\frac{k}{81}}+\dcc{\frac{200-k}{81}} &\le \dcc{\frac{200}{81}} \end{align*} $$ We want to find the values of $k$ for which at least one of these inequalities are strict.

It is useful to notice that the value $\dcc{\frac{k}3}+\dcc{\frac{200-k}3}$ is the same for all $k$'s in the same residue class modulo 3. So it suffices to check $k=0,1,2$ and we see that $$\dcc{\frac{k}3}+\dcc{\frac{200-k}3} = \dcc{\frac{198}3} = \dcc{\frac{200}3}$$ for any $k$. (We tried $k\equiv 0,1,2\pmod3$).

For 9 we get $$\dcc{\frac{k}9}+\dcc{\frac{200-k}9}= \begin{cases} \frac{198}9=22=\dcc{\frac{200}9} & \text{for }k\equiv0,1,2 \pmod9, \\ \frac{191}9=21<\dcc{\frac{200}9} & \text{for }k\equiv3,4,\dots,8 \pmod9 \end{cases} $$

For 27 we get $$\dcc{\frac{k}{27}}+\dcc{\frac{200-k}{27}}= \begin{cases} \frac{189}{27}=7=\dcc{\frac{200}{27}} & \text{for }k\equiv0,1,2,\dots,11 \pmod{27}, \\ \frac{162}{27}=6<\dcc{\frac{200}{27}} & \text{for }k\equiv12,13,\dots,26 \pmod{27} \end{cases} $$

For 81 we get $$\dcc{\frac{k}{81}}+\dcc{\frac{200-k}{81}}= \begin{cases} \frac{162}{81}=2=\dcc{\frac{200}{81}} & \text{for }k\equiv0,1,2,\dots,38 \pmod{81}, \\ \frac{81}{81}=1<\dcc{\frac{200}{81}} & \text{for }k\equiv39,\dots,80 \pmod{81} \end{cases} $$

So the numbers which $k$ for which $\binom{200}k$ is not divisible by $3$ are precisely the numbers which simultaneously fulfill the conditions $$ \begin{align*} k&\equiv0,1,2 \pmod9\\ k&\equiv0,1,2,\dots,11 \pmod{27}\\ k&\equiv0,1,2,\dots,38 \pmod{81} \end{align*} $$ The first two conditions are fulfilled if $k\equiv0,1,2,9,10,11\pmod{27}$. If we add the third condition, we get that this holds for $$ k \equiv 0,1,2,9,10,11,27,28,29,36,37,38 \pmod{81}$$ This gives us the 36 possible values $k= 0,1,2,9,10,11, 27,28,29,36,37,38, 81,82,83,90,91,92, 108,109,110,117,118,119, 162,163,164,171,172,173, 189,190,191,198,199,200$.

This coincides with the calculations mentioned in this comment.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

See for example N. J. Fine, Binomial coefficients modulo a prime, Am. Math. Monthly 54 (10) (1947) 589-592, http://www.jstor.org/stable/2304500 . See also D. Singmaster, Divisibility of binomial and multinomial coefficients by primes and prime powers, http://www.fq.math.ca/Books/Collection/singmaster.pdf .

| cite | improve this answer | |
$\endgroup$

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.