Yesterday’s Thoughts

March 27, 2008

Problem Solving – The Little Man’s Homework

How do you solve a problem?

I had two different concrete experiences of problem solving in the past couple of days. I think these examples are interesting because they are so contained, not because they are hard problems. They illustrate how I tackle a problem and provide some generalizable strategies for problem solving. I’ll cover the other problem in a future post and try to extract the strategies.

This post is about the little man’s homework this week. He’s still struggling with this:

Shelley wanted to buy some clothes that were on sale.

Blouses Pants Socks Shoes
$10 $10 $5 $20
$15 $20 $10 $30
$25 $35 $15 $40

Her mother said she could spend $85. List all the different ways that Shelley can buy 1 blouse, 1 pair of pants, 1 pair of socks, and 1 pair of shoes that total exactly $85. One way has been done for you.

Blouses Pants Socks Shoes
$10 $20 $15 $40
___ ___ ___ ___
___ ___ ___ ___
___ ___ ___ ___
___ ___ ___ ___
___ ___ ___ ___
___ ___ ___ ___
___ ___ ___ ___
___ ___ ___ ___

So how do you solve this?

The exhaustive solution is to run through each of the possible combinations of each item and total the associated cost. There are 3 possibilities for each of the 4 different items, so there are 3^4, or 81 possibilities. That would be a moderately tedious number of sums for an adult faced with a real life problem. The little man is 8 and doesn’t care about clothes, so he has zero patience for that approach. He wants to look at the problem and figure out the solution and if he doesn’t get it immediately then he wants to write, “I tried my best, but couldn’t figure out the answer” on his paper. Apparently this is some sort of magic incantation that he thinks his teacher will accept.

His parents aren’t happy with that solution. He has only investigated approximately 2 of the 81 possibilities, the top row and the given solution. I don’t know how to motivate him to check out all 81. I still don’t. That’s not what this post is about, but if you have any ideas, let me know.

I got bored myself after running through the first 9 possibilities — there are no solutions with the $10 blouse and the $10 pants — and started looking to solve an easier, less compute intensive, problem.

I took a couple of approaches.

First thing that I noticed was that there had to be either 1 or 3 items whose price ended in 5, or you couldn’t get $85. As I was staring at the possibilities, I felt like this eliminated many options. Many is a subjective word, though and after I figured out the there were still 39 remaining, it didn’t seem so many. Computing 39 sums of 4 two-digit numbers is tedious, even if all the terms are multiples of 5.

Human calculation speed is greatly increased by dividing every items price by 5, and trying to get them to total 17 (=85/5). You can still limit this to possible solutions that have either 1 or 3 odd terms.

Blouses Pants Socks Shoes
2 2 1 4
3 4 2 6
5 7 3 8

None of the shortcut solutions are ultimately satisfying however, because of a flaw in the display of the problem. Even running through all 81 permutations won’t satisfy, because there are spaces for 9 solutions, but there are only 8!

I wrote a little program that iterated through all the possible solutions and found these solutions:

Blouses Pants Socks Shoes
$10 $20 $15 $40
$10 $35 $10 $30
$15 $20 $10 $40
$15 $35 $5 $30
$15 $35 $15 $20
$25 $10 $10 $40
$25 $20 $10 $30
$25 $35 $5 $20

Ultimately, this becomes a problem of combinatorial optimization, which seems like too much for 3rd grade.

Anyway, I haven’t shared my results with him. I don’t know if I will. He might be fascinated, or repelled, by them. Most likely, he would want me to give them to him so he could copy me and just get it done.

Post a Comment