6 ms·
Ask HN: Can you work out how this is done? (repost)
Choose a polynomial p(x) with non-negative integer coefficients.
Now choose an integer k that's larger than all the coefficients and evaluate p(k). You tell me k and p(k), and I tell you the polynomial.
So ...
Can you work out how to do it?
Do you find this interesting?
Please don't give it away - by all means make it clear that you know how to do it (if you do!) but please don't spoil it for the others.
But mostly I'm interested in knowing (eventually) how you think about it.
This is a repost because the first time I asked the question fell off the front page with very little reaction, and perhaps not many people saw it. This is a one-shot repost - I'll not post this question again. I look forward to your answers (assuming there are any ...)
Thanks in advance.
- deleted 8y ago[deleted]
- detaro 8y agoHm, seems pretty straightforward. Can't think of any "interesting" consequences right now, but I wouldn't be surprised if there's a few interesting things about it that I'm not thinking of right now.
- ColinWright 8y agoIf you think it's straight-forward then here's an example: k=7, p(k)=12028 What's p(x)? How did you find it?
- detaro 8y agohttps://pastebin.com/A3AxRkDT https://pastebin.com/A3AxRkDT
- ColinWright 8y agoJust out of interest, can you find a connection to something more "everyday" ??
- detaro 8y ago[redacted]
- ColinWright 8y agoYup. I guess that since the post (and the previous) seems to have attracted almost no interest, the fact that you've given it away doesn't really matter - probably very few people are reading it anyway. In my experience most people find this connection surprising, and you can get a sense of that from some of the other reactions here, although I deduce from your tone that you don't. Which I find interesting. Thank you for interacting - any further comments would be welcome.
- detaro 8y agoOh, sorry, I thought you asking meant you wanted me to post the details, should have looked at the entire thread again :/ EDIT: could still edit, so edited. I guess I find it not that interesting because I spent a lot of high school with math and math puzzles, so my threshold for "surprising" is higher - although when I wrote the first comment I hadn't made the connection, only when I typed it out later, in a slightly different form than I had in my head it was clear.
- ColinWright 8y agoOh - thanks for redacting - appreciated. Mind you, very, very few people seem to be interested, which I find curious. Nice that you didn't initially make the connection, and it came to you later - that's a nice progression. Thanks for letting me know.
- techbio 8y agoI think of it like a coin counting machine.
- ColinWright 8y agoI don't see how that helps - can you elaborate?
- techbio 8y ago// usage: node coin_counter.js <p(k)> <k> const args = process.argv.slice(2); let p_of_x = Number(args[0]); // p(k) let x = Number(args[1]); // k const coins = {0:1}; let coin_ndx = 0; // compute the values of coins to add to purse total // exit loop when coin face value is too large to subtract from purse for (let n = 0; Math.pow(x, n) <= p_of_x; n++,coin_ndx++) { coins[coin_ndx] = Math.pow(x, n); // compute coin face values } console.log("Show face values of coins:"); let keys = Object.keys(coins); keys.sort(); // find the largest exponent (max_key) let max_key = 0; for (let key in keys) { console.log(key, coins[key]); max_key = key; // use current largest } console.log("Show polynomial"); let purse = p_of_x; // purse is sum of coins for (max_key; max_key >= 0; max_key--) { let count = 0; while (coins[max_key] <= purse) { purse -= coins[max_key]; count++; } console.log("+" + count + " x**" + max_key); } >node coin_counting.js 12028 7 Show face values of coins: 0 1 1 7 2 49 3 343 4 2401 Show polynomial Edit: exercise for the reader
- techbio 8y agoThe face value of each coin is multiplied by the count of the coin type to total to the purse. Or rather, the sum of the nth powers of k multiplied by each positive coefficient equals the value of the function at k. Edit: Source in sibling.
- ColinWright 8y agoWow, what an interesting approach! Thank you ... I've copied that out to a file and I'll study it more later. Cheers!
- nanis 8y agoThe question is not well defined. If m is the degree of the polynomial, you want ∀ i ∈ {0, ..., m}, c_i ≥ 0 and ∃ i ∈ {1, ..., m}, c_i > 0. Otherwise the solution is either trivial or not unique. > Do you find this interesting? Depends. For a pedagogical tool in 5th to 8th grades, maybe. There may be some reason it is a compelling exercise which I am not seeing though. So, you might want to explain why you find this interesting enough to post it twice.
- ColinWright 8y agoI find it odd that you think the question is not well defined. Choose a polynomial with non-negative integer coefficients. Note that under the usual conventions, the polynomials x^2+1 and x^2+0x+1 are the same. Does that cover the situation you're worried about? Seriously, I don't know anyone who would say that x^2+1 and x^2+0x+1 are different, so maybe I'm not seeing what you're worried about. However, given that, does it answer your objection? As to why I think it's interesting, I think it's slightly surprising that given k=6 and p(k)=665 then the polynomial is uniquely identified as 3x^3+2x+5. Do you not find that surprising? If you don't find it surprising, how would you explain it?
- nanis 8y ago> I find it odd that you think the question is not well defined. You must assume that at least some of the coefficients of the x terms are non-zero. > Do you not find that surprising? No. > how would you explain it? I think it is up to you to explain why this is interesting. Without the condition that k is greater than all the coefficients, the solution is clearly non-unique. Given that, the assumption of the coefficients are integers, and that the solution is not a constant polynomial, the statement becomes equivalent to "division is a function".
- ColinWright 8y ago>> I find it odd that you think the question is not well defined. > You must assume that at least some of the coefficients of the x terms are non-zero. That turns out not to be the case. >> Do you not find that surprising? > No. Interesting. >> how would you explain it? > I think it is up to you to explain why this is interesting. So far, many people who are clearly intelligent seem to miss that it works at all, let alone how it works. You appear so far to be among them. As I've said elsewhere, I appreciate that you are trying to poke holes in it, but it really is complete and correct as stated. > Without the condition that k is greater than all the coefficients, the solution is clearly non-unique. Well, yes. That's why having k greater than all the coefficients is a requirement. That's why your example in another comment elsewhere is not an example of the puzzle failing - it does not satisfy the condition that k must exceed all the coefficients. > Given that, the assumption of the coefficients are integers, and that the solution is not a constant polynomial, the statement becomes equivalent to "division is a function". I don't see why this is true - perhaps you could expand on it? Why is the problem statement equivalent to saying "Division is a function."? So now I don't understand what you're trying to say or do. The question as stated is fine - an example that doesn't satisfy the conditions isn't a counter-example. So at least one of us is confused. So let me state clearly, rather than having a bitty back'n'forth. You pick a polynomial p(x) with non-negative integer coefficients. You choose an integer k that's larger than all the coefficients of p(x). You tell me k and p(k). In return, I tell you p(x). So: Are you claiming this doesn't work? Are you claiming it's trivial to accomplish? Are you claiming it's obvious why it works? I'm no longer sure what you're claiming, so I thought I'd ask clearly and plainly.
- Someone 8y ago“Choose a polynomial p(x) with non-negative integer coefficients” I think you want to say positive there, or mathematicians will exploit the fact that common definitions (examples: https://en.wikipedia.org/wiki/Polynomial#Definition https://en.wikipedia.org/wiki/Polynomial#Definition, http://mathworld.wolfram.com/Polynomial.html http://mathworld.wolfram.com/Polynomial.html) of polynomial allow coefficients to be zero, making, for example, x + 1 (a polynomial of degree 1) different from 0 x² + x + 1 (a polynomial of degree 2) Reason for that choice is that it makes the set of polynomials of degree n closed under addition and subtraction)
- ColinWright 8y agoNope, I explicitly mean non-negative, because you are allowed polynomials like x^4+x+2. In particular, polynomials are considered equivalent if they differ only in terms that have zero coefficients. That means that 0x^2+x+1 is the same polynomial as x+1. Further, 0x²+x+1 is not a polynomial of degree 2, because the degree is the highest power with a non-zero coefficient. So the question is fine as it stands.
- nanis 8y ago[redacted because I was completely wrong, missing the obvious ;-)] ... See child comment.
- ColinWright 8y ago> No it is not. Your statement of the problem does not rule out only the coefficient of x^0 being positive, and the rest being zero. You are correct that we permit any and/or all coefficients to be zero, allowing the case that p(x)=665. That is intentional. > Just saying the coefficients are all nonnegative, the polynomial p(k) = 665 also is a solution for the case k = 6 and p(6) = 665. No it isn't, because you have evaluated at 6, which is not larger than all the coefficients. Specifically, 6 is not larger than 665. So I still claim that the question is fine as it stands. I do appreciate you trying to poke holes in it, though. Thanks. (Added in edit: Given that you've retracted that, would you like me to remove this comment?)
- impendia 8y agoOr, roughly equivalently, "our notation for writing down integers makes sense".
- artemisyna 8y agoIf we know what k is, we've got an upper bound on the value of the roots. Since we can express p(k) as (k-x_1)(k-x_2)...(k-x_n) (with x_i as roots), we know that each (k-x_i) must be an integer factor of p(k). Based on these facts, I'd probably just brute force it. Figure out the prime factorization of p(k), then figure out all of the ways to express the x_i. Note that this does also prove that the algorithm will not uniquely define an expression for p(k). For example, if p(10) = 12, then (x-4)(x-8), (x-7)(x-6), among others, satisfy. This is mildly interesting to think about as someone who never was a math major but maybe should have been. There are some interesting side bits (for example, disproving uniqueness) but it does feel like there are more "powerful" statements floating around this type of algebra.
- ColinWright 8y agoI think you are missing that the coefficients must be non-negative. In fact the answer is always unique, so you may want to rethink your approach.
- artemisyna 8y agoAh yeah, misread that there. Express p(k) in base k. Those are your coefficients. Pretty cute. :)
- matheist 8y ago> Can you work out how to do it? Yes. > Do you find this interesting? Yes! I found it interesting because at first it seems like the solution space ought to be many-to-one, not one-to-one, and it's not immediately clear why the condition that k is larger than the coefficients is the "right" condition to fix that. I had to work through some examples to see the trick of it. hints (rot13): 1. jungunccrafvslbhpubbfrxrdhnyfgjb 2. jungunccrafvslbhpubbfrxrdhnyfgra solution: jevgrcxvaonfrx
- ColinWright 8y agoExcellent - pleased you liked it. Here on HN we seem to be in a minority. And your answer is one of the two techniques I've got - nice one.
- quickthrower2 8y agovyvxrgbrknttrengr:jungunccrafvslbhpubbfrxrdhnyfbarzvyyvbanaqgurpbrssvpvragfneryrffgunagra
- ColinWright 8y agoThe simplest answer is for you to try it and see what happens. Nothing goes wrong, and it just makes the solution/technique more obvious.
- quickthrower2 8y agoThanks! I was just saying how I arrived at the answer, how my mind works, which I think is what the OP was looking to see - how people solve a problem like this. Hope this comes up in my next whiteboard interview :-)
- ColinWright 8y agoOh, OK, that wasn't obvious to me, but now is - thanks for the clarification, and for the answer. Interesting. Your technique, by the way, is a classic puzzle solving technique that I've used successfully many times, sometimes to great effect. Nice one.
- cm2012 8y agoIt's amazing how far away I am from being able to figure this out :)
- ColinWright 8y agoCool! It's nice that you've found this, and are interested. There are clues elsewhere in the thread, but email me for another clue, or an explanation. Address is in my profile.