Блог пользователя antidisestablishment

Ask for the solution of CF1704F
Автор antidisestablishment, история, 2 года назад, По-английски

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 ?

  • Проголосовать: нравится
  • +79
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

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.)

→ Ответить