# 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. –  BirdKiller1989 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}$.

-

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

-