2
$\begingroup$

How many nonnegative integer solutions are there to the equation $$A_1 + A_2 + A_3 + A_4 = 25$$ such that $A_1 \leq 12$ and $A_4 \leq 10$?

I am completely lost on how to solve such a question.
If someone could give me a detailed solution, I would greatly appreciate it.

$\endgroup$
8
  • 1
    $\begingroup$ I feel that there's a mistake in the phrasing of the question - what's $A_5$? $\endgroup$ – Eevee Trainer Dec 6 '18 at 6:25
  • 1
    $\begingroup$ Sorry about that, its fixed now $\endgroup$ – Steve Dec 6 '18 at 6:29
  • $\begingroup$ How many choices are their for A1? 12 (13 if you include 0 I suppose). How many choices are there for A4? 10? So how many pairs of A1 and A4 can you have? $\endgroup$ – DanielOnMSE Dec 6 '18 at 6:36
  • $\begingroup$ I'm not quite sure....The question was stated exactly as above. $\endgroup$ – Steve Dec 6 '18 at 6:40
  • $\begingroup$ @DanielOnMSE More is needed since have to assign $A_2,A_3.$ $\endgroup$ – coffeemath Dec 6 '18 at 7:04
1
$\begingroup$

We can think of it in this way:

We find all cases for the equation without restriction of $A_1\leq12$ and $A_4\leq10$. Then we fill in these cases with a 2-circle Venn Diagram, the first circle ($P$) with cases satisfying $A_1>12$ (yes, $>$), and the second circle ($Q$) with cases satisfying $A_4>10$. Then what we want to find is $P'\cap Q'$ i.e. $\xi - P - Q + P\cap Q$.

Now we have to solve for

$$A_1 + A_2 + A_3 + A_4 = 25\ \fbox*$$ when $\fbox1\ A_1>12\ (A_1\geq13)$, when $\fbox2\ A_4>10\ (A_4\geq10)$, and when $\fbox3$ both occurs.

From now, we think of those 4 "$A$"s as bins, and numbers as "balls".

For $\fbox*$

Using stars and bars we get ${28\choose3}=3276$

Case $\fbox1$

Then it's easy to eliminate the restriction. We fill in box $A_1$ with 13 balls, and then we get an equation we need to solve for (with no restrictions!): $$A_1 + A_2 + A_3 + A_4 = 12$$

Using stars and bars the answer is ${15\choose3}=455$

Case $\fbox2$

Similarly we get $$A_1 + A_2 + A_3 + A_4 = 14$$ and hence we get ${17\choose3}=680$

Case $\fbox3$

Similarly we get $$A_1 + A_2 + A_3 + A_4 = 1$$ and hence we get ${4\choose3}=4$

Hence we have $3276-455-680+4=2145$ which is what we want.$\ \square$

$\endgroup$
5
  • $\begingroup$ I understand your process, but i'm a bit confused about why you can't make a substitution for A1 and A2 after you make A1≥13 and A≥11 $\endgroup$ – Steve Dec 6 '18 at 16:16
  • $\begingroup$ yeah I can make a substitution of $x=A_1-13$ and $y=A_4-11$ (the process is similar) $\endgroup$ – Vee Hua Zhi Dec 7 '18 at 11:42
  • $\begingroup$ May I know where did you get this question (which topic are you studying) so I can give you a proof related to the topic? :) $\endgroup$ – Vee Hua Zhi Dec 7 '18 at 11:43
  • $\begingroup$ It was from a past midterm so i'm not exactly sure. But i've found that using generating functions to solve these problems are easier. $\endgroup$ – Steve Dec 7 '18 at 19:07
  • $\begingroup$ Well you can use generating functions by expanding $(\sum_{k=0}^{12}x^k)(\sum_{k=0}^{25}x^k)^2(\sum_{k=0}^{10}x^k)$ (I suggest doing it with WolframAlpha) $\endgroup$ – Vee Hua Zhi Dec 8 '18 at 3:49
1
$\begingroup$

Sum for $A_1$ from $0$ to $12$ aand $A_4$ from $0$ to $10$ of $25-A_1-A_4+1$ where the last part is from stars and bars for the possible values of $A_2,A_3.$ [There's only one bar.] If I entered it right it's $2145.$

It's lucky that $12+10=24\le 25$ here. [edit-- lucky that $12+10=22 \le 25.$]

More explanation: You can have any of the possible values up to $12$ for $A_1$ and up to $10$ for $A_4$ (including $0$ for each.) These are distinct possibilities for assigning two of the four letters. Once $A_1$ and $A_4$ have been assigned, the overall sum of $25$ needs $25-A_1-A_4$ more to go, between $A_2$ and $A_3$, and this can be completed in $[25-A_1-A_4+1]$ ways, hence that is the value summed.

One more thing-- I just put this sum in a calculator to get the number, but it may be possible to do it formally using sum formulas applied to parts of the thing summed.

$\endgroup$
2
  • $\begingroup$ yea that answer matches the answer key. But would it possible for you to make your solution more explicit? $\endgroup$ – Steve Dec 6 '18 at 7:27
  • $\begingroup$ @Steve Just added some explanation at end. $\endgroup$ – coffeemath Dec 6 '18 at 7:55

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.