4
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ but this problem is so apt for generating functions... in fact, I recall this being in a combinatorics ebook I read a while back... $\endgroup$ – oldrinb Aug 30 '13 at 3:45
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

We want to count the number of solutions in integers of

$2 x_1 + 5 x_2 + x_3 + x_4 = n$ subject to $x_i \ge 0$ for all $i$, $x_3 \le 4$ and $ x_4 \le 1$.

As suggested by @oldrinb, this problem has an elegant solution via generating functions. Let $a_n$ be the number of solutions, and define $f(x) = \sum_{n=0}^{\infty} a_n x^n$. Then "clearly" we have

$f(x) = (1+x^2+x^4+\dots) (1+x^5+x^{10}+\dots) (1+x+x^2+x^3+x^4) (1+x)$

$= \frac{1}{1-x^2} \cdot \frac{1}{1-x^5} \cdot \frac{1-x^5}{1-x} \cdot (1+x)$

$= (1-x)^{-2}$

$= \sum_{n=0}^{\infty} (n+1) x^n$

So $a_n = n+1$.

Given the simplicity of the result and the OP's request for a non-GF solution, we seek a combinatorial proof that the number of solutions is $n+1$. To that end, suppose $n \ge 0$ is given. Consider one of the $n+1$ pairs $(i, n-i)$, $i = 0, 1, 2, \dots ,n$. There are unique non-negative integers $x_1$ and $x_4$, $x_4 \le 1$, such that $2 x_1 + x_4 = i$. And there are also unique non-negative integers $x_2$ and $x_3$, $x_3 \le 4$, such that $5 x_2 + x_3 = n-i$. Then $2 x_1 + 5 x_2 + x_3 + x_4 = i + (n-i)= n$. Given a solution of the equation, we can also easily generate the pair $(i, n-i)$; so we have a bijection between the solutions of the equation and the $n+1$ pairs $(i, n-i)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy