Grundy Numbers: Why is the binary representation of a number special?

Revision en1, by cyan17, 2024-08-23 17:57:05

A note

Before I begin, I would I like for readers to note that this blog does not offer a "solution", it is merely my thoughts which I hope spark an interesting discussion and hopefully lead to some conclusions or atleast provide some clarity.

After the recent codeforces round which featured a problem which can be solved using grundy numbers. After the end of the contest I revisited grundy numbers. (You can read about it here and here).

The Motivation

I began to wonder why it is that the binary representation of the numbers are so crucial to this solution. And after sometime I think I found an answer.

The "ANSWER"!

I think the answer is... there isn't anything special about the binary representation of numbers! I think that there are ways to formulate a solution to a grundy problem which would use the base-$$$n$$$ representation of numbers for any $$$n$$$. Of course these formulations may be more complicated but they must exist, no?

A technicality?

Of course, one trivial formulation for every base-$$$n$$$ would be converting it to binary and then xor-ing the numbers as before. I only want to focus on formulations do not do this, or something equivalent. However, this might be problematic too. Perhaps any formulations that do exist could be shown to equivalent to the one described here (converting to binary and then xor-ing)?

Tags grundy, sprague-grundy, binary, base

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English cyan17 2024-08-24 19:10:39 46
en1 English cyan17 2024-08-23 17:57:05 1614 Initial revision (published)