Before starting the experiment, fill 15 of the 16 boxes with an equal mass of coarse sand or gravel that is heavier than the dirty socks. Use an electronic balance to be precise in your measurement. Place the pair of “dirty” socks in the 16th box.
Choose one or two individuals to carry out the experiment.
Ask the individuals to divide the 16 boxes into two groups of 8 boxes each.
Load each group of boxes onto either side of the balancing scale. Allow some time until the balance settles.
Given that the socks are lighter than the other boxes, discard the group of boxes that tip the balance downwards
Divide the remaining boxes into two equal groups.
Repeat from Step 4 till step 6, until only one box remains. The remaining box is the one containing Santa’s Dirty Socks
Instead of sand or gravel, other objects can be used, as long as the 15 filled boxes have identical masses.
Instead of socks, other items can be used, as long as the mass of the box containing these items is significantly less than that of the other boxes.
Help keep our environment clean by reducing waste, reusing materials, and recycling whenever possible!
It’s Christmas Eve and Santa’s elves are busy placing skateboards into gift boxes and wrapping them in nice red and gold paper. Suddenly, Santa comes in and says that he has lost his dirty socks in one of the 1024 boxes that were just wrapped! Santa asks the elves to help him find them quickly without unwrapping the boxes.
One elf thinks that they should weigh every box,
but this could mean that 1023 boxes would have to be checked until the socks are found.
Then, another wise elf comes up with the idea of dividing the boxes into two groups and putting them on each side of the scale. Assuming that the socks are much lighter than the heavy skateboard gifts, the elves remove the group of boxes that are heavier than the others. Then, the elves divide the remaining boxes again and repeat the process of weighing and removing the heavier group.
Therefore from the initial 1024 boxes, 512 boxes remain in the search. When these are divided, 256 remain in the search; then 128, then 64, 32, 16, 8, 4, 2 and finally the 1 box containing Santa’s Dirty Socks. This makes Santa so relieved and happy!
And you know what’s interesting? It only takes 10 trials to go through the 1024 boxes instead of the possible 1023 checks!
The experiment simulates how Santa and his helping elves made all this happen using 16 boxes.
How many trials are required if there are twice as many boxes than the original 1024 boxes?
How many trials are required if there are half as many boxes than the original 1024 boxes?
What happens if there is an odd number of boxes that need to be divided?
Bring back a box from the discarded pile.
What happens if the boxes have all different weights?
The boxes would have to be opened and checked individually.
Are there other ways to look for Santa’s Socks?
Solving a problem through the Divide and Conquer approach involves breaking down the given problem into similar, smaller problems until the answer to the problem is found.
In our activity, the initial 16 boxes were split into 2 groups (Divide), and after being weighted, one of the groups was discarded, keeping the other group for further activity (Conquer). The decision on which group of boxes should be discarded is based on two assumptions:
1. The box containing the socks is lighter than the other boxes
2. The other boxes all have the same mass.
Based on these assumptions, the discarded group of boxes is the heavier of the two groups and therefore the kept group is always the lighter one, which will be investigated further.
This reduces the number of boxes to 8. The process is repeated using the remaining boxes until only one box remains. Given the above-mentioned assumptions, the process always keeps the lighter group of boxes, hence the process will finish when only the box of (lighter) socks remain.
Concept taken from: https://www.kidscodecs.com/cs-unplugged-projects/
The activity is a simplified version of a binary search algorithm: a fast search algorithm (run-time complexity: O log(n)) which works on the divide-and-conquer principle. Note that the algorithm assumes that the list within which the search is conducted is ordered.
Having equal masses for all the boxes in the activity, except the one holding the socks, assures that the boxes are sorted. The following algorithm also assumes that the initial number of boxes is a power of 2:
1. Divide the number of boxes into 2 groups
2. If the mass of the first group is larger than the second group
a. Then the first group is ignored, and the search continues with the second group.
b. Otherwise, the second group is ignored, and the search continues with the first group.
3. If the number of remaining boxes is greater than 1 then the search starts again from step 1 using the chosen group of boxes.
4. Otherwise the remaining box is the box with the socks.
This process can be described with the following pseudocode:
a = group of boxes
While (Size(a) != 1)
Let s = size(a)/2
m, n = groups of boxes
m = a[1..s]
n = a[s+1..size(a)]
If mass(m) > mass(n) then a = n
Else a = m
The Divide-and-Conquer approach is the basis of many important algorithms, including the following:
1. Binary Search
2. Sorting algorithms: Merge Sort, Quick Sort
3. Closest Pair of Points – Given a number of points in a plane, the algorithm finds the closest pair of points. https://www.geeksforgeeks.org/closest-pair-of-points-using-divide-and-conquer-algorithm/
4. Strassen’s Multiplication – an algorithm for matrix multiplication
5. Karatsuba Algorithm – a fast multiplication algorithm that multiplies 2 numbers
6. Cooley-Tukey Algorithm – the most common algorithm for Fast Fourier Transform (FFT)
Research is currently being carried out on the use of the divide‐and‐conquer strategy to enhance a data mining approach to bank telemarketing.
“A divide‐and‐conquer strategy using feature relevance and expert knowledge for enhancing a data mining approach to bank telemarketing” Sérgio Moro, Paulo Cortez, Paulo Rita. 26 October 2017 from Expert Systems, Volume 35, Issue 3 June 2018. Wiley Publishing Ltd. https://onlinelibrary.wiley.com/doi/10.1111/exsy.12253
- Challenge participants to think of which group of boxes should be chosen if the box of socks is heavier than the other boxes.