6
$\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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Umm, the answer to this question is in the link you provided to your previous question. $\endgroup$
    – Daniel P
    Feb 19, 2018 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, 2018 at 22:13
  • $\begingroup$ @spellbee2 I never said the questions were the same. $\endgroup$
    – Daniel P
    Feb 20, 2018 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, 2018 at 17:57
  • $\begingroup$ @MichaelSeifert Ah, now I see what Gh0sT meant. Sorry about that... $\endgroup$
    – spellbee2
    Feb 20, 2018 at 20:06

1 Answer 1

Reset to default
10
$\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.

Improve this answer
$\endgroup$
8
  • $\begingroup$ You're too fast :P I'll accept within the next day or so. $\endgroup$
    – boboquack
    Feb 19, 2018 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, 2018 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, 2018 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, 2018 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, 2018 at 13:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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