# Counting, Combinations

Stuck here :( What's the number of ways a person can score 60 total points from taking 4 tests given that 3 of 4 tests each have maximum score of 50 points and other test a maximum score of 100 points?

My strategy is to enumerate all ways in which scores from each exam sum up to 60 points. Is there some efficient way to do this?

-
Doing this by brute force is going to take forever. Try to start off by finding an equation between the four tests and the goal of 60 points. This should give you some possible ways to solve the problem. – BirdKr Jun 21 '14 at 9:44

This can be viewed as finding the number of non-negative integer solutions of the equation $x_1+x_2+x_3+x_4=60$, with the proviso that $x_1$,$x_2$, and $x_3$ are $\le 50$.

We solve the problem using the Stars and Bars procedure. I prefer to think of it as distributing $60$ identical candies between $4$ kids, with the proviso that none of the first $3$ kids gets more than $50$ candies.

With no such restriction, the number of ways is $\binom{60+4-1}{4-1}$.

From this we must subtract the bad ways, where one of the first three kids gets $51$ or more candies. How many ways if the first kid gets $51$ or more? Give her $51$ candies to start with.Then distribute the remaining $9$ among the $4$ kids (so the first kid may get additional candies). This can be done in $\binom{9+4-1}{3}$ ways. So the total number of "bad" ways is $3\binom{12}{3}$. It follows that the number of ways to distribute the marks between the tests is $\binom{63}{3}-\binom{12}{3}$.

-
Nicolas , Is the data fourth test have maximum marks 100 superfluous? If yes then anything other than 100 and greater than 50 will not change the final solution.Is it given to confuse students? – rugi Apr 7 at 5:22
The solution I gave is slightly sneaky. I basically first made no explicit limit on the score obtainable in any test, just found the number of ways to get a total of $60$. (This is the same as the number of ways if all tests have a maximum of $60$ available marks.) Then I removed the "bad" ways, where marks of $51$ or more are assigned on one of the first three tests. On the last test, it would not change the answer if the max on the last test was anything from $61$ up. – André Nicolas Apr 7 at 5:36

(I'm assuming only non-negative integer values for scores, doesn't matter how you get the scores, and the three 50-max tests are distinguishable.)

Hint: This problem reduces [how?] to the somewhat easier case of finding the number of ways a person can score $k$ points on three tests which have a maximum score of $50$, for arbitrary $0\leq k\leq 60$.

For the reduced problem, imagine you have $k$ points and are trying to distribute them among the tests. This is the same as choosing how to break a row of $k$ blocks into three pieces. If you've not seen problems like this before, you might get some intuition by drawing some pictures for these broken rows for medium values of $k$, or enumerating all of them for tiny values of $k$.

-