No Three In a Line
This activity has a logic and reasoning focus.
create geometric shapes that satisfy the no three in a line condition on 3 by 3 grids
use a systematic appraoch to find possible outcomes
This problem is one of a series of 8 that builds up to some quite complicated maths based around the theme of no-three-in-a-line. That theme was not obvious in the lower Level problems, Strawberry Milk, Strawberry and Chocolate Milk and Three-In-A-Line but it will start to come to the fore now. This theme continues in later problems at the higher Levels. These problems are More No-Three-In-A-Line, Level 4; No-Three-In-A-Line Again, Level 5; No-More-In-A-Line and No-Three-In-A-Line Game, Level 6.
It might help if you have done the three problems from Levels 1 and 2 with your class before you start on this problem. Those problems contain the essential ideas of (i) ensuring that you have obtained all possibilities and (ii) finding all possibilities that are ‘alike’ (can be obtained from others by quarter turns). (See Strawberry Milk.)
So the essential four steps in this problem are to
- find some answers;
- find all possible answers;
- justify that all have been obtained; and
- reduce the answers down to ones that are not alike under rotation.
It may be possible to do the last two steps together as we did in Three-In-A-Line. The techniques used there are sufficient to solve the present problem.
There is a web site on the no-three-in-line problem. Its url is www.uni-bielefeld.de/~achim/no3in/readme.html. This is still an open problem in mathematics and has an interesting number of sub problems relating to symmetry.
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?
- Talk about milk crates and their symmetry.
- 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?
- After some discussion, let the class work on the problem in their groups.
- Help the students that need it.
- 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.
Are all of these arrangements different?
How might we think of some of them as being the same?
- 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?
- Try to get them to see the systematic approach that we used in the Solution to get all possible answers.
- 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.
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?
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.
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.