4
$\begingroup$

The question (from an NTA sample paper for JEE Main) -

If $p, q, r \in \Bbb N $, then the number of points having position vector $p\hat{i} + q\hat{j} +r\hat{k}$ such that $8 \leq p + q + r \leq 12$ are:

It is evident that I had to essentially find the integral solutions for the inequalities given. I couldn't solve it in time and moved on. However upon reviewing the explanation and key concepts of the answer, I came out more perplexed and need help.

They explain that you have to add the no. of solutions for $p+q+r = 8, 9, 10, 11, 12$. and also $p,q,r \geq{1}$. I knew how to solve for $p,q,r \geq{0}$ using the "Beggar's method/ Fencing method", but did not know how to solve this case.

They used the formula, required number of positive integral solutions = ${n-1}\choose{r-1}$ and have written the solution as: $${7\choose2} + {8\choose2} + {9\choose2} + {10\choose2} + {11\choose2} = 185$$

Makes sense, but here's the stuff that baffles me:

The number of integral solutions of $x_1 + x_2 + \ldots + x_r = n$, where $x_1 \geq 1, x_2 \geq 1, \ldots, x_r \geq 1 $ is the same as the number of ways to distribute n identical things among r persons getting at least 1. This is also equal to the coefficient of $x^n$ in $(x^1 + x^2 + \ldots )^r$ = coefficient of $x^n$ in $ x^r (1-x)^{-r}$ = coefficient of $x^{n-r}$ in $\{1 + rx + \frac{r(r+1)}{2!}x^2 + \cdots + \frac{r(r+1)(r+2)\ldots(r+n-1)}{n!}x^n + \ldots \}$
= $\frac{(n-1)!}{(n-r)!(r-1)!}$ = ${n-1 \choose r-1}$

They've also explained the case for $x \geq 0$ in a very similar manner above this, instead talking about coefficient of $x^n$ in $(1-x)^{-r}$. I'm struggling to understand what this means and how it ties in to combinations. I understand how the binomial theorem for natural indices uses combinations in effect to find the coefficient so I can see how they might also be important here, but there are a few things I'm not able to get here.

How can I solve this problem in an intuitive way (like the $x_i \geq 0$ case)? What do the coefficient of $x^n$ have to do with this at all? Any help is much appreciated.

$\endgroup$
2
$\begingroup$

The formula they use is the same as Theorem One from Stars and Bars.

This is proved by considering $k$ fences that lie strictly within the fields, and only one fence between each pair of fields.

The 'zero-option' allows for fences to be placed outside the fields, and also more than one together, creating 'empty spaces'.

The generating function (GF) used is:

$$(x^1 + x^2 + \ldots )^r$$

For the zero-option, we would use:

$$(1 + x + x^2 + \ldots )^r$$

and for example if there were to be at least two fields between fences, we would use:

$$(x^2 +x^3 + \ldots )^r$$

These all go into the binomial expansion, and we look for the coefficients of $x^n, x^{n-r}, x^{n-2r}, \dots$, depending on the minimum value of $x_i$ allowed.

Which is like giving the minimum values to each player, do a zero-based stars and bars, and then give this as extra to each player.

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

I guess I can help you by providing another way to think about the whole $n$ identical things being distributed among $r$ people.

So, imagine you have $n$ identical objects to be distributed in $r$ groups and you plan to do so by putting partitions/walls between them. Since there are $n$ objects, you've got $n-1$ spaces to put that partition, if you don't want any group to have $0$ objects(that is similar to saying that $x_i\geq1$). Also, since you want $r$ groups, the number of partitions you need to use is $r-1$.

Now, it breaks down to a simple Permutation Combination problem. Choose $r-1$ spaces/points from $n-1$, i.e. $$n-1\choose r-1$$ which gives you the "number of possible solutions under given constraint".

Also, the questions with a given constraint like $x_i\geq1$ have their branches in the Multinomial Theorem which is not a part of JEE Mains (I suppose) and given that NTA has placed a few questions which are way out of JEE Mains syllabus in there tests, you can surely move on.

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

If you suppose $p+q+r=8$ then they are natural numbers, so you can replace them with $x+1$, $y+1$ and $z+1$. Your new equation is $x+y+z=5$. The number of solutions is $7\choose2$. Similarly for remaining values, you will get the rest.

| 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.