CEMC Banner

Problem of the Week
Problem E and Solution
Feeding Penguins

Problem

Sabrina is playing a video game that uses a \(6\) by \(6\) grid. Her character starts in the top-left square and needs to get to the house in the bottom-right corner. All the other squares contain either fish or penguins, as shown in the following grid.

character one penguin two fish one fish two fish two penguins
one fish one fish three fish three penguins one penguin two fish
one penguin two fish one penguin one penguin one fish two penguins
three fish two penguins two penguins two fish one penguin one fish
three penguins two fish one penguin two penguins one penguin two fish
three fish one fish three penguins two fish one fish house

Sabrina can move only right or down through the grid. When she gets to a square with fish, she picks up all the fish. When she gets to a square with penguins, she must feed one fish to each penguin.

If Sabrina starts with \(5\) fish, what is the maximum possible number of fish she could have with her when she arrives at the house?

This problem was inspired by a past Beaver Computing Challenge (BCC) problem.

Solution

One way to solve this problem is by counting the number of fish Sabrina has as she moves through the grid, recording the maximum possible number of fish for each square. To start, Sabrina has \(5\) fish. If she moves to the right then she lands on a square with one penguin. After feeding it she has \(5-1=4\) fish. If she instead moves down initially, then she lands on a square with one fish. After picking it up, she has \(5+1=6\) fish. There are two ways to get to the square in the second row and second column. If Sabrina comes from the left, she will have \(6\) fish, but if she comes from above, she will have only \(4\) fish. Since \(6>4\), the best way to reach the square in the second row and second column is to come from the left. We record this on our grid with an arrow. Then, since the square in the second row and second column has one fish, Sabrina will pick it up and then have \(6+1=7\) fish.

The first two rows of a 6 by 6 grid. The top-left square has the number 5 and arrows pointing to the square to the right and below. The square to the right shows the calculation 5 minus 1 equals 4. The square below shows the calculation 5 plus 1 equals 6, and has an arrow pointing to the square to its right. This square, in the second row and second column, shows the calculation 6 plus 1 equals 7.

In this way, for each square we calculate the total possible number of fish coming from the left or from above, and use the higher number in that square. Each arrow indicates the direction from which the higher number was calculated. The completed grid is shown. A shaded path through the squares in the grid is also indicated. Following the shaded path allows Sabrina to end up with the maximum possible number of fish when she arrives at the house.

The shaded path starts at the top left square containing the number 5 and ends at the bottom right square containing the number 12. The path moves as follows: 1 square down, 2 squares right, 1 down, 1 right, 1 down, 2 right, 2 down. The entry in each square, along with the direction of the arrow pointing into that square, is described in the Alternative Format for the Grid.

Thus, the maximum possible number of fish Sabrina could have with her when she arrives at the house is \(12\).