6

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?

Wen1now
  • 9,253
  • 4
  • 33
  • 86
boboquack
  • 21,982
  • 1
  • 66
  • 138
  • 1
    Umm, the answer to this question is in the link you provided to your previous question. – Daniel P Feb 19 '18 at 21:46
  • @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. – spellbee2 Feb 19 '18 at 22:13
  • @spellbee2 I never said the questions were the same. – Daniel P Feb 20 '18 at 10:36
  • @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. – Michael Seifert Feb 20 '18 at 17:57
  • @MichaelSeifert Ah, now I see what Gh0sT meant. Sorry about that... – spellbee2 Feb 20 '18 at 20:06

1 Answers1

10

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.

Community
  • 1
Deusovi
  • 146,248
  • 16
  • 519
  • 609
  • You're too fast :P I'll accept within the next day or so. – boboquack Feb 19 '18 at 21:24
  • 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 – ferret Feb 19 '18 at 22:02
  • 2
    @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. – Deusovi Feb 19 '18 at 22:23
  • 2
    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. – Jaap Scherphuis Feb 20 '18 at 12:26
  • 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. – Florian Bourse Feb 20 '18 at 13:54
  • @FlorianBourse The question was whether Bob can always be guaranteed to win. I answered that. (But in your case, any valid polynomial can have (x-1)(x-10) added to it, so Bob still can't know. Same for all other cases with finitely many guesses.) – Deusovi Feb 20 '18 at 14:06
  • Don't you need to show there can a different value of $P(2.018)$, not simply a different $P$? – Ankoganit Feb 22 '18 at 05:12
  • @Ankoganit I agree, but it is pretty obvious that the integer polynomial that can be added without affecting the guessed values will be non-zero at the non-integer value of $2.018$. – Jaap Scherphuis Feb 22 '18 at 10:15