1
$\begingroup$

A piece of art receives an integer mark from $0$ to $100$ for each of the categories design, technique and originality. In how many ways is it possible to score a total mark of $200$?

I got the answer of $5151$ by writing out some cases. Is there a faster way to do this?

$\endgroup$
  • $\begingroup$ You're looking for the number of integer solutions to $x_0 + x_1 + x_2 = 200$. See this post: math.stackexchange.com/questions/919676/… $\endgroup$ – Matti P. Mar 1 '19 at 8:43
  • $\begingroup$ The restriction in the question is that each group has a maximum. $\endgroup$ – Chris Ta Mar 1 '19 at 8:47
  • $\begingroup$ Welcome to MathSE. This tutorial explains how to typeset mathematics on this site. $\endgroup$ – N. F. Taussig Mar 1 '19 at 9:57
0
$\begingroup$

Since the marks can range from $0$ to $100$, we wish to solve the equation $$x_1 + x_2 + x_3 = 200 \tag{1}$$ in the nonnegative integers subject to the restrictions that $x_1, x_2, x_3 \leq 100$.

If there were no restrictions, then a particular solution of equation 1 corresponds to the placement of two addition signs in a row of $200$ ones.

Let's illustrate with the equation $y_1 + y_2 + y_3 = 10$.
$$1 1 1 1 + 1 1 1 1 1 + 1$$ corresponds to the solution $y_1 = 4$, $y_2 = 5$, $y_3 = 1$, while $$1 1 1 1 1 + + 1 1 1 1 1$$ corresponds to the solution $y_1 = 5$, $y_2 = 0$, $y_3 = 5$.

The number of solutions of equation 1 in the nonnegative integers is $$\binom{200 + 3 - 1}{3 - 1} = \binom{202}{2}$$ since we must choose which two of the $202$ positions required for $200$ ones and two addition signs will be filled with addition signs.

From these, we must subtract those solutions in which one of the variables exceeds $100$. Notice that at most one variable may exceed $100$ since $2 \cdot 101 = 202$. There are three ways to choose the variable that exceeds $100$. Suppose it is $x_1$. Then $x_1' = x_1 - 101$ is a nonegative integer. Substituting $x_1' + 101$ for $x_1$ in equation 1 yields \begin{align*} x_1' + 101 + x_2 + x_3 & = 200\\ x_1' + x_2 + x_3 & = 99 \tag{2} \end{align*} Equation 2 is an equation in the nonnegative integers with $$\binom{99 + 3 - 1}{3 - 1} = \binom{102}{2}$$ Hence, there are $$\binom{3}{1}\binom{101}{2}$$ solutions that violate the restrictions $x_1, x_2, x_3 \leq 100$.

Hence, the number of ways a total mark of $200$ can be obtained on three tests in which the maximum possible score is $100$ is $$\binom{202}{2} - \binom{3}{1}\binom{101}{2} = 5151$$ as you found.

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

Basically, we need to find out the number of solutions to $x_0+x_1+x_2=200$ with $0\leq x_i\leq 100$ for all $i$ and furthermore it should hold that $x_0+x_1\geq 100$

Once $x_0$ and $x_1$ are assigned, $x_2$ is automatically determined as $200-x_0-x_1$

Assigning $x_0=0$, there is only one choice for $x_1$ which is $100$

Assigning $x_0=1$, there are two choices for $x_1$, which are $99$ and $100$

Assigning $x_0=k$, there are $k+1$ choices for $x_1$, from $100-k$ to $100$

So, there are a total of $$\sum_{k=0}^{100}(k+1)=\sum_{k=1}^{101}k=\frac{101\times 102}2=5151$$ choices.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ +1. the answer by @N.F.Taussig is more general but you found a surprising (to me) way to exploit the fact that $100$ is exactly half of $200$. neat! $\endgroup$ – antkam Mar 1 '19 at 19:39

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.