Sofiya and Marquis are playing a game. Sofiya announces to Marquis that she’s thinking of a polynomial of the form f(x)=x^{3}+p x+q with three integer roots that are not necessarily distinct. She also explains that all of the integer roots have absolute value less than (and not equal to) N, where N is some fixed number which she tells Marquis. As a “move” in this game, Marquis can ask Sofiya about any number x and Sofiya will tell him whether f(x) is positive, negative, or zero. Marquis’s goal is to figure out Sofiya’s polynomial.
If N=3 \cdot 2^{k} for some positive integer k, prove that there is a strategy which allows Marquis to identify the polynomial after making at most 2 k+1 “moves”.