tag:blogger.com,1999:blog-3722233.post7333291716679702160..comments2019-10-21T21:47:16.813-04:00Comments on Computational Complexity: A NIM-game and some possibly open problemsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-3722233.post-5638550707097262432008-12-15T15:59:00.000-05:002008-12-15T15:59:00.000-05:00I AGREE with the corrections of Michael Forbes. Th...I AGREE with the corrections of Michael Forbes. Thank you.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19198095694520108192008-12-15T15:27:00.000-05:002008-12-15T15:27:00.000-05:00For question (2) I imagine the solution is the sam...For question (2) I imagine the solution is the same idea as for (1), namely that in the sequence p(x), x\in\mathbb{Z}, there must be arbitrarily large gaps. However, this only works for polynomials of degree >=2. Further, the result doesn't hold for linear polynomials (especially any of the form p(x)=x+a, integer a). Moreover, there are problems with the fact that an arbitrary polynomial might not assume the value 1, so it could be the case that neither player wins, especially if the game starts with 1 stone. I think the problem would have to be stated more carefully to explore (4).<BR/><BR/>I agree with the result in (3), but only if we take the convention that 1 is not a power of 2 (contrary to what I am used to).Michael Forbeshttp://www.mit.edu/~miforbes/noreply@blogger.com