0

Prompt: You want to cut a rectangular pan of brownies, made up of n square-shaped brownies, but you can only make horizontal or vertical cuts. Assuming you can only make one cut at a time, how many cuts will you need to split the pan into n individual brownies? Use strong induction to prove your answer.

I have no idea how to do this question but I assume it's using pigeonhole principle in the proof. Any help as to how I can solve this? I was thinking to start: The base case of 1 is either 1 slice horizontally or 1 slice vertically to get 2 brownies. Meaning your brownies created are determined by (number of cuts * 2). But I am not sure how to do a strong induction proof for this.

amWhy
  • 209,954
Marshal
  • 101
  • 7
  • 3
    Do the $n$ brownies have to be the same size? – Brian M. Scott Feb 25 '21 at 23:06
  • the n brownies can be any size or the same size, doesn't matter – Marshal Feb 25 '21 at 23:42
  • I don't think number of brownies is twice the number of cuts. Think about what you can do on the 4th cut. EDIT: I am so confused. How are these n brownie squares arranged in the baking tray? Also, it should be illegal to post about brownies at midnight when the reader has them in the fridge (just kidding) – Benjamin Wang Feb 25 '21 at 23:42
  • Do you need to use the whole pan? Or can there still be stuff left in the pan after taking out the n brownies? – Bram28 Feb 25 '21 at 23:48
  • you don't need to use the whole pan, just need to make n brownies – Marshal Feb 25 '21 at 23:49
  • @BenjaminWang Do not ever suggest an edit, commenting "edited only so I can change my vote." You wasted my time, and that of another reviewer, forced to review your fake edit. – amWhy Feb 26 '21 at 00:12
  • After thinking about it more, I think to start we do have to make a formula that relates number of cuts to number of brownies made. Would it be 2x+1, where x is the number of cuts made? – Marshal Feb 26 '21 at 00:19
  • @BenjaminWang clearly you are not helping at all – Marshal Feb 26 '21 at 00:21
  • 3
    I think https://math.stackexchange.com/questions/563271/cutting-a-rectangle-into-squares may answer this question. – Gerry Myerson Feb 26 '21 at 02:08
  • Here's the computer science version of the question: https://stackoverflow.com/questions/49743966/an-%C3%97-chessboard-is-to-be-cut-into-its-unit-squares – Gerry Myerson Feb 26 '21 at 02:13
  • It is unclear (given some comments) what a cut means - does a cut divide one existing "brownie" into two pieces, or does it extend the whole length or width of the tin, dividing any "brownie" in its path? Or can I use both kinds of cuts? – Mark Bennet Feb 26 '21 at 07:58
  • Suppose I just need one brownie. Since the pan is rectangular, it seems like I can make use of three sides, and thus with one cut create a square piece of brownie. However, do I still need to cut the brownie loose from the sides of the pan, in which case I need 4 cuts? – Bram28 Feb 26 '21 at 13:48
  • Also, suppose I don't need to cut the sides: Suppose the pan is a 3 x 2 pan. Then with one cut I get a 2x2 brownie, and with one more cut I get two 1x1 brownies, and so with two cuts I get three square brownies. However, it the pan is 5x2 I need three cuts to cut three brownies. And with a 2x2 pan I need no cuts at all to get 1 brownie, whereas with a 3x2 pan I need 1 cut to get 1 brownie .... My point is: doesn't the answer depend on the relative dimensions of the pan? – Bram28 Feb 26 '21 at 13:54
  • I also wonder what this "Assuming you can only make one cut at a time" bit is for .... I mean, it asks for the number of cuts I need to make, so whether I have to make these cuts one at a time or whether I can make multiple cuts at a time shouldn't have any effect on the answer. – Bram28 Feb 26 '21 at 13:57
  • Have you had a look at the link I posted, Marshall? – Gerry Myerson Feb 27 '21 at 12:12

0 Answers0