Operation Ice Cream Truck!
Using "Tourist Town" to Challenge a Puzzle Even Computers Can't Easily Solve (Dominating Sets)

In the sweltering heat of summer, nothing is better than a scoop of ice cream!

But for the Mayor of "Tourist Town," this is a major headache. The streets of the town are intricate and tangled. He wants to set up ice cream trucks at intersections, but he has a limited budget and can't afford too many trucks.

His Goal: Use the fewest number of ice cream trucks so that every resident living at any intersection only has to walk a short distance (traverse at most one street) to buy ice cream.

In Computer Science, this is known as the "Dominating Sets" problem. This isn't simple arithmetic; it is an "Optimization Challenge" that even supercomputers find tricky. Get your chips ready—let's help the Mayor save some money!

Phase 1: Creating Conflict — Does Greed Logic Fail?

First, let the children try to solve the problem using their intuition, and let them experience the moment when "intuition fails."

Phase 2: Game Setup — Visualizing Coverage

To make the concept of "Dominating" concrete, we use colors or chips to mark the coverage.

1. Props Preparation:
   • Print out the map.
   • Get about 20 chips (or coins) to represent Ice Cream Trucks.
   • Get markers of a different color (like transparent sheets or small Lego blocks) to represent "Served Residents."
2. Operational Definition:
   • When you place a truck on Intersection A, place a "Served" marker on A and all intersections connected to A.
   • There cannot be a single empty (unserved) intersection left on the map.

Phase 3: Breaking Intuition, Finding the Optimal Solution

This step is key to guiding children toward "Counter-Intuitive Thinking."

1. Guiding Reflection:
   • "We just tried grabbing the 'Big Intersections' first, and it failed.
   • Let's try a different strategy this time." "Are there any intersections that are 'lonely and difficult'? If we don't specifically place a truck there, or right next to it, will it never get ice cream?"
2. Finding Key Points:
   • Guide the child to observe the edges of the map—those intersections with very few connections.
   • Try not placing the truck in the dead center, but rather distributing them in key positions around the periphery.
3. The Moment of Success:
   • After repeated moving and adjusting, the child will eventually piece together a perfect solution using "6 Trucks."
   • Cheer : "Wow! You did it! We thought we had to occupy the biggest intersection, but it turns out avoiding the biggest one actually saved the most money!"

Phase 4: Concept Connection — Why Do Computers Find This Hard?

• Parent: "What you just did is what computer scientists call finding the 'Minimum Dominating Set.' This is super useful in the real world!"
  • Cell Phone Towers: Telecom companies want to set up base stations. They hope to use the fewest towers to ensure the whole country has signal coverage.
  • Influencer Marketing: Brands want to hire a few influencers to promote a product. They hope the combined followers of these few people cover all young people.
• The Deep Theory (NP-Complete):
  • "This map only has a few dozen intersections, and it took you 10 minutes to find the answer. What if it were all the intersections in the whole country?"
  • "The scariest part about this type of problem is: Checking if your answer is correct is simple (just count if it's 6 trucks), but 'finding' that minimum answer is incredibly difficult!"
  • This is the famous "NP-Complete Problem." This category of problems ranges from logic puzzles, jigsaw puzzles, and map coloring, to finding optimal paths on maps and scheduling processes. There are thousands of such problems.
    Surprisingly, all these problems have been proven to be the same: If a polynomial-time algorithm is found for just one of them, then all other problems can be converted and solved by this algorithm. "Either they are all solvable efficiently, or none of them are."

Phase 5: Debug & Challenge — Design Your Own Puzzle

• Reverse Engineering (One-way Function):
  • Question : "Solving puzzles is hard, but making them is easy! Do you want to test Mom and Dad?"
  • Method:
    1. Draw 5 red dots on a blank paper (these are the Ice Cream Trucks).
    2. Randomly draw many other black dots (these are the intersections).
    3. Start Connecting: Ensure every black dot connects to at least one red dot.
    4. Finally, color the red dots black so they look like normal dots. Now it's a regular puzzle map.
  • Challenge: Hand this map to someone else and ask them to find where those 5 original red dots were.
  • Discovery: The child will realize that "Encrypting (Creating the problem)" took them only 1 minute, but the other person "Decrypting (Solving the problem)" might take an hour! This is the fundamental concept of modern Cryptography.

Teaching Observation Checklist

Teaching Observation Guide

Observation Point	Less Effective Response	More Effective Guidance (Inquiry Based)
When the child insists on the biggest intersection	"That spot is bad, pick another one."	"This spot looks great; it connects to many roads. But after you place it, are the remaining corners easy to handle? Do you want to try handling the tricky corners first?"
When the child can't find the 6-truck solution	"The answer is to put them on these spots..."	"If I told you this map really only needs 6 trucks, where do you think you might have 'wasted' a truck? Are there two trucks serving the exact same group of people?"
Explaining why this is hard	"It's called an NP problem, it's complex."	"It's like a super hard Sudoku. Computers don't have a smart formula to calculate the answer instantly either. They have to try one by one (Brute Force) just like you, which takes forever."

Postscript

One interesting thing about the Ice Cream Truck problem is that no one knows if there is an algorithm for finding an optimal solution that is significantly faster than the Brute Force Method!
The time taken by the Brute Force method grows exponentially with the number of intersections—hence it is called an "Exponential-Time Algorithm."
In contrast to exponential-time algorithms, a "Polynomial-Time Algorithm" is one where the execution time grows with the square, cube, 17th power, or some other power of the variables.

A polynomial-time algorithm, even if it is to the 17th power (n¹⁷), will eventually be faster than a brute force method given a large enough map. This is because exponential growth will always overtake any polynomial growth once the parameters get large enough (For example, compare n¹⁷vs 2ⁿWhich is bigger? Once n is greater than 117, the latter surpasses the former).So, is there a polynomial-time algorithm to find the minimum locations needed? No one knows yet, but everyone is trying hard to find one.As for the easier problem: Checking if a specific set of locations is the optimal solution is actually the same situation. The time to check via brute force grows exponentially, and a polynomial-time algorithm for this specific check has neither been found nor proven not to exist.

Reference :CS Unplugged: Dominating Sets Teacher’s Supplement