1

I'm trying to answer the following question:

The boxes Banana Ltd. uses to ship bananas come in two sizes, one that holds three bananas and one that holds five bananas. The company promises to ship at least as many bananas as you order. Show using induction that the company can fulfil any order for nine or more bananas exactly.

The only thing I've been able to come up with is an equation: $3x + 5y = n$ where $n$ refers to the number of bananas ordered.

Also for the cases where the number of bananas ordered is less than $9$, it is obvious that the company will be able to ship at least as many bananas as ordered.

I am unsure on how to proceed from here.

EDIT:

Since the OP, I have done the following:

$3x + 5y = n$

$3x +5y + 1= n+1$

$3x+5y + 6-5 = n+1$

$3x +5y + 2*3 - 5 = n+1$

$3(x + 2) + 5(y-1) = n+1$

Therefore, if $y \ne 0$, then $x+2$ 3-capacity boxes and $y-1$ 5-capacity boxes can be used to fulfil an order of size $n+1$.

bawse
  • 325
  • 1
    How about considering as the base case that the company can ship $9$, $10$ and $11$ bananas? Then prove that for $n\geq 9$, if the company can ship $P(n)$, $P(n+1)$, and $P(n+2)$ bananas, then it can also ship $P(n+3)$, $P(n+4)$, and $P(n+5)$ bananas. – Mankind Sep 16 '15 at 09:48
  • 1
    By the way, the Frobenius problem is related to this: https://en.wikipedia.org/wiki/Coin_problem It says that you can ship any number of bananas of at least $5\cdot 3 - 5 - 3 + 1 = 8$ in number. – Mankind Sep 16 '15 at 09:50
  • Why do we need to also prove $P(n+2)$ for this particular problem? – bawse Sep 16 '15 at 09:55

1 Answers1

2

You’re supposed to assume that the cases are always shipped completely filled. Thus, there’s no way for the company to satisfy an order for $1,2,4$, or $7$ bananas. It can fill an order for $8$, by shipping a $3$ and a $5$, or an order for $9$, by shipping three $3$s.

HINT: Suppose that it can fill an order for $n$ bananas; i.e., there are non-negative integers $k$ and $\ell$ such that $3k+5\ell=n$.

  • Can it fill an order for $n+3$ bananas?
  • Wev’e seen that it can fill orders for $8$ or $9$ bananas. Can it fill an order for $10$?

If you answer those two questions correctly, you have the necessary pieces for a proof by induction. It doesn’t go from $n$ to $n+1$; it goes from $n$ to ... ? And it has more than one base case.

Further help, spoiler-protected:

Once you’ve verified that they can send $8,9$, or $10$ bananas, you can keep adding boxes of $3$ to get any larger number. If you want to be more formal about it, you can show by three inductions on $n$ that they can send $3n+2$ for any $n\ge 2$, $3n$ for any $n\ge 3$, and $3n+1$ for any $n\ge 3$. Since every integer can be written in one of these three forms, ...

Brian M. Scott
  • 616,228
  • I have added an edit into the OP, is this what you were suggesting? – bawse Sep 16 '15 at 09:53
  • @cp101020304: No, because $y-1$ may be negative. Don’t try to go in steps of $1$. Use $k$ starting points and go in steps of $k$ for some $k>1$; my answer points you towards the right $k$. – Brian M. Scott Sep 16 '15 at 09:55
  • Okay, so is there a particular reason why the first question is if it can fulfil an order for $n+3$ bananas? – bawse Sep 16 '15 at 09:59
  • @cp101020304: Yes, there is, but I’d rather not give it outright, at least not yet, because it very nearly completes the proof. Can you answer that question? – Brian M. Scott Sep 16 '15 at 09:59
  • $3x + 5y + 3 = n+3$.

    $3(x+1) + 5y = n+3$.

    Something like that? It is quite intuitive that if we have some arbitrary n (e.g $9$), then $n+3$ can be fulfilled by having $4$ 3-capacity boxes.

     – bawse Sep 16 '15 at 10:03
  • @cp101020304: Yes: if there are integers $x,y\ge 0$ such that $3x+5y=n$, then clearly $3(x+1)+5y=n+3$, so if they can fill an order for $n$ bananas, they can fill one for $n+3$. Since they can fill one for $9$, it follows by induction that that they can fill one for $3k$ for any $k\ge 3$. That gives us $9,12,15,\ldots$; how do we get the rest? – Brian M. Scott Sep 16 '15 at 10:05
  • do the same thing for $n+2$ and $n+1$? – bawse Sep 16 '15 at 10:07
  • @cp101020304: That won’t work, because you can’t send a box of $2$ bananas or $1$ banana. Try thinking more in words and less in algebraic computation. The reason that we can go from $n$ to $n+3$ is that if we can somehow ship $n$ bananas, we can always send one more box of $3$ to make a total of $n+3$. The base case of $9$ gives us $9,12,15,\ldots$ as we keep adding another box of $3$. What if we start at $8$ and keep adding boxes of $3$? – Brian M. Scott Sep 16 '15 at 10:10
  • How can we start at $8$ if $n \ge 9$? We can start at 9 and send another box of $5$ to make a total of $n+5$, which will give us $9,14,19,...$ – bawse Sep 16 '15 at 10:13
  • @cp101020304: You can prove the stronger result that the company can actually fulfil any order for at least $8$ bananas; that certainly implies the desired result. Don’t bother adding boxes of $5$: apart from the ones that you use to send $8$ or $10$ bananas, you don’t need them, and not using them makes the proof shorter. – Brian M. Scott Sep 16 '15 at 10:15
  • Sure, so adding boxes of $3$ starting from $8$ will give us $8,11,14,17,...$. How does that prove that the company can fulfil any order $n \ge 8$? – bawse Sep 16 '15 at 10:18
  • 1
    @cp101020304: It doesn’t, because you’re not done yet. But look: you’ve now taken care of $8,9,11,12,14,15,17,18,20,21,\ldots$, so you’re missing $10,13,16,19,\ldots$. At this point you should be able to find a way to deal with them. – Brian M. Scott Sep 16 '15 at 10:20
  • I see! Thank you for bearing with me hahaha – bawse Sep 16 '15 at 10:22
  • @cp101020304: You’re welcome. – Brian M. Scott Sep 16 '15 at 10:23