Suppose a polynomial with rational coefficients takes an integer value for all non-decreasing integers. In a nondecreasing integer, the digits never decrease from left to right. Examples include 122, 123, 224, and 237. Must it be true that the polynomial takes an integer value for all integer inputs?

My idea was to use induction on the degree. Basically it goes something like this: For a degree $n$ polynomial $P(x)$ define $d(x)=P(x+1)-P(x)$. But the induction sadly fails, since we can't conclude that $d(x)$ is an integer on all non-decreasing integers (we can get close). Any ideas?

  • 1
    $\begingroup$ THIS IS ON USAMTS. DELETE THIS QUESTION NOW $\endgroup$ – mathworker21 Dec 26 '17 at 4:37
  • $\begingroup$ @mathworker21 Just flag the question, and notify the moderators. $\endgroup$ – Matemáticos Chibchas Dec 26 '17 at 5:25
  • $\begingroup$ I think I have a generalization that is true, but I won't post it because of the USAMTS. $\endgroup$ – marty cohen Dec 26 '17 at 6:49

I am pretty sure that any such polynomial must take on integer values for all $x\in\mathbb{Z}$. The problem lies in the notion of "nondecreasing integers," which are not well-defined once you consider different bases. For example, $$122_{10}\equiv 1111010_2,$$ which is certainly not non-decreasing.

  • 2
    $\begingroup$ This is a comment, not an answer. $\endgroup$ – J.-E. Pin Dec 26 '17 at 4:36
  • $\begingroup$ Isn't the fact that we're working in base 10 implicit in the problem? $\endgroup$ – Tiwa Aina Dec 26 '17 at 4:49

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.