17 ms·
NP Complete 3rd Grade Math Problems (2018)
- ajsfoux234 5y agoThe PDF linked to in the post: https://web.archive.org/web/20181123120243/www.insidemathematics.org/assets/problems-of-the-month/diminishing%20return.pdf https://web.archive.org/web/20181123120243/www.insidemathema... (the original link is dead) Also, I wonder if posting a photo of the work with pencil annotations violates the CC NoDerivatives license.
- qsort 5y agoProblem E of that set is hilariously wrong: The probability of being born a male is 0.466. The probability of being born in North America is 0.153846. The probability of being born in an urban location is 0.3571428. Find the exact probability that a baby will be born a male, in North America, in an urban location. They obviously expect you to multiply those numbers (seven digit numbers with the quadratic algorithm -- poor kids), but the joint probability equals the product if and only if the random variables are independent, which in this case they are not. Problem B (mentioned in the article) is probably not as bad as it looks: you can eyeball that the target sum is approximately half of the total, and you can probably match the final digit.
- OJFord 5y agoThese things are marked by humans, and appealable (in the case of exams, if it's just homework who cares) - IME in the UK, if you write something like 'insufficient information in the question, given RVs are not independent' then you are not going to be marked down for it; if they find the question incorrect it'll likely be struck off entirely. But more likely, everyone answers either wrong (not because they know better) or right, because they don't know to do anything but multiply them; at the stage this is a question they don't know there are dependent and independent RVs. It's like if you draw something that looks near enough a square and show it to someone in primary school, asking for the angle in the corners. The correct answer is 90 degrees, it doesn't matter that it's not exactly drawn, that we didn't define a coordinate system or the units we wanted.
- jameshart 5y agoI'm glad these unwritten rules are all clearly expressed so that all 3rd graders understand them. Because if you didn't realize all the things you were allowed to assume at the level of math you are doing, it might be really stressful to be given problem for homework tat's unsolvable in general, but solvable if you make the correct set of assumptions, and think you are expected to produce a solution for it. Especially that part about 'if it's homework, who cares'. I'm sure kids are very clear on that one.
- qsort 5y agoI don't doubt that what you say is true, but it strikes me as odd that they didn't sidestep the problem by picking an example where the variables are obviously uncorrelated. It comes off as extremely sloppy: nobody expects kids in primary school to even understand what it means for variables to be independent, but certainly those writing the questions should know better!
- OJFord 5y agoJust because they don't know better, or it's a mistake. I'm not suggesting they knowingly thought 'but that doesn't matter here we want a specific technically wrong answer'.
- will4274 5y agoEh. My teacher just wrote "assume all probabilities are independent" at the top of the test. Using only independent examples is a good way to have a lot of very repetitive problems where you take marbles out of bags of marbles.
- ggggtez 5y agoThat's not NP complete. There are two major differences: 1) it fits exactly. 2) you are told there is an answer NP complete defines a generalization of a problem. Just because a general problem is hard doesn't mean every set of numbers is the same difficulty. The problem of course is they are overthinking it using an adult brain. Just think stupid: add toys until you go over, then remove some. Start from largest to smallest. Etc.
- kongin 5y agoBy that logic no instance of an NP complete problem is NP complete because you can solve any NP complete problem in finite time, seeing as it's not undecidable. It just might take longer than the universe will exist for you to get a solution.
- dfdz 5y agoIf we are being technical (and I must assume that we are given that you are making a technical critique), then everything you are claiming is wrong. 1. The phrase “an NP Hard problem” refers to the computational complexity of a problem as the “scale” of the problem goes to infinity. Typically, an author would detail the problem, and what parameters go to infinity, but in this case the general problem “The subset sum problem (SSP)” is well known so explaining details is not necessary. 2. The homework question has two parts. The second part asks “(assume a solution exists) is the solution unique?” Clearly this decision problem reduces to SSP and is NP Hard
- IncRnd 5y agoAn NP complete problem is not any generalization but a problem where all solutions can be solved using brute force in polynomial time, also representing other problems in the same space. In actuality, an NP complete problem is defined as easy to find a single solution, not that it is difficult to find a solution.
- tsimionescu 5y agoNo. If you want an intuitive but also theoretically correct definition of NP, it is the set of problems where it is easy to verify that a given solution is correct. NP - P then is the set of all problems for which it is easy to verify that a solution is correct, but hard to find any solution (this set may be empty, but we haven't proved either way). Here 'easy' means 'in polynomial time', and the property of all NP problems is that they are solvable in polynomial time given an oracle which generates the solutions, and then verifying that each solution is correct. Equivalently, they are solvable in polynomial time given an infinite number of execution threads that each takes one candidate solution and verifies whether it is correct or not (in polynomial time). I don't think there is any known class of problems in complexity theory where it is easy to find 1 solution but hard to find all solutions.
- ashton314 5y agoPeak parenting right here. Tell me about a time when you over-engineered a solution to your child’s homework or school project!
- ashton314 5y agoTo be clear I think it’s neat that this guy is involved with their child’s schooling. I for one enjoyed it when my dad got involved—I usually learned way more from working with my dad than I did from the problem itself.
- literallyaduck 5y agoSort desc first then it is pretty easy and can be stored as a bitmask.
- kongin 5y agoThe reason so many people hate maths is because maths is taught so poorly: https://www.rangevoting.org/FeynTexts.html https://www.rangevoting.org/FeynTexts.html >The reason was that the books were so lousy. They were false. They were hurried. They would try to be rigorous, but they would use examples (like automobiles in the street for "sets") which were almost OK, but in which there were always some subtleties. The definitions weren't accurate. Everything was a little bit ambiguous – they weren't smart enough to understand what was meant by "rigor." They were faking it. They were teaching something they didn't understand, and which was, in fact, useless, at that time, for the child. >[...] That's the way everything was: Everything was written by somebody who didn't know what the hell he was talking about, so it was a little bit wrong, always! And how we are going to teach well by using books written by people who don't quite understand what they're talking about, I cannot understand. I don't know why, but the books are lousy; UNIVERSALLY LOUSY!
- faeriechangling 5y agoAre there any books that aren't lousy or is it truly universal?
- codetheweb 5y agoI did Art of Problem Solving in high school which has excellent textbooks. Certainly not for everyone though.
- abrax3141 5y agoThere are many many wonderful math books, and many many wonderful math resources on youtube. (As well as, of course, many many terrible ones!) I second AOPS! They have a fantastic series for younger kids called "Beast Academy" (https://beastacademy.com https://beastacademy.com), and their challenge problem sets are fantastic! The same blog has a couple of other posts about them: https://leosstemhacks.wordpress.com/2019/11/06/the-three-best-science-math-channels-on-youtube-and-one-video-from-each-that-will-blow-your-mind/ https://leosstemhacks.wordpress.com/2019/11/06/the-three-bes...
- 5y ago
- sillysaurusx 5y agoI wish I had the energy to dive in to a delightful segue. But: https://news.ycombinator.com/item?id=26804484 https://news.ycombinator.com/item?id=26804484 … okay, I fail at presenting why this is interesting. Let me try again. Ha, I tricked you. The thing I want to talk about is CHOOSE and FAIL. There’s a certain kind of program that can solve this problem in remarkably little code: non-deterministic. Imagine you had a JavaScript statement called fail; if (foo) { fail; } The program continuously restarts, trying all possible combinations such that fail never executes. It’s like pretending the code (or incidentally, the start of my comment) has supernatural powers. It can “look into the future” and set up all the variables such that it just so happens never to fail;. Therefore, you could solve the problem like this: for each possibility { if possibility doesn’t spend all the tokens { fail } print(possibility) } The program will execute and perfectly print out every solution. And that’s all the code you need. So with that intro, I encourage you to scroll back up and read the comment chain I linked, if you’re thirsty for details. Now I sleep. Goodnight :) fail. Just kidding, I’m awake still. EDIT: Bah, I really did a terrible job with this. Sorry. You’re probably wondering “why not just use continue instead of fail?” and “what about CHOOSE?” Those are reasonable questions. The magic here is that the logic can be arbitrarily complicated. You can say “if x + y != 10, then fail; print(x,y)” and it will only print pairs like 1 and 9, 2 and 8, etc. But you’re probably still wondering “why not just loop x from 1 to 10, y from 1 to 10, and skip any x+y != 10? That’s like a Python one-liner.” … I think this is a case where I should have thought a bit more carefully before commenting, so I’ll leave this as an actual fail. But, all I can say is, non-determinism really is delightfully fascinating, and I hope I sparked one person’s curiosity about it… … sorry? runs away like an introvert
- nhumrich 5y agoThere are libraries based on this very concept. Instead of programming the solution, you program the "rules". And the library essentially a brute force (with branch trimming) until it finds a solution for you.
- umvi 5y agoSomehow I doubt "Leo" actually understands anything about NP-completeness or the Lisp program written in the article. When I was in third grade I was learning times tables. Anyway, the "trick" for me was to just group the toys together into small sets that make easily workable values. For example, I tried to find a small grouping of toys that ends in 94 cents. Boat + Racecar + Checkers = $19.94 After that I tried to find small groups of toys that added to whole numbers. For example, Bear ($4.89) + Xylophone ($7.11) = $12. Once you have a few of those, it's easy to find solutions: So then 2x (Bear + Xylophone) + Boat + Racecar + Checkers = $12 + 12 + $19.94 = $43.94 Of course, knowing whether you've found all solutions is, as the article notes, an entirely different beast.
- deckar01 5y ago> Somehow I doubt "Leo" actually understands anything about NP-completeness The parent is a Stanford professor that studies scientific reasoning. I would assume he is a good judge of what his kid understands. This article was 4 years into a series about teaching his child STEM concepts. https://leosstemhacks.wordpress.com/about/ https://leosstemhacks.wordpress.com/about/
- rejectedandsad 5y agoI love seeing that I’m literally mentally challenged compared to this third grader. Christ I hate myself.
- CaptainNegative 5y agoAn adjunct*. Also, I'm going to go ahead and say it. I don't buy it. The third grader with three different sets of handwriting who needs to write down carries in order to compute 2.16 + 0.87 and who 30 days earlier was still learning basic algebra suddenly has his own programming language in which he's doing implicit typecasting into bit vectors to enumerate a set of 2^n solutions?
- MontyCarloHall 5y agoYou’re right, the handwriting depicting the “SnuffyCode” program is far neater than the handwriting enumerating basic arithmetic on the worksheet. Looks like Leo’s dad wrote the “SnuffyCode.” I guess Leo could have been dictating to his dad, but why not just write it himself? If he’s capable of coming up with his own programming language as a third grader, he’s definitely capable of writing ~10 lines of code in it himself. The handwriting on the worksheet is actually really neat for a third grader!
- gnodar 5y agoIt is hard, but only if you try to find the general solution. If instead you think in the way the problem designer (who had a target audience of 3rd graders in mind) intended the solution to be found, then it becomes easy to find a solution: one of each toy from the yo-yo to the car (inclusive). That gets you $5.18 from the goal of $43.94, so get another car (the problem doesn't state you can't have repeats).
- bottled_poe 5y agoUnfortunately that’s exactly the issue here. That justification puts more focus on training a (simplified and flawed) process rather than understanding the fundamental nature of the problem being presented.
- Aerroon 5y agoBut that's how you build to to the learning about the eventual general solution. First graders here get fill in the blank questions: __ + 3 = 10 Years later they'll learn x + 3 = 10 Filling in the blanks isn't that hard for most kids, but dealing with x can be.
- bottled_poe 5y agoI would argue that arithmetic is overvalued in early mathematics education. Category theory, as an example, has many more practical applications and leads into arithmetic. In my experience, early education in mathematics skips many of the prerequisites and you end up learning these things through rote-learning instead of building that knowledge from the fundamentals.
- ggggtez 5y agoThe easiest solution: Sort from largest to smallest. Then just do a DFS. Or, if you're so inclined, pay attention to the 1s digit. You know the digit has to add to exactly 4, because there is an exact fit. The search space is not 20^20, it's not even close.
- joshuaissac 5y agoOne approach is to get close to the desired sum by buying a few of the more expensive toys, and then trying combinations of the cheaper ones. Just by trial and error, I tried 5*7.11 (xylophone) to get 35.55, followed by 4.77 (chequers), 2.75 (doll) and 0.87 (pinwheel). First and second were just guesses, so the only "calculated" choices were the doll and pinwheel. There are probably many other easy solutions that one might arrive at by guessing different values to start with.
- Charon77 5y agoGood job finding it I've tried the problem myself and it seems it's possible to get exact answer without allowing repeats. I got the answer, but not the method yet :(
- userbinator 5y agoThere's actually 21 items in the set, so 2097151 non-empty zero-or-one combinations. 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. Possibly they did something similar to https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-poly... ?
- deckar01 5y agoThe AZSPCS Sums of Powers problem was similar [0]. I found the optimizations surprisingly convoluted for how little of a speed up they provide. Writing an efficient backtracking, depth-first search was fun though. [0]: http://azspcs.com/Contest/SumsOfPowers http://azspcs.com/Contest/SumsOfPowers
- jameshart 5y agoIT doesn't say you can only buy zero or one of each item - in fact, the setup is explicitly that the toys are to be donated, meaning that we aren't likely to care too much about buying duplicates.
- bodhiandphysics 5y agoThere’s a trick... the answer is (yoyo + ball + elephant + jump rope)3 = 83 = 24 + (Checkers + boat + racecar) = 19.94 = 43.94. There are probably other solutions. The trick is to get rid of the change, than fine something that adds up to 8
- deleted 5y ago[deleted]
- klyrs 5y agoFun fact, that problem is NOT NP-complete. It's a finite-sized instance of a class of NP-complete problems. It can be solved in constant time. That said... holy smokes that is an awful problem.
- thallium205 5y agoSort the list descending and apply a DFS.
- cascala 5y agoHelicopter parenting, now with extra math! Don’t bore about this at the next PTA meeting, let the kid do his homework, it’s clearly intended to get them do some additions
- Charon77 5y agoHere's one answer I got from randomly picking. Each toy is either bought or passed (no repeats). I got the exact answer by getting: yoyo, duckie to elephant (from left to right, then down), and checkers. I'm trying to see if it's possible to get a more general solution rather than trial / error
- hackcasual 5y agoOne of the things that's rarely brought up in discussions about NP complete and NP hard problems is that they have input ranges where they require non-polynomial time solutions. It's difficult to speak in general, but for SSS problems, when the values are comparatively small or large, the you can use the LLL algorithm to find an exact answer in polynomial time.
- hackcasual 5y agoUsing Julia and it's LLLplus library using LLLplus show(IOContext(stdout, :limit=>false), MIME"text/plain"(), subsetsum([122,275,185,597,647,216,713,457,146,518,316,489,711,645,477,804,671,231,621,98,87],4394)) ([1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1], true) Giving a yo-yo, doll, ball, racecar, car, bear, tank, checkers, jacks, truck, pinwheel as an answer
- blibble 5y agoI was given an edge-matching puzzle as a kid, similar to this one: https://i.etsystatic.com/17381496/r/il/440b0d/3124003935/il_fullxfull.3124003935_edw8.jpg https://i.etsystatic.com/17381496/r/il/440b0d/3124003935/il_... 3x3 tiles, after spending probably days on I gave up a few years later I wrote some code to brute-force the solution, there were a total of two solutions out of ~20 billion possibilities (not including rotations) and the box said "for kids ages 8+"... I suspect the designers just drew it out and cut it up without realising quite how hard it was (NP complete)
- teruakohatu 5y agoI remember those puzzles. Are you sure there was no way for a child to prune the search space?
- gnarbarian 5y agoturns out it was a puzzle and OP is blind.
- blibble 5y agoI found the pictures I took after beating my childhood nemesis https://imgur.com/a/ICIBZCw https://imgur.com/a/ICIBZCw and https://imgur.com/a/JOWkTsp https://imgur.com/a/JOWkTsp have a go, though I think that was the strategy I was using as a child (and the box actually says 6+... mean)
- marcosdumay 5y agoYes, you can prune that thing severely. I imagine nearly all branches can be discarded after 5 tiles are positioned and the initial set is invariant to rotations, what leads to "only" many tens of thousands of possibilities. I hated with a passion those puzzles when I was a child, and the people that claimed that they measured intelligence. I had better things to do than mindlessly rearranging pieces in a board until they fit! Strangely, I have much more patience for that now.
- maxov 5y ago
- nayuki 5y agoCovered in https://xkcd.com/287/ https://xkcd.com/287/
- H8crilA 5y agoThis is a classic dynamic programming problem. You create an array of bools of length 4394+1, initialize to False, and fill it left to right with True on the specific amount of cents that can be covered (this is possible because nothing has a negative price). Then if the final element is True the solution exists, and all solutions can be generated by back-tracking. It's polynomial if the input is represented in unary form (like in the regex version down below), and exponential if the input is represented in binary. BTW, if you want you can even express this as a certain regex+input combo: Regex: (a^122|a^275|a^185|...)+ Input: a^4394 Where a^N means "a" repeated N times, and of course the regex must cover the entire string. And, if your regex engine can find all matches, then it would also find all solutions.
- hackcasual 5y agoIf the values are small enough. The problem is that the length of the unary form grows exponentially
- nroets 5y agoHere's that runs in O(√2^n) time and space. And with careful implementation it will never be significantly slower than the above DP algorithm. 1. Spilt the toys in two sets (A and B) of similar size. 2. Generate a sorted list L of all the possible sums that can be made with the toys in set A. If two sums are equal, keep only one. 3. Generate a sorted list M of all the possible sums that can be made with the toys in set B. If two sums are equal, keep only one. 4. Iterate through L forwards and through M backwards looking for two sums that together make up the target amount.
- H8crilA 5y agoThe lists L and M have to be O(2^N) in size, where N is the target sum. I fail to see how this is any faster. In fact I think it's a little slower, if N is the target sum and M is the number of toys this algorithm runs in O(2^N * M * log(M))
- 5y ago
- ohazi 5y agoReminds me of https://www.quora.com/How-do-you-find-the-positive-integer-solutions-to-frac-x-y+z-+-frac-y-z+x-+-frac-z-x+y-4 https://www.quora.com/How-do-you-find-the-positive-integer-s...
- sidpatil 5y agoIsn't this a knapsack problem [1]? It looks like it can be represented as a linear program: Maximize sum(x) subject to constraint: P•x = 43.94 where P is a vector of prices of each toy, and x is a vector of quantities purchased of each toy. Then one can either plug this into an LP solver, or can solve it by hand using simplex or other algorithm. [1] https://en.m.wikipedia.org/wiki/Knapsack_problem https://en.m.wikipedia.org/wiki/Knapsack_problem
- IncRnd 5y agoYep, except this is so small, you can look at all combinations. Something like this would do it (without replacement). from itertools import combinations arr = [ ("yoyo",1.22),("doll",2.75),("duckie",1.85),("tractor",5.97),("airplaine",6.47), ("ball",2.16),("racecar",7.13),("dog",4.57),("jumprope",1.46),("car",5.18), ("elephant",3.16),("bear",4.89),("xylophone",7.11),("tank",6.45),("checkers",4.77), ("boat",8.04),("train",6.71),("jacks",2.31),("truck",6.21),("whistle",0.98) ("pinwheel",0.87) ] for r in range(1,len(arr)+1): for thisset in list(combinations(arr, r)): if 43.94==sum([tup[1] for tup in thisset]): print ([tup[0] for tup in thisset])
- mkl 5y agoYou're missing a comma before the pinwheel one, but otherwise this finds the same 686 solutions as mine.
- deleted 5y ago[deleted]
- IncRnd 5y agoYou're correct... I must have made a mistake when pasting it into the HN edit box, since I performed slight edits to make it not jam into a single line. Thanks!
- lqr 5y agoThe LP solver might find a solution with fractional toys. If we add the constraint that x must be an integer vector, then it becomes an integer linear program. Solving integer linear programs is NP-complete.
- kristopolous 5y agoIs there any proof that the solution must have an iterative approach? For instance, say there was some extremely clever way of depicting the relationships that allowed a "single pass" computation in a way that abstractly solves it that can be reduced to the valid combinations without ever having to "guess" or backtrack or do some variation of a permutation map wherein you reduce a set of candidate solutions. This novel method would solve it like say, one does with the process of algebra. Of course this would be in some rules and abstractions perhaps invented and defined solely for this problem - perhaps discarding all of arithmetic in the process. I can imagine a proof could exist showing such an approach isn't possible and I realize coming up with such a novel system for this problem is so unlikely the inventor would be put in the league of Gauss and Maxwell, the question is setting that aside, has it been shown to be a futile effort?
- Cerium 5y agoThis is a variation on the Knapsack problem. I'm not familiar with the common proofs used, but it is a well studied problem.
- kristopolous 5y agoYep, that's kind of why I asked it. I've always been unhappy with the various solutions and I've felt that with some representations, abstractions, and relationships this class of problems would be as solvable as say, a geometry problem. But it might be the geometry problem of squaring the circle and I can roughly see how a proof for it having to be iterative might work (by contradiction specifically). I am not enough of a mathematician in the field to know
- tsimionescu 5y agoGiven that this problem is the knapsack problem, which is known to be NP-hard, your question amounts to asking if we know for sure that P!=NP, except that you're actually asking for a much tighter bound than polynomial complexity. Right now there is no proof that there isn't a polynomial time algorithm for the problem. I'm not 100% sure, but there are probably proofs for lower bounds, forbidding something like the O(n) you're thinking about. For example, the minimum possible worse-case complexity for an algorithm sorting n numbers is proven to be O(n*log n) comparisons. You're not going to find a solution to the knapsack problem that's easier than that, I think that much is obvious.
- brudgers 5y agoBy the way, Leo says that some kids actually solved the problem exactly Occam’s Razor suggests access to the answer as the simplest explanation. Given the level of parenting described in the article, the perceived academic stakes within the context would justify the proverbial file cabinets with answers to the professors’ tests moved down to primary school…I mean some parents have kids competing with the NP complete kid.
- jtc331 5y agoGiven many here have shown it’s not hard to “stumble” onto a correct answer, your comment is a great example of how Occam’s Razor shows the probable, but there are many cases where the simplest explanation isn't correct.
- kccqzy 5y agoIf the question is asking how many possible solutions there are, it can be solved with generating functions. (This method was popularized by George Pólya but I learned it from Knuth.) Let A(z) be the generating function for the number of ways to spend n cents using only the $1.22 yoyo. Then naturally we can only spend those n that are multiples of 122 cents. So we define A(z) = 1 + z^122 + z^244 + z^366 + ... In this formulation the coefficient represents the number of ways: that's why the coefficient is 1 if the power is a multiple of 122 but 0 otherwise. Next we realize this infinite sum can be transformed into A(z) = 1 / (1 - z^122). Next, we consider what happens if we are allowed to use both the $1.22 yoyo and $2.75 doll. We get B(z) = 1 / (1 - z^275) * A(z). We repeat this for all items, to arrive at the closed form solution U(z) = 1 / ((1 - z^122) * (1 - z^275) * (1 - z^185) * ... * (1 - z^87)) Now if we have a computer algebra system we just ask it to do a Taylor expansion and read off the solution at the z^4394 term. Mathematica can do it but sadly I can't get Wolfram Alpha to do it. The answer is 4794820. (This allows repetitions, and I think the author didn't allow repetitions. The author also missed the third item, the $1.85 duckie which is apparent from the posted code and the fact that there are references to 2^20 not 2^21.) If you don't have a computer algebra system you can of course solve it manually with dynamic programming: the coefficient of z^n for B(z) is equal to the coefficient of z^n for A(z) plus the coefficient of z^(n-275) for B(z). Just think about the distributive law for multiplication. But then for Hacker News, I guess dynamic programming is more preferred then: #include <array> #include <stdio.h> int main() { static constexpr std::array<int, 21> kItemPrices = { 122, 275, 185, 597, 647, 216, 713, 457, 146, 518, 316, 489, 711, 645, 477, 804, 671, 231, 621, 98, 87}; static std::array<std::array<int, 4395>, kItemPrices.size()> dp = {}; // Base case for (int j = 0; j <= 4394; j += kItemPrices[0]) dp[0][j] = 1; // Recurrence for (int i = 1; i < kItemPrices.size(); ++i) { for (int j = 0; j <= 4394; ++j) { dp[i][j] = dp[i - 1][j] + (j - kItemPrices[i] < 0 ? 0 : dp[i][j - kItemPrices[i]]); } } printf("%d\n", dp[20][4394]); }
- TchoBeer 5y ago>The answer is 4794820 how do we get the answer from here?
- noduerme 5y agoThis problem looks really familiar to me. I went to an experimental elementary school - actually a large-scale psych experiment run by psychologists - where these kinds of NP-hard problems were parceled out in each class to supposedly find the most talented students, and where the problems ranged from those with geometric or visual solutions to purely mathematical ones (some of which even the teachers couldn't solve). It's impressive (if true, which I doubt) that the child wrote NP-COMPLETE on the paper. And I wouldn't argue it's good exercise for a child's mind to try to solve things like this; in fact, an 8-year-old may be a lot faster at doing it than any known algorithm, for reasons we don't fully understand. But in fact these tests had nothing to do with getting the answer right. No one expects them to get it right. It's a way of measuring whether or not a child becomes frustrated with hard problems - or whether they try to do all the math one step at a time - or whether they try to invent some logic to solve them. Technically, mathematically, whatever shortcut they invent to solve can't possibly shortcut the NP-Hard nature of the problem, but the array of ways they'll come up with to try to do that is what's fascinating.
- foxes 5y agoAlthough finding the specific partitions might be tricker, existence is easy, this is the classic change making problem. Expand prod_i 1/(1-x^p_i) and check if you have terms = total value. Should tell you the number of possible partitions right away.
- phoenixreader 5y agoFor those interested, there is a trick to this. You successively add the first several items until the amount first exceeds 43.94. This occurs after summing up the first twelve items, with the sum being 46.81. The items are over the limit by 2.87. You wish to decrease your spending by $2.87, so you check if there are any items you have not chosen that cost exactly $2.87 less than an item you have chosen. A smart fifth-grader would quickly find that the car ($5.18) can be replaced by Jacks ($2.31). This concludes the problem-solving process. This question was intended for fourth- and fifth-graders (https://www.insidemathematics.org/sites/default/files/materials/diminishing%20return.pdf https://www.insidemathematics.org/sites/default/files/materi...). Put yourself in the shoe of a smart fifth-grader who knows nothing about NP-completeness or knapsack problems. This problem is given to you, and you know it as solvable. This problem would look intimidating, but a good student would look for patterns, and the best way to start looking would be to sum the first few items (who knows, maybe the first items would sum up to exactly $43.94). After summing up to 46.81, a good student would "naturally" stop adding new items and ask himself "what can be done now?" All that he needs is now a mental "click". Essentially, this problem tests students' intuition. It tests whether students can remain unintimidated in the face of difficult-looking questions. They need to start adding, and they need to have that one insight of replacing one of the items. Insights like these are extremely common and rewarding for young math learners. I won't be surprised if many fifth-graders can solve the problem in five minutes.
- quacked 5y agoThat is... absurd. What an absolute waste of time, setting arbitrary patterns in interesting math questions- do we seriously want students, upon seeing a tough problem, to "just start adding"? What rationale could anyone possibly have to teach this mindless nonsense to children, unless it was to prepare them for other standardized tests later in life, which are unanimously the product of mathematically impotent failed bureaucrats?
- ivalm 5y agoOftentimes problems are hard, being able to come up with a useful heuristic (in this case greedy + fixer) is probably the most valuable thing one can do. Most math problems in real life aren’t solvable, you have to learn to approximate/bootstrap your way through.
- marcodiego 5y agoMy solver found 351 solutions without repeating items. But the article says there are 279. What is wrong? #include <stdio.h> #define N_ITEMS 21 int prices[] = {122,275,185,597,647,216,713,457,146,518,316,489,711, 645,477,804,671,231,621,98,87}; int sol[N_ITEMS] = {0}; void show_sol(void) { printf("["); for(int i = 0; i < N_ITEMS; i++) printf("%d%c", sol[i], i != N_ITEMS - 1 ? ',' : '\0'); printf("]\n"); } void solve(int limit, int depth) { if(depth == N_ITEMS) return; if(limit == 0){ show_sol(); return; } solve(limit, depth+1); sol[depth]++; limit -= prices[depth]; solve(limit, depth+1); sol[depth] = 0; } int main(void) { solve(4394, 0); return 0; }
- lmns 5y agoThe author forgot to add the "duckie" item in the list.
- abrax3141 5y agoThe OP wrote in Lisp. The Lisp compiler reflects on the code, and realizing that it’s trying all combinations, cross-compiled it to a quantum computer which produced an approximate answer.
- mkl 5y agoThere are actually 686 solutions. The problem is you're exiting the solve function before showing the ones that include the last price. Swapping the order of the two if statements fixes it.
- marcodiego 5y agoThanks!
- Tempest1981 5y agoNote that this line only initializes element 0, not all elements: int sol[N_ITEMS] = {0}; Did you mean {}?
- shreyshnaccount 5y agoI wish somebody had taught me like Leo is being. seems so much fun
- nroets 5y agoHere's a much more efficient algorithm that runs in O(n*√2^n) time and space: 1. Spilt the toys in two sets (A and B) of similar size. 2. Generate a list L of all the possible sums that can be made with the toys in set A. 3. Sort the list. 4. Generate all the possible sums that can be reached with the toys in B and binary search L for a sum that will solve the problem.
- octonion 5y agoSolution in SageMath: from sage.numerical.knapsack import knapsack knapsack([122, 275, 185, 597, 647, 216, 713, 457, 146, 518, 316, 489, 711, 645, 477, 804, 671, 231, 621, 98, 87], max=4394) Note that this only finds a solution, not all solutions.
- andi999 5y agoI don't like the title, NP problems do not have to be hard, it only means they get hard if you scale up the problem. Like traveling salesmen with 3 destinations is easy, not hard. I also agree the problem posed is ridiculous, but NP hard does not alway mean hard.
- arh68 5y agoThe code snippet in the made-up language is certainly interesting. You know, with more judicious use of the graph paper, sprinkle in some OCR and you might could run the hand-written version one day. The typed version maybe something like 0 PRICE=$10.02 1 MAT A[20] 2 BIN L 3 DEC N / 4 FOR N FROM 1 to 2^20 | 5 L = N | 6 /*******/ | 7 (/\A[L])?=PRICE 10 \ 8 NEXT N 9 10 PRINT A[L] 20 END 30 /SNUFFYRUN 40 ((NIL)) 50 60 70 80 90 100 200 300 400 500 END
- ajennings 5y agoHere's how I did it by hand (assuming you can buy multiple of a given item): Work in cents, modulo 87 (the cost of the cheapest item, the pinwheel). The total we want is 4394 (or 44 mod 87). Write down the price of every item modulo 87. The whistle is 98 (or 11 mod 87) so you can buy 4 whistles and make up the rest in pinwheels (46). The dog is 457 (or 22 mod 87) so you can buy 2 dogs and make up the rest in pinwheels (40). Lots of other combinations. However, the paper doesn't seem to suggest that buying multiple is okay. I'm glad others mentioned the dynamic programming solution. That one feels elegant. Should've thought of that.