Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] 12/15/2008 11:29:00 AM

Expand Messages
  • GASARCH
    I made up the following problem which was on the Univ of MD Math Competition for HS Students Part II. (It was question 3 of 5, indicating intermediary
    Message 1 of 1 , Dec 15, 2008
    • 0 Attachment
      I made up the following problem which was on the Univ of MD Math Competition for HS Students Part II. (It was question 3 of 5, indicating intermediary difficulty.) It leads to other questions that may be open and/or interested. I state it differently then it appeared so I can more easily state the other questions.
      Let A&sube N - {0}. Let n&isin N. NIM(A,n) is the following game: There are initially n stones on the table. Players I and II alternate removing stones from the table. They can remove x stones iff x &isin A. The first player who can't move loses. Let SQ be the set of squares. Show that there exists an infinite number of n such that Player II wins NIM(SQ,n).
      1. Most people who read this blog should be able to do this problem. The solution is at the link above.
      2. Let p &isin Z[x]. Let Ap = { p(x) : x &isin Z, p(x)>0 } It is easy to show that there are an infinite number of n such that player II wins NIM(Ap,n).
      3. Let POW2 be the set of powers of 2. Let A=N-POW2. It is easy to show that there are only a finite number of n such that player II wins NIM(A,n).
      4. OPEN: classify exactly which A are such that there are an infinite number of n such that Player II wins NIM(A,n). (Note- it may not have a nice classification.)


      --
      Posted By GASARCH to Computational Complexity at 12/15/2008 11:29:00 AM
    Your message has been successfully submitted and would be delivered to recipients shortly.