Originally Posted by

**JeffM**
I have a proof, but it is hardly elegant. But it turns into a fairly simple procedure, which is easily extended to product II.

[tex]n \text { is a positive integer.}[/tex]

[tex]\text {DEFINE: } k = \left \lfloor \dfrac{n}{5} \right \rfloor \text { and } m = n - 5k.[/tex]

[tex]\therefore k \text { and } m \text { are integers, } n = 5k + m \text {, and } m = 1,\ 2,\ 3,\ \text { or } 4.[/tex]

[tex]\text {DEFINE integers } x \text { and } y \text { such that (i) } 5x + 3y = n \text {, (ii) } x \ge 0 \le y \text {, and}[/tex]

[tex]\text {(iii) if integers } a \text { and } b\ \exists \text { such that}[/tex]

[tex]\text{(1) } 5a + 3b = n \text { and ( 2) } 0 \le b \ne y \text {, then } a + b > x + y.[/tex]

Note that x and y may not exist for every value of n.

We need three lemmas. LEMMA 1 states that if y exists, then y = 0, 1, 2, 3, or 4. Proof follows.

[tex]\text {ASSUME non-negative integers } x \text { and } y \ \exists \implies 5x + 3y = n.[/tex]

[tex]\text {ASSUME } y \ge 5.[/tex]

[tex]\text {Let } a = x + 3 \text { and } b = y - 5 \implies a \text { and } b \text { are integers such that }[/tex]

[tex]5a + 3b = 5x - 15 + 3y + 15 = 5x + 3y = n \text { and } 0 \le b \ne 5.[/tex]

[tex]\text {By definition then, } a + b > x + y.[/tex]

[tex]\text {BUT } a + b = (x + 3) + (y - 5) = (x + y) - 2 < x + y \text {, a CONTRADICTION.}[/tex]

[tex]\therefore y \not \ge 5 \implies y = 0,\ 1,\ 2,\ 3, \text { or } 4\ \because \text { by definition } y \text { is an integer } \ge 0.[/tex]

LEMMA 2 states that if x exists, it does not exceed k. Proof follows.

[tex]\text {ASSUME non-negative integers } x \text { and } y \ \exists \implies 5x + 3y = n.[/tex]

[tex]\text {ASSUME } x \ge k + 1 \implies 5x + 3y \ge 5(k + 1) + 3y \implies n \ge 5k + 5 + 3y \implies[/tex]

[tex]5k + m \ge 5k + 5 + 3y \implies 0 > m - 5 \ge 3y \implies y \not \ge 0\ \because \ m \le 4.[/tex]

[tex]\text { BUT, by definition } y \ge 0 \text {, a CONTRADICTION.}[/tex]

[tex]\therefore x \not \ge k + 1 \implies x < k + 1 \implies x \le k\ \because \text { by definition } x \text { is an integer.}[/tex]

LEMMA 3 states that if x exists, it is k - 2, k - 1, or k. Proof follows.

[tex]\text {ASSUME non-negative integers } x \text { and } y \ \exists \implies 5x + 3y = n.[/tex]

[tex]\text {ASSUME } x \le k - 3 \implies 5x + 3y \le 5(k - 3) + 3y \implies n \le 5k - 15 + 3y \implies[/tex]

[tex]5k + m \le 5k - 15 + 3y \implies 15 \le m + 15 \le 3y \implies 5 \le y\ \because \ 0 \le m.[/tex]

[tex]\text {BUT, by LEMMA 1, } y \le 4 \text {, a CONTRADICTION.}[/tex]

[tex]\therefore x \not \le k - 3 \implies x > k - 3 \implies x \ge k - 2\ \because \text { by definition } x \text { is an integer.}[/tex]

[tex]\text {By LEMMA 2, } x \le k \implies x = k - 2,\ k - 1, \text { or } k \ \because \text { by definition } x \text { is an integer.}[/tex]

Putting our lemmas together, there are exactly fifteen potential possibilities, and, by brute force, we can find x and y (if they exist) by examining all fifteen of them.

[tex]\text {I: } x = k - 2 \text { and } y = 0 \implies n = 5x + 3y = 5k - 10 \implies m = -\ 10 \text { FALSE.}[/tex]

[tex]\text {II: } x = k - 2 \text { and } y = 1 \implies n = 5x + 3y = 5k - 10 + 3 \implies m = -\ 7 \text { FALSE.}[/tex]

[tex]\text {III: } x = k - 2 \text { and } y = 2 \implies n = 5x + 3y = 5k - 10 + 6 \implies m = -\ 4 \text { FALSE.}[/tex]

[tex]\text {IV: } x = k - 2 \text { and } y = 3 \implies n = 5x + 3y = 5k - 10 + 9 \implies m = -\ 1 \text { FALSE.}[/tex]

[tex]\text {V: } x = k - 2 \text { and } y = 4 \implies n = 5x + 3y = 5k - 10 + 12 \implies m = 2 \text { OK.}[/tex]

[tex]\text {VI: } x = k - 1 \text { and } y = 0 \implies n = 5x + 3y = 5k - 5 \implies m = -\ 5 \text { FALSE.}[/tex]

[tex]\text {VII: } x = k - 1 \text { and } y = 1 \implies n = 5x + 3y = 5k - 5 + 3 \implies m = -\ 2 \text { FALSE.}[/tex]

[tex]\text {VIII: } x = k - 1 \text { and } y = 2 \implies n = 5x + 3y = 5k - 5 + 6 \implies m = 1 \text { OK.}[/tex]

[tex]\text {IX: } x = k - 1 \text { and } y = 3 \implies n = 5x + 3y = 5k - 5 + 9 \implies m = 4 \text { OK.}[/tex]

[tex]\text {X: } x = k - 1 \text { and } y = 4 \implies n = 5x + 3y = 5k - 5 + 12 \implies m = 7 \text { FALSE.}[/tex]

[tex]\text {XI: } x = k \text { and } y = 0 \implies n = 5x + 3y = 5k \implies m = 0 \text { OK.}[/tex]

[tex]\text {XII: } x = k \text { and } y = 1 \implies n = 5x + 3y = 5k + 3 \implies m = 3 \text { OK.}[/tex]

[tex]\text {XIII: } x = k \text { and } y = 2 \implies n = 5x + 3y = 5k + 6 \implies m = 6 \text { FALSE.}[/tex]

[tex]\text {XIV: } x = k \text { and } y = 3 \implies n = 5x + 3y = 5k + 9 \implies m = 9 \text { FALSE.}[/tex]

[tex]\text {XV: } x = k \text { and } y = 4 \implies n = 5x + 3y = 5k + 12 \implies m = 12 \text { FALSE.}[/tex]

Thus, of the fifteen potential possibilities, only five are actual possibilities, namely V, VIII, IX, XI, and XII. Furthermore, each matches to a different possible value of m, and therefore we can reverse them. We can also see that if k = 0, only XI and XII result in a non-negative x so that V, VIII, and IX are impossible if n < 5. (That accounts for the lack of solutions if n = 1, 2, or 4.) Finally, if k = 1, V results in a negative x so that V is impossible if n < 10. (That accounts for the lack of a solutions if n = 7.)

So we have proved that there are solutions for x and y if n > 7 or if n = 3, 5, or 6. And the solutions can be found by the following algorithm, which is a fairly simple procedure.

[tex]m = 0 \implies x = k \text { and } y = 0.[/tex] XI

[tex]m = 1 \implies x = k - 1 \text { and } y = 2.[/tex] VIII

[tex]m = 2 \implies x = k - 2 \text { and } y = 4.[/tex] V

[tex]m = 3 \implies x = k \text { and } y = 1.[/tex] XII

[tex]m = 4 \implies x = k - 1 \text { and } y = 3.[/tex] IX

EDIT: It occurs to me that you might be interested in minimizing the number of packages even if one package is not completely filled. Calculate k and m as above. If m = 0, use k packages of size 5. If m = 1, 2, or 3, use k packages of 5 and and 1 package of size 3. If m = 4, use k + 1 packages of size 5.

## Bookmarks