NP Complete 3rd Grade Math Problems | STEM Hacks & Cogniscient

Leo’s third grade class got to try a Noyce Foundation math worksheet [1] the other day. They didn’t fare so well, but I gotta tell you, some of the problems are REALLY hard! In fact, one of them is NP-Hard! Now, I’m sure that there must be a trick to this problem, but I wasn’t able to see it in the couple of minutes that I thought about it. In fact, Leo even recognized that it’s NP-Hard; He told me the day of the quiz that they had given out an NP-Complete problem! (In fact, if you look closely at the page, you’ll see that he wrote “NP Compleite” (Sic ) diagonally across the picture:

One of the things I’ve told my students over the years, only half jokingly, is that computer scientists are fundamentally lazy; Why should we work when we can get a computer to work for us?! Since I couldn’t figure out off the top of my head how to solve this problem without trying all possible combinations (and god help you if you allow repeats!), Leo and I set about writing a program to solve it for us.

Without going into great detail, here’s the code:

*Items* is the list of items as pairs, as: (name . price):

The only interesting function here is the combs function, and that’s the only one that I bothered to work through in detail with Leo. We first set out the recurrence on the board (bottom to top, excluding the top line, which is the input):

Leo got the recurrence pattern right away, although I, of course, had to help him put it into Lisp. (Compare with his Snuffycode version, below.)

Of course, first making a huge list of all possible combinations, and then scoring each one, is extremely space-inefficient. A depth first search would be better, but making all the combinations first is conceptually simpler.

Anyway, space-wasting aside, calling it (via seek$) results in 279 non-redundant solutions.

Here are the first few:

We also found the shortest and longest solutions (shortest was 7 — the reduce…mapcar got cropped out of the screencap):

After all this was done, Leo wanted to write the program in “Snuffycode”, his own private programming language (for which, thank goodness, neither a compiler or interpreter exists):

Note that this code uses a different search method, counting up to 2^20, and using binary expansion to select the item list. Snuffycode, being a bit like APL, has implicit type conversion (L=N), operators that select a subset of an array when the array index is represented in binary (A[L]), and an operator that sums up arrays (/ \).

By the way, Leo says that some kids actually solved the problem exactly, so there may be a trick that wasn’t obvious to Leo or me, or maybe they just got lucky. It seems to me that there must be a trick, because if you’re only looking for 1 solution in 279 out of 2^20, that’s about a 1 in 3000+ chance of finding it by luck. (The problem might be easier is you allow redundant solutions. Although that makes for many more possible solutions if you were brute-forcing it (technically, an infinite number! … although you could apply a sensible limit), you maybe could do some sort of stacking up to a target that you can then fill in….or some such algorithm.

Like I said at the outset, it’s not worth thinking deeply about such a small problem; That’s why we invented computers!

By the way, the problems in the Noyce set were supposedly in difficulty order, and this was only the second of five problems! I solved the third one using straightforward algebra (although apparently some of Leo’s classmates solved it by brute force — remember, these are THIRD GRADERS!). The fourth required slightly more complex algebra.

The fifth problem was extremely easy, if you know anything about probability.

Go figure…

[1] Unfortunately, I think that the Noyce Foundation has ceased operations.