4
$\begingroup$

Let n be a natural number, then,

1.) Probability that ⁿC₇ is divisible by 7. This one I could solve by observing a pattern in by writing 7 consecutive digits, I observed that for every 7 consecutive natural numbers starting from 7, there was only 1 value of n which made ⁿC₇ divisible by 7. Hence, the required probability was 1/7.

Edit 1: I realised that I did a mistake while calculating and got the answer by mistake, but the answer given in the book is 1/7 .

Edit 2: as pointed out in the comments, that for the condition doesn't hold true for any n<49, I did some rigorous calculation and found that all natural numbers from 49≤n<98 , only 7 satisfy the given condition . I found the same for the next 49 numbers. Can this be generalised to all natural numbers? This gives the probability 7/49 , = 1/7.

2.) Probability that ⁿC₇ is divisible by 12. I tried this the same way I did the above question but couldn't see any simple pattern for 12.

Is there a general, more elegant way to solve these kind of problems?

$\endgroup$
16
  • 1
    $\begingroup$ Use your method for $3$ and $4$, and combine them. $\endgroup$
    – Trebor
    Apr 30, 2019 at 6:25
  • 3
    $\begingroup$ Technically, you can't talk about probabilities without first having a distribution. How is $n$ chosen, exactly? $\endgroup$
    – Arthur
    Apr 30, 2019 at 6:39
  • $\begingroup$ I'd like to know how you came up with your answer for 1). Because for all natural numbers $n\le 48$, $n$ choose $7$ is not divisible by $7$. $\endgroup$
    – WaveX
    Apr 30, 2019 at 6:48
  • $\begingroup$ Agree with Arthur. There is no "natural" distribution because the uniform distribution fails on a countable set. We can try and calculate $\lim_{m\to\infty}p_m$, with $p_m$ being the prescribed probability when $n$ is limited to the range $1..m$. $\endgroup$ Apr 30, 2019 at 6:58
  • $\begingroup$ Anyway, Lucas's theorem and Kummer's theorem will surely come in handy. $\endgroup$ Apr 30, 2019 at 7:00

1 Answer 1

4
$\begingroup$

Translating a solution to the first question from an approach based on Lucas's theorem to high school level language.

Write $n$ in base $7$. So $$ n=\sum_{i=0}^m a_i 7^i, $$ where $a_i\in \{0,1,2,3,4,5,6\}$ for all $i$. Then I make the

Claim: The binomial coefficient $\binom n 7$ is divisible by $7$ if and only if $a_1=0$.

To make the meaning of this clear consider the following examples: $$ \begin{array}{c|c|c|c} n&\text{$n$ in base $7$}&\binom n7&\text{remainder of $\binom n7$ modulo $7$}\\ \hline 6&006_7& 0&0\\ 11&014_7&330&1\\ 18&024_7&31824&2\\ 50&101_7&99884400&0\\ 55&106_7&202927725&0 \end{array} $$ You see how the second to last "digit" in the base $7$ plays a role. To make things simpler I adopted the convention that $\binom nk=0$ whenever $0\le n<k$. This won't change the end result. Lucas's theorem would actually say that $\binom n7-a_1$ will always be divisible by seven, and you see that to be the case from the data in the last column.

Proof. Recall that $$ \binom n7=\frac{n!}{7!(n-7)!}=\frac{n(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)}{7\cdot6\cdot5\cdot4\cdot3\cdot2}.\qquad(*) $$ We see that in the prime factorization of the denominator the prime $7$ appears with multiplicity one; the other factor $6\cdot5\cdot4\cdot3\cdot2=720$ is not divisible by $7$.

Let's turn our attention to the numerator. It is the product of seven consecutive integers. So exactly one of those factors is divisible by seven, and the rest are not. A moment's reflection shows that the interesting factor is $n-a_0$. Its factor $7$ is cancelled by the $7$ in the denominator. This is just as well for we knew in advance that the binomial coefficient is an integer. Meaning that some factor of the numerator must cancel it. Anyway, for our purposes the more relevant observation is that the quotient $(*)$ is divisible by $7$ if and only if $n-a_0$ is divisible by $7^2$. But, $$ n-a_0=\sum_{i=1}^ma_i7^i=7a_1+7^2a_2+\cdots+7^ma_m. $$ All the other terms on the right are divisible by $7^2$ except possibly the first one. Therefore that first term is the key. Guess what! It is divisible by $7^2$ if and only if $a_1=0$. QED

The answer follows from this. $\binom n 7$ is divisible by seven for exactly $7$ choices of $n$ in any interval of length $49$. In the range $[0,48]$ only $n=0,1,2,\ldots,6$ work. In the range $[49,97]$ only $n=49,50,\ldots,55$ work et cetera.

This means that it is sensible to say that the probability of $\binom n 7$ being divisible by seven is $1/7$.

A more precise formulation could be given in terms of the ratio of the good cases / all the cases when $n$ is constrained to the range $[0,N]$, and we then let $N\to\infty$.


The other problem can be dealt with similarly. Leaving the following as exercises to you. They are more complicated than the claim above, but you can try your hand at this now that you know what you need to show.

  • $\binom n7$ is divisible by three unless the remainder of $n$ modulo $9$ is either $7$ or $8$ (probability $P_1=7/9$).
  • $\binom n7$ is divisible by four unless the remainder of $n$ modulo $16$ is $7$, $11$ or $15$ (probability $P_2=13/16$).
  • $\binom n7$ is divisible by $12$ if and only if it is divisible by both three and four. The two probabilities are independent from each other, so the final answer to the second question is $P=P_1P_2=91/144$.

The difficulties come from the fact that there will be several factors in the numerator divisible by a power of the relevant prime ($3$ and $2$ respectively). This leads to the need to study $n$ modulo $3^2$ and $2^4$ in the respective cases.

Good luck!

$\endgroup$
1
  • $\begingroup$ Can there be some other soln? $\endgroup$ Mar 30, 2020 at 8:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .