a six year old solves the subset sum problem: a post on an operations research science fair project

In December, I asked for suggestions for my six year old daughter’s science fair project.  After getting many excellent suggestions, my daughter ended up picking her own project.  I promised to blog about her project, so here goes.

The science fair project began on a snowy day in December when I took my daughter to my office when her school closed.  To keep her occupied, I printed out math worksheets and let her poke around on educational websites on my laptop.  During a lull in the day’s activities, I wrote an instance of the subset sum problem with four items on my chalkboard just for kicks.  I drew bars with lengths equal to the item sizes and then drew a number line of length ten to serve as the capacity.  She then fit three of the items along the number line to exactly fit within the capacity of ten.  She had so much fun with this, that we decided to do a subset sum science fair project.  Could she always find numbers that would add up to ten?

My six year old solves the subset sum problem

My six year old solves the subset sum problem on a number line on my office chalkboard. That's not an "E," it's a "3."

Her experimental setup was to randomly generate sets of five items using five six-sided dice.  She considered capacities of ten and twelve.  We chose these capacities since (a) her class has done a lot of math involving the number 10 recently, and (b) 30 randomly generated Excel instances gave sizes that summed to fourteen or more, so twelve seemed like a reasonable capacity that wasn’t too big.

The goal of the project was to solve the subset sum problem visually and to then turn it into an addition problem.  If she couldn’t find numbers that would exactly equal ten or twelve, she would find the closest number without going over the capacity.  To solve the problems visually, we cut out bars of length 1″ to 6″ using grid paper and then made two number lines of length 10″ and 12″.  We stuck Velcro to the numbers to make them stick.

When we set up the experiment and ran through a test case, my daughter figured out which numbers added to ten and how to write it down as an addition problem. She immediately said “This is fun!” and the rest is history.  Soon, she was able to record the results in her log herself in addition to running the experiments.

The experiment

The experimental setup. After rolling some dice to produce random numbers, my daughter selected pieces of length to the numbers rolled and then tried to Velcro the numbers on the number line. After solving the Subset Sum Problem visually, she wrote down the corresponding addition problem (5 + 4 + 1 + 2 = 12 in this case). We didn't always produce numbers that would exactly add to 10 or 12.

We made a bar graph of the results together (the one thing I know about early math education is to use bar graphs! hers is below) and discussed whether the hypothesis was correct.  She practiced explaining the experiment to me, and it was amazing how much she had learned during the process.

When I brought her poster to school, I noticed that she was the only kid to do a project in the “Math/Computer Science” category in grades K-2, the “junior” division (Chemistry, Life Sciences, and Physics were the popular categories). They K-2 projects were not judged, but as someone with science fair judging experience, I think she did a fantastic job.  Regardless, I was happy with increasing my six year old’s enthusiasm for operations research.

A bar graph of the results

A bar graph of the results. In 24 random instances, there were numbers that added to ten in 19 of 24 instances, and there were numbers that added to twelve in 22 of 24 instances.

Advertisements

8 responses to “a six year old solves the subset sum problem: a post on an operations research science fair project

  • Tallys

    Excellent project! Congratulations to your daughter and to you as well!

  • Paul Rubin

    The governor and legislature in Michigan are starting the annual budget wrangle. Given their aptitude with budgets, I was wondering what your daughter charges for consulting?

  • Laura McLay

    Ha! Politics can be an ugly business, so I’ll shield her for a few more years 😉

  • Basil

    Very nice science fair project. I do a similar thing in my class with a game called “Chance”. There are a total of 6 different rounds, one for each letter in Chance. Each round consist of rolling two dice. Students are allowed to stand up during a round and add the sum of the dice. They may remain standing and continue to add their sums until they sit down. Once they sit down, they are not allowed to stand up again that round. The catch is if a one is rolled, then the round ends and anyone standing when the one is rolled losses the entire sum for that round. So if the total sum for the round were 17 and the students remained standing on the next roll of a 1 on either dice, then they would not make any points for that round. By sitting down, they are allowed to bank their points for the final score after all 6 plays. There is one last catch. If you are ever caught standing when a 1 is rolled on both dice you lose all points for all rounds. I think a good project would be to find when would be best to sit down in a round…

  • Laura McLay

    Basil, what an excellent game! That would be challenging for kids as well as for my college students.

  • alex mills

    Basil, that’s an interesting game- I am sure there are gambling games that are similar that have already been analyzed.
    You could add a twist if each student rolled their own two dice, versus the whole class rolling just 2 dice, that changes things a lot.
    If the objective of each individual student is to win the game, and be the only winner, and there’s an absolute payoff to being #1, this is different than everyone trying to simply maximize their own score disregarding the scores of their classmates, the latter being more akin to playing multiple rounds of an entire game of CHANCE.

    If we start our analysis in the 6th and final round, the choice is to either stand and gamble, or sit and take an automatic 0 points (as it is for each round).

    I think the answer for the last round is:
    If you are winning by more than the expected value of a return on standing, then you should definitely sit out the last round, otherwise you should gamble.

    Expected value of gains is 6.75. In the last round, the game is only between the leader(s) and you. So if in the last round you are down to the leader by any amount, and the leader chooses to sit out, then you must gamble to win the game. If the leader(s) is up by any amount and chooses to gamble, you don’t have to gamble to win the game, but it’s much more likely that the leader will gain points in the last round, so you should gamble in that case also.

    On the other hand, if you are winning the game by more than 6.75, then sit, or if you are winning the game by any margin and nobody else chooses to gamble (what?!) then sit.

    In the 5th 4th, and prior rounds, things are much more complicated and it’s not just a game between you and the leader(s).

    Other it could possible be this simple. In the 5th round: if you are up by more than 2 x 6.75, you should sit out that round, otherwise gamble.

    In the 4th round, same idea as 5th round. If you up by more than 3 x 6.75, sit, otherwise gamble.

    In the 3rd round, always gamble, because you cannot be up by more than 4 x 6.75 at this round.
    In the 2nd round, always gamble.
    In the 1st round, always gamble.

    Things change if you don’t know the scores of the other players, then you have to compare your current score in each round with the expected maximum score of the other players, and you have to assume the other players are perfectly rational, because you can’t see what choices they are making 🙂

    Definitely a fun problem.

  • alex mills

    *Sorry, correction to above, this magic number of 6.75 is definitely wrong, it should be close to 5.5555.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: