No Three In a Line

The Problem

Mary the milk lady had a square milk crate that could hold nine bottles. Can she put six bottles into the crate so that no three of them are in a line? If so, in how many ways can she do it? If not, why not?

Teaching Sequence

1. Talk about milk crates and their symmetry.
2. Tell the class Mary’s problem.
   What does no-three-in-a-line mean?
   Can you group four students so there are no-three-in-a-line?
   How many bottles is she going to use?
   Can you group five students so there are no-three-in-a-line?
   How might you go about solving Mary’s problem?
3. After some discussion, let the class work on the problem in their groups.
4. Help the students that need it.
5. Call them all together from time to time to see how many arrangements they have come up with. Get them to take turns in putting a picture of one of their arrangements on the board. Call each arrangement by the student’s name.
6. Ask
   Are all of these arrangements different?
   How might we think of some of them as being the same?
7. As a lead into the Extension problem, ask
   How do you know if there are any more than we have found so far?
   How would you go about finding out more?
   How could you go about showing that there are no more?
8. Try to get them to see the systematic approach that we used in the Solution to get all possible answers.
9. Let a few groups report back to the whole class. Try to choose groups that have used different approaches to the problem. Let the students put their pictures of the bottle arrangements on the wall.

Extension

Mary the milk lady had a square milk crate that could hold nine bottles. Can she put five bottles into the crate so that no three of them are in a line? If so, in how many ways can she do it?

Solution

The students might be able to find a solution to this problem by guessing and checking. Let them do that for a while until they have got a good idea of what the question is asking. Then try to lead them to be more systematic.

We’ll go straight into being systematic. First note that as we can’t have three bottles in a line, there are at most two in a row. Then observe that since we have to use 6 bottles we have to have two bottles in each row of the crate. We then start off our systematic approach by putting two bottles together on the left of the top row of the crate. We follow that by putting one bottle in each corner of the top row. The final case is with two bottles together in the right end of the top row.

Let’s talk our way through this. With position 1 we have put the bottles in the second row to the extreme right. The crosses show that we can’t put bottles in those squares because that would give us three in a row. So position 1 leads nowhere.

With position 2 we spread out the bottles in row 2. This forces only one cross in row three and so we can fill up the other two squares to give an answer.

With position 3 we put the two bottles in row two to the right-hand end. This forces two crosses and so there is no answer here.

The same arguments apply to the other positions. Only position 8 gives us another answer. However, by rotating 8 through a quarter turn (90° in a clockwise direction) it becomes the same as position 2. Both of these are alike (see Strawberry Milk. So the answer to the original question is ‘yes’ and there is essentially only one possible answer.

Extension:

The students should be able to find some solutions to this problem by guessing and checking. Let them do that for a while until they have got a good idea of what the question is asking (though they should have got on top of the idea from Mary’s original question). Then try to lead them to be more systematic.

We’ll go straight into being systematic. First note that as we can’t have three bottles in a row, there are at most two in a row. Then observe that since we have to use 5 bottles we have to have two rows with two bottles in and one row with just one bottle. We then start off our systematic approach by putting two bottles in the top row and two in the next row. This is followed by two in the top row and one in the next; and then one in the top row.

We’re sorry there are so many cases. It seems to be a bit tedious but it is a good exercise in systematic listing and it will be very useful later in the No-Three-In-A-Line Game and other variations on this theme at Levels 4, 5, and 6.

Out of all of that we get 28 possible answers. These are 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 17, 19, 20, 21, 22, 24, 26, 27, 28, 29, 30, 31, 32, 33, and 34. The question now is, how many of these are alike? So we need to group them into answers that are alike.

What answers are essentially the same as 2? We can get to 10 by one clockwise quarter turn, to 31 by another quarter turn and to 29 by another. So there is a class of four answers that are the same.

What answers are essentially the same as 3? Here we get 20, 24, and 26. The question now is, what about 9? Now you can’t get to 9 by rotating Mary’s milk crate. You can get to it though by a reflection symmetry. But if you did that, the bottles would fall out of the crate. So we think that 9 is a different answer. It’s a sort of left-hand form of 3. But if you disagree, let us know.

So here we might as well list the answer that are the same as 9. They are: 12, 16, and 34.

We now list the rest.
4: 7, 28, 33;
5: 8, 27, 32 (this is the left-hand form of 4);
6: 14, 22, 30;
15: 17, 19, 21.

So Mary can put 5 bottles in her crate in 7 different ways so that no three of them are in a line.