Space: Supermarket networks
View Sequence overviewAlgorithms can be used to systematically generate, organise and count valid paths through a network, with decomposition helping make complex path-counting problems more manageable.
Whole class
Supermarket networks Slides
Each student
Supermarket paths Student sheet
Each group
In this lesson, students are divided into four groups. Each student in each group needs the Student sheet corresponding to their group, printed on A3 paper:
- Supermarket navigation Group 1 Student sheet
- Supermarket navigation Group 2 Student sheet
- Supermarket navigation Group 3 Student sheet
- Supermarket navigation Group 4 Student sheet
Task
Show Slide 10 from Supermarket networks Slides with the supermarket network from Task 1 and the spill still blocking the connection between L6 and L5.
Set the scenario:
The supermarket manager wants a security guard to complete regular inspections from entry to exit. The guard is required to vary the inspection route so they are not walking the same way every time.
Clarify the language:
In everyday life, we might call this a route through the supermarket. In network mathematics, we call it a “path”. For this task, a path cannot pass through the same point, or vertex, twice.
Ask one student to describe a possible path from entry to exit by reading the vertex labels aloud. For example:
Entry → L6 → U7 → U6 → U5 → L4 → L3 → L2 → Exit
Record their path on the board and ask:
- Is this a valid path? Why?
- Does each step move along an edge?
- Has any vertex been repeated?
Then introduce the main problem: That is one valid path. But how many valid paths are there altogether?
Ask:
- Do you think there are only a few valid paths, or many?
- How could we start finding them?
- What might make it difficult to know whether we have found them all?
Invite students to record a prediction for the total number of paths. Write a range of these predictions on the board to refer to later.
Emphasise that finding one path is easy. The challenge is to find every valid path without missing any or counting the same path twice.
Give each student the Supermarket paths Student sheet.
Ask students to list at least three valid paths from entry to exit without passing through any vertex more than once.
As students work, circulate and ask questions such as:
- What vertex did the path have to move to first?
- Where was the first choice in the path?
- Were any moves forced because there was only one possible next edge?
- Which vertices created more than one possible direction?
- How can the path be checked to make sure no vertex has been repeated?
Bring the class together and ask students to share one or two paths.
Discuss: What parts of the paths seem to be the same each time?
Students should notice that every valid path begins: Entry → L6 → U7 → U6 and eventually needs to reach: L2 → Exit.
Ask:
- Where do the paths first start to branch?
- Which vertices give more than one possible next move?
- Were there any forced moves where you had no choice?
- What might make it difficult to list every valid path?
Draw out that finding a few paths is manageable, but finding all paths requires keeping track of all branches, avoiding repeating vertices, and avoiding counting the same path more than once.
Conclude that a more organised approach is needed to follow every branch of the network to be confident that all possible paths have been found and none have been duplicated.
Ask students to discuss in small groups how they think the total number of valid paths could be found.
- Where does every valid path have to start?
- What should happen when there is only one possible next move?
- What should happen when there is more than one possible next move?
- What should happen if a path reaches the exit?
- What should happen if a path gets stuck?
- How could the process avoid repeating vertices?
- How could the process avoid missing or duplicating paths?
Ask each group to suggest one rule or step that would help make the process possible.
Bring the class together and record useful ideas on the board. As a class, conclude that a reliable method to find the total number of valid paths needs to:
- start from a clear point.
- move only along connected edges.
- avoid vertices already used in that path.
- branch when there is more than one option.
- record completed paths.
- return to earlier choice points when needed.
Show Slide 11 with the unordered algorithm statements.
Explain that an algorithm is a clear, step-by-step process for solving a problem. The statements on the slide can be arranged to form a branching algorithm for finding all valid paths. Use the class ideas to decide the order of the steps, noting that some steps may need careful discussion because more than one order may seem reasonable at first.
Ask students to help arrange the statements into a logical order.
The steps can be arranged in the following order.
- Start at Entry.
- Move to a connected vertex that has not already been used in that path.
- If there is only one possible next move, follow it.
- If there is more than one possible next move, create a new branch for each option.
- If a branch reaches Exit, record the full path.
- If a branch gets stuck, go back to the last choice point.
- Continue until every branch has been explored.
Show Slide 12 to demonstrate the algorithm being applied.
Use the animation to follow the first few branches from the entry vertex.
Ask:
- Where is the first forced move?
- Where is the first choice point?
- What happens when there is more than one possible next move?
- Why is it useful to leave unfinished branches marked with “…”?
- When should a full path be recorded?
Highlight that the algorithm does not follow a single path from Entry to Exit. It keeps track of every branch that still needs to be explored.
Point out the completed path shown on the slide: Entry → L6 → U7 → U6 → L5 → L4 → L3 → L2 → Exit.
Explain that this is one completed path, but the unfinished branches marked with “…” show that there are still other paths to investigate.
Conclude:
The algorithm provides a way to organise the search. Each branch must be followed until it either reaches Exit or cannot continue. The challenge is now to use this structure to find all valid paths without missing or duplicating any.
From guess-and-check to systematic methods
Students often begin mathematical problems by trying a few examples and seeing what happens. This can be a useful starting point, but it also creates a powerful teaching opportunity: how do we help students recognise when an informal strategy is no longer enough?
The key teaching move is to shift students from finding some paths to needing a method for finding all paths without omissions or duplicates. This creates a reason for developing a branching algorithm. When the number of branches becomes difficult to manage, students then break the network into subnetworks that can be counted separately and recombined.
More broadly, moving students from guess-and-check to systematisation is a powerful teaching move across many areas of mathematics. The pedagogical value lies in allowing students to experience both the usefulness and the limitations of informal strategies. Rather than presenting a formal method too early, the teacher creates a need for it: students come to see that a good mathematical method is not only one that works occasionally, but one that is organised, complete, efficient and able to be checked by others.
Students often begin mathematical problems by trying a few examples and seeing what happens. This can be a useful starting point, but it also creates a powerful teaching opportunity: how do we help students recognise when an informal strategy is no longer enough?
The key teaching move is to shift students from finding some paths to needing a method for finding all paths without omissions or duplicates. This creates a reason for developing a branching algorithm. When the number of branches becomes difficult to manage, students then break the network into subnetworks that can be counted separately and recombined.
More broadly, moving students from guess-and-check to systematisation is a powerful teaching move across many areas of mathematics. The pedagogical value lies in allowing students to experience both the usefulness and the limitations of informal strategies. Rather than presenting a formal method too early, the teacher creates a need for it: students come to see that a good mathematical method is not only one that works occasionally, but one that is organised, complete, efficient and able to be checked by others.
Branching algorithms
The branching algorithm used in this task is an informal version of depth-first search. At each choice point, one branch is followed as far as possible until it either reaches the destination or gets stuck. The process then returns to the most recent choice point and explores another branch.
This approach is useful when the goal is to generate all valid paths through a network. It helps students keep track of which branches have already been explored, record complete paths as they are found, and avoid accidentally skipping possible paths.
Other search strategies are useful for different purposes. For example, a breadth-first search explores all paths one step from the start, then all paths two steps from the start, and so on. Breadth-first search is often useful for finding the shortest path in an unweighted network. Depth-first search is a natural fit in this task because students are following and recording complete branches through the network.
The branching algorithm used in this task is an informal version of depth-first search. At each choice point, one branch is followed as far as possible until it either reaches the destination or gets stuck. The process then returns to the most recent choice point and explores another branch.
This approach is useful when the goal is to generate all valid paths through a network. It helps students keep track of which branches have already been explored, record complete paths as they are found, and avoid accidentally skipping possible paths.
Other search strategies are useful for different purposes. For example, a breadth-first search explores all paths one step from the start, then all paths two steps from the start, and so on. Breadth-first search is often useful for finding the shortest path in an unweighted network. Depth-first search is a natural fit in this task because students are following and recording complete branches through the network.
Explain that the branching algorithm gives a reliable way to generate all valid paths, but the full path search is still large. Refer to some of the large estimates for the total number of paths that students made at the start of the task.
Ask:
- Is there a way to organise the class so the workload can be shared?
- How could different groups count different paths without overlapping?
Draw out that the path search can be broken into smaller parts, with different groups responsible for counting the paths within one part of the network.
The discussion then turns to how the network can be broken down and divided.
Ask:
- Where is the first major choice in the network?
- Is there another useful choice point where each branch could be split again?
Draw out that every valid path begins: Entry → L6 → U7 → U6. Then, at U6 the path search splits into two branches: paths that move towards L5, and paths that move towards U5. Each branch can then be split again at the next useful choice point.
Show Slide 13. Use the findings from this discussion to highlight the four non-overlapping path groups.
Introduce the language: A “subnetwork” is a smaller part of a larger network. By fixing the first few moves of a path, the remaining search can be split into smaller subnetworks.
Divide students into four groups and assign each group one of the four path starts.
Give each student in each group the relevant sheet for their group:
- Supermarket navigation Group 1 Student sheet
- Supermarket navigation Group 2 Student sheet
- Supermarket navigation Group 3 Student sheet
- Supermarket navigation Group 4 Student sheet
Explain that each group begins with a different fixed start, so the groups should not count the same path twice. However, there are still many paths to find within each subnetwork. It is up to each group to decide how to organise the search within their group so that all remaining branches are followed.
Groups use the branching algorithm to find all valid paths within their assigned subnetwork.
As groups work, circulate and ask questions such as:
- Is there a way to divide the work within the group?
- What branches still need to be explored?
- How is the group keeping track of completed paths?
- How is the group checking that no vertex is repeated?
- How will the group know when every branch has been followed?
Each group records the total number of valid paths found within their assigned subnetwork. These totals will be shared and combined in the next phase of the lesson.
Bring the class back together after each group has counted the valid paths within its assigned subnetwork.
Have each group report:
- the number of valid paths they found.
- how they organised the search within their group.
Record the results in a class table.
| Group | Fixed starting vertices | Number of paths |
|---|---|---|
| 1 | Entry → L6 → U7 → U6 → L5 → L4 → L3 → | |
| 2 | Entry → L6 → U7 → U6 → L5 → L4 → U5 → | |
| 3 | Entry → L6 → U7 → U6 → U5 → L4 → | |
| 4 | Entry → L6 → U7 → U6 → U5 → U4 → |
Discuss: Is it valid to add the number of paths for each group to find the total?
Draw out that the four groups are non-overlapping because each group begins with a different fixed start. Therefore every valid path must belong to one of these groups, and no path can belong to more than one group.
Show Slides 14 and 15 with the completed branches for each group. Use these slides to compare the organisation of the branches and to check group totals.
If group totals do not match the expected results, use this as an opportunity to check the organisation of the count.
Ask:
- Did the group follow every branch until it reached Exit or became stuck?
- Has any path repeated a vertex?
- Has the same path been recorded twice?
- Did the group start with the correct fixed beginning?
- Does every recorded path belong only to this group?
- Are there any choice points where one branch may have been missed?
Correct totals:
- Group 1 → 11 paths
- Group 2 → 14 paths
- Group 3 → 11 paths
- Group 4 → 14 paths
Calculate the total: 11 + 14 +11 +14 = 50
Therefore, there are 50 valid paths from entry to exit.
Conclude:
“Decomposition” made the path-counting problem manageable. Each group counted one smaller part of the search, and because the parts did not overlap, the totals could be combined to find the total number of valid paths.
After the class has combined the four group totals and found 50 valid paths, explain that this answer applies to the network while the spill is blocking the edge between L6 and L5.
Introduce the change:
The spill has now been cleaned up, so the edge between L6 and L5 is reopened.
Show Slide 16.
Ask: How many valid paths are now possible from Entry to Exit?
Give students a short time to discuss in pairs or groups.
Prompt:
- Does the whole path search need to start again, or can the previous work be reused?
- Which paths from the previous search are still possible?
- What new movement is now possible because the edge between L6 and L5 has been reopened?
- Does the reopened edge create new paths that match any of the previous path groups?
Draw out that the original 50 paths are still possible. The reopened edge also creates new paths because the guard can now move directly between L6 and L5.
This creates:
- a shortcut into Groups 1 and 2.
- another way to reach U6, which leads into Groups 3 and 4.
So, the same four group totals can be reused: 11 + 14 + 11 + 14 = 50.
The reopened edge creates another 50 paths.
Therefore, there are 100 valid paths from Entry to Exit when the spill is cleared.
Summarise that finding 50 valid paths showed how the network model can support the security guard’s need to stay unpredictable. The branching algorithm generated paths systematically, while decomposition organised the search into smaller groups that could be counted and combined. When the spill was cleared, the same grouped structure could be reused to identify the additional paths, showing how an organised network model can be updated when conditions change.