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):
  • 「這張地圖只有二十幾個路口，你花了 10 分鐘才找到答案。如果是全台灣的路口呢？」
  • 「這類問題最可怕的地方在於：要檢查你的答案對不對很簡單（逐一確認每個路口都有被冰淇淋車照顧到），但要『找到』這個最少數量的答案，卻超級無敵難！」這就是著名的 「NP 完全問題(NP-Complete) 」。（嚴格說，「k 輛夠不夠」的判定版本才叫 NP-complete；「找出最少幾輛」的版本稱為 NP-hard。）
  • 這一類的問題，範圍從邏輯，拼圖式的排列問題到地圖著色問題，規劃走遍所有地點的路線，還有調度流程問題等等，問題可以說成千上萬。但令人驚訝的是，所有的這些問題已被證明是相同的：如果其中一個問題找到了多項式時間的演算法，那其他所有的問題就可以經由此演算法做轉換而一起解決—「要嘛全部都有高效率的解法，要嘛全部都沒有。」

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ⁿ來比較，哪個比較大？在n達到117之後，後者就會超越前者）。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

延伸閱讀

• THE POOR CARTOGRAPHER—GRAPH COLORING
• Unlocking the "Budget-Saving Paving Magic" through Muddy City: The Minimum Spanning Tree (MST)
• What is the Price of Your Luck? — Cracking Computer Search Costs with the "Token Game"