Here's a diabolical math problem that I found.
In how many ways can we fill a bag with n fruits subject to the following constraints?
• The number of apples must be even.
• The number of bananas must be a multiple of 5.
• There can be at most four oranges.
• There can be at most one pear.
This problem is purely for recreational purposes, but I prefer to see a solution that involves "pure" counting, and not generating functions.
Best Answer
Here's a tedious 'solution by counting'.
Let $S_{op}(n)$ denote the number of solutions to the original problem. Let $S_o(n)$ denote the solution to the problem, except no pears are included in the bag. Let $S(n)$ denote the solution to the problem with no pears or oranges in the bag, which is to say, $S(n)$ is the number of nonnegative integer solutions $(a,b)$ to the equation $$2 a + 5 b = n $$
Notice that $$S_{op}(n) = S_o(n) + S_{o}(n-1)$$, as we count in the first summand how many ways there are to bag exactly $n$ fruits with no pears, and in the second summand we count how many ways there are to bag $n-1$ fruits with no pears, it being implicit that we intend to sneak a pear in afterwards to make a full $n$.
In a similar vein, $$ S_o(n) = S(n) + S(n-1) + \cdots + S(n-4) $$ In doing so, we have shown $$ S_{op}(n) = S(n) + 2 \sum_{k = 1}^4 S(n- k) + S(n-5) $$ where, to make the formula true in all cases (for small $n$), we adopt the convention $S(n) = 0$ for $n = 1,0,-1,\cdots$.
We now count $S(n)$; I derived that we have $$ S(n) = \begin{cases} \left\lfloor \frac{n}{5} \right\rfloor & n \text{ odd} \\ \left\lfloor \frac{n}{5} \right\rfloor + 1 & n \text{ even} \end{cases} $$ Putting all this together gives a solution to the original problem $S_{op}(n)$.