Wolves and Sheep
Here’s your chance to be the hero of the story! Help keep the big bad wolf from eating the three little… sheep. Well, I guess it’s not the same story – and unfortunately, the sheep live in a field, not a house – but you get the idea.
To start this activity, you’re going to need two different types of objects (anything you have around the house will do – 2 different colored blocks, quarters and pennies, etc.) and a 4 by 4 and 5 by 5 grid (a chess or checker board works well for this).
The rules are simple: you want to place the sheep on the board so that the wolves can’t eat them. A wolf can eat a sheep if it has a direct path to it – or is in same row, column, or diagonal as that sheep.
Let’s start with our 4 by 4 grid. If we have 2 wolves and three sheep, can we find a configuration of wolves and sheep where none of the sheep get eaten?
After some tinkering around, I arrived at this:
Ok, now what if I kick the difficulty up a notch? Could you place 3 wolves and 2 sheep so that none of the sheep get eaten? While, after some struggle, I found this configuration…
… I was kicking myself when I realized that I could have simply switched the roles of the wolves and sheep from the solution I found in Question 1:
Sometimes the best (or at least the simplest) answer is right in front of our eyes!
If we only have 1 wolf now, what’s the largest number of sheep we can add to the board?
My first thought when approaching the problem was this: for which location on the board will the wolf take up the least number of squares? No matter where you place the wolf on the board, the number of squares taken up by the row and column remain the same. However, by placing a wolf anywhere in the middle, you increase the number of squares taken up by the diagonals. That leaves two more locations we could put the wolf: in the corner, or on the edge.
Either way, it turns out, the results are the same. The maximum number of sheep we can fit on this 4 by 4 board is 6 sheep.
What if we increased the board to a 5 by 5? Keeping the 1 wolf rule, what is the maximum number of sheep we can place on the board now?
Using the same logic as we did in Question 3, we come to the conclusion that all of the edge squares will yield the same (and highest) result. I chose to use the corner piece to make placement of the sheep simpler, and arrived at a maximum of 12 sheep.
Challenge Question 1
We’ve found the maximum number of sheep on a 4 by 4 and a 5 by 5 board, but can we find an expression for the max number of sheep on any n by n board (still with 1 wolf)?
If we continue using the strategies we employed in Question 3 & 4, we know that the maximum amount of sheep is the number of squares that remain on the board after we take away the row, column and diagonals from a corner or edge piece.
If you exclude the wolf’s square from the row, column, and diagonal, you end up with the same number for each: n – 1. That gives us 3*(n – 1) plus the 1 square the wolf resides in, so 3*(n – 1) + 1 = 3n – 3 + 1, which gives us 3n + 2.
Then, we subtract that value from the total number of squares on the grid, n^2, which gives us a final expression for the max number of sheep on an n by n board: (n^2 ) – 3n + 2.
Let’s see if this checks out for a 6 by 6 board. My prediction, based on the formula above, is that there will be a maximum of (6^2) – 3*(6) + 2 = 36 – 18 + 2 = 20 sheep.
There we go! You can count them for yourself if you’d like, but I can assure you there are exactly 20 sheep on that board. Well done, you’ve finished the first challenge!
Challenge Question 2
Now, if we have 3 wolves and 5 sheep, what is the total number of possible configurations of wolves and sheep we can have on a 5 by 5 grid so that all of the sheep survive?
This problem gave me a little more trouble, but after messing around with the same types of configurations I used in Questions 1 & 2, I found this:
If you flip and rotate this grid, you can come up with 7 more variations on the original configuration, which gives a total of 8 configurations.
(reflected across the vertical axis)
(rotated 90 degrees clockwise)
You did it! You saved the sheep! But there’s still so much more to explore. Like, what’s the largest number of sheep for any n by n board if there are 2 wolves? What about 3? Or what’s the smallest grid that can safely fit 4 wolves and 6 sheep? Come up with your own puzzle – see if your friends can solve it!
Keep exploring, and keep saving the day!