5
$\begingroup$

Alice: Let's play a game, Bob!
Bob: (sighing) What is it this time?
Alice: I'm thinking of a polynomial $P$ with integer co-efficients. For any integer $n$, you can ask me what $P(n)$ is. Then, if, after a while, you guess correctly what $P(2.018)$ is, you win! Otherwise, I win.

Bob(oquack?) searches up the ever-handy PSE.

Bob: We did this just over two years ago!
Alice: Did we now? Oh well, I suppose you'll have an advantage. So what are you complaining about? Let's play!
Bob: (sighing again) Okay… what's $P(1)$?
Alice: It's 1.
Bob: Hmm… what's $P(10)$?
Alice: It's 10.
Bob: Then using my astonishing powers of deduction, I conclude that $P(2.018)=2.018$.
Alice: You're wrong! I choose $P(x)=x^2-10x+10$, giving $P(2.018)=-6.10768$.
Bob: But you said they were pos... oh, you didn't, did you.
Alice: Want to play again?

Can Bob still be guaranteed to win? If so, what is the fewest number of moves in which winning is always possible?

$\endgroup$
  • 1
    $\begingroup$ Umm, the answer to this question is in the link you provided to your previous question. $\endgroup$ – Daniel P Feb 19 '18 at 21:46
  • $\begingroup$ @Gh0sT There's a key difference in this one, however: the coefficients can be positive or negative, unlike the linked question which can only have positive coefficients. $\endgroup$ – spellbee2 Feb 19 '18 at 22:13
  • $\begingroup$ @spellbee2 I never said the questions were the same. $\endgroup$ – Daniel P Feb 20 '18 at 10:36
  • $\begingroup$ @spellbee2: The answer to this question is in the answer given by Penny Hassett to the previous question. It was an incorrect answer for that question, but it's the correct answer here. $\endgroup$ – Michael Seifert Feb 20 '18 at 17:57
  • $\begingroup$ @MichaelSeifert Ah, now I see what Gh0sT meant. Sorry about that... $\endgroup$ – spellbee2 Feb 20 '18 at 20:06
9
$\begingroup$

Can Bob be guaranteed to win?

No. No matter how many guesses $x_1,x_2,x_3,\ldots,x_n$ Bob makes (as long as it's finite), the polynomial $(x-x_1)(x-x_2)\cdots(x-x_n)$ is indistinguishable from the zero polynomial.

But what if...

Bob can make infinitely many guesses? If so, he can win: he would just ask for the point at each natural number, and then take successive differences until he gets a constant sequence.

$\endgroup$
  • $\begingroup$ You're too fast :P I'll accept within the next day or so. $\endgroup$ – boboquack Feb 19 '18 at 21:24
  • $\begingroup$ Re: 2nd spoiler, maybe Bob could win, but I'm so impossibly dreadful at math, even with infinite non-repeating guesses I would never get it $\endgroup$ – ferret Feb 19 '18 at 22:02
  • 2
    $\begingroup$ @frabjrew Well, it's not your fault! Your infinitely many guesses would work, but they'd require you to calculate infinitely many subtractions, and I'm sure anyone would be tripped up by that. $\endgroup$ – Deusovi Feb 19 '18 at 22:23
  • 2
    $\begingroup$ The sad thing is that Bob will always be able to arrive at the correct polynomial in a finite number of steps, but he will never know for sure when he's actually found it. Even if he's asked for a hundred points and they all seem to lie on a straight line, he can't be sure Alice hasn't made a degree 100 polynomial that feigns being a straight line through those points. Alice can be so sneaky. $\endgroup$ – Jaap Scherphuis Feb 20 '18 at 12:26
  • $\begingroup$ What about those that have value 1 at x=1 and 10 at x=10? Your answer doesn't rule out the possibility to uniquely find it, it just says that there is a polynomial you cannot find for sure. $\endgroup$ – Florian Bourse Feb 20 '18 at 13:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.