1
$\begingroup$

Q: Find the number of positive integer solutions to the equation:

$$\begin{align} (x_1+x_2+x_3)(y_1+y_2+y_3+y_4)=77. \end{align}$$

The solution given is $\begin{pmatrix} 6\\2 \end{pmatrix}$ $\begin{pmatrix} 10\\3 \end{pmatrix}$$+$ $\begin{pmatrix} 10\\2 \end{pmatrix}$ $\begin{pmatrix} 6\\3 \end{pmatrix}$.

I am clueless as to how can I go about solving this, given that the method of solving this question should centre around the concepts of combinations, distribution problems and multisets, in particular the formulas for $r$ $\mathbb identical $ objects, $n$ $distinct$ boxes:

  1. Each box can hold at most 1 object:$$\begin{align} C_r^n = \begin{pmatrix} n\\r \end{pmatrix} \end{align}$$

  2. Each box can hold any number of obects: $$\begin{align} H_r^n = \begin{pmatrix} {r+n-1}\\r \end{pmatrix} \end{align}$$

  3. Each box must hold at least one object - Put 1 object in each box first: r-n objects left. Apply (2), then number of ways: $$\begin{align} \begin{pmatrix} {r-n+n-1}\\{r-n} \end{pmatrix} = \begin{pmatrix} {r-1}\\{n-1} \end{pmatrix}\end{align}$$

Some help will be deeply appreciated.

$\endgroup$
  • 1
    $\begingroup$ Factor $77$, what does this imply about the values of $(x_1 + x_2 + x_3)$ and $(y_1 + y_2 + y_3 + y_4)$? From there on, your knowledge of partitioning numbers and combinatorics should come in handy $\endgroup$ – J. Marx-Kuo Sep 23 '16 at 4:12
  • $\begingroup$ Is it something like what @Nick Peterson suggested below? $\endgroup$ – Stoner Sep 23 '16 at 5:59
  • $\begingroup$ Yes, his last sentence is especially important $\endgroup$ – J. Marx-Kuo Sep 23 '16 at 6:52
3
$\begingroup$

Hint:

You probably have specific examples of how to find the number of integer solutions to either $x_1+x_2+x_3=k$ or $y_1+y_2+y_3+y_4=k$, for any constant $k$. (If you don't: think about trying to distribute those $k$ $1$'s into boxes, such that each box gets at least one.)

To reduce there: note that $77=7\cdot11$, which are both prime. So, if $A\cdot B=77$, you must have one of:

  • $A=1$, $B=77$
  • $A=7$, $B=11$
  • $A=11$, $B=7$
  • $A=77$, $B=1$

Only two of these are possible with all $x_i$ and $y_j$ positive.

$\endgroup$
  • 1
    $\begingroup$ Oh @Nick Peterson do you mean $x_1+x_2+x_3=7$ and $y_1+y_2+y_3+y_4=11$ , for which in total there are 2 possibilities as stated above and so I have to consider all the aforementioned cases? (Since all $x_i, y_i > 0$) $\endgroup$ – Stoner Sep 23 '16 at 5:59
  • 1
    $\begingroup$ Alright I got it! Thank you for your suggestion! $\endgroup$ – Stoner Sep 23 '16 at 7:41

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.