antidisestablishment's blog

Ask for the solution of CF1704F
By antidisestablishment, history, 2 years ago, In English

In the Editorial, it didn't explain the SG function has a cyclic section of length $$$34$$$ by strictly proof. So I hope someone can help me.

And another problem : Why the conclusion that problem-maker cannot prove can become a problem in the contest ?

  • Vote: I like it
  • +79
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +37 Vote: I do not like it

The game in which there is an alternating string of length $$$n$$$ is equivalent to the following impartial game:

  • Start with a heap of $$$n$$$ stones.
  • In each turn, remove 2 stones from a heap, and optionally split the heap into two heaps.

This is the octal game $$$0.07$$$, or Dawson's Kayles, whose nim-sequence is shown to have period 34 in Chapter 4 of the book Winning Ways for your Mathematical Plays by Berlekamp, Conway and Guy. (They also go further to show that we only need to check a finite number of nim-values to prove that the sequence of any octal game is periodic.)

→ Reply