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

Правка en1, от 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)?

Теги grundy, sprague-grundy, binary, base

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский cyan17 2024-08-24 19:10:39 46
en1 Английский cyan17 2024-08-23 17:57:05 1614 Initial revision (published)