CEMC Banner

Problem of the Week
Problem C and Solution
Stacking Bowls

Problem

Alice has a set of bowls of various sizes. She likes stacking her bowls upside down. A bowl can be stacked over another bowl if the smaller bowl can be completely enclosed by the larger bowl. This means the larger bowl can completely hide the smaller bowl.

For the example below, a bowl with a width of \(10\) cm and height \(10\) cm can stack over a bowl with a width of \(5\) cm and a height of \(5\) cm. In turn they can be stacked over by a bowl with a width of \(20\) cm and a height of \(20\) cm. This gives a single stack.

A front view of three bowls flipped over so that their openings lie on a flat surface. The height measures the distance from top to bottom and the width measures the distance across the bowl. The three bowls become a single stack with the medium bowl is inside the large bowl and the small bowl is inside the medium bowl.

On the other hand, a bowl with a width of \(20\) cm and a height of \(20\) cm cannot be stacked over a bowl of a width of \(25\) cm and a height of \(15\) cm. Also, a bowl with a width of \(25\) cm and a height of \(15\) cm cannot be stacked over a bowl of a width of \(20\) cm and a height of \(20\) cm.

Alice has the following set of bowls and starts stacking them. What is the fewest number of stacks that Alice can have?

Seven bowls with the following dimensions, given as width by height: 45 by 45, 30 by 15, 25 by 35, 50 by 30, 40 by 25, 10 by 10, and 20 by 20.

Solution

We note that the bowl with a width of \(45\) cm and a height of \(45\) cm cannot be stacked over a bowl of a width of \(50\) cm and a height of \(30\) cm. We also note that we are not able to stack these two bowls the other way either. Therefore, we cannot have a single stack. Thus, if we can find a solution with two stacks then we will find the fewest number of stacks is two.

Here is a solution with two possible stacks. The four bowls in the first row can be stacked and the three bowls in the bottom row can also be stacked.

The bowls in the top row have dimensions 45 by 45, 25 by 35, 20 by 20, and 10 by 10. The bowls in the bottom row have dimensions 50 by 30, 40 by 25, and 30 by 15.

Therefore, the fewest number of stacks is \(2\).