How many steps are required to break an m x n bar of chocolate into 1 x 1 pieces? We may break an existing piece of chocolate horizontally or vertically. Stacking of two or more pieces is not allowed.
Solution:
Consider a 3x4 bar chocolate.
You will first require 2 horizontal breaks -creating 3 -1x4 bars => Count = 2
You will require 3 vertical breaks on the 1st 1x4 bar => Count = 5
You will require 3 vertical breaks on the 2nd 1x4 bar => Count = 8
You will require 3 vertical breaks on the 3rd 1x4 bar => Count = 11
So for a 3x4 bar chocolate you will require 11 breaks = (3*4) -1
In general you will require mn-1 breaks
No comments:
Post a Comment