Rei's blog

Round 51, A
By Rei, 14 years ago, translation, In English
Problem A.
This problem is solved by simple emulation. After 2n jumps flea returns to initial position, because 1 + 2 + 3 + ... + 2n = n(2n + 1) is divisible by n. Moreover, after that, jumps would be the same as in the beginning, because 2n is divisible by n. So it is just enough to emulate first 2n jumps.
In fact one may see that it is enough to emulate first n jumps and moreover answer is "YES" exactly when n is power of two. Last gives alternative solution. For example: printf("%s", n&(n-1) : "NO" ? "YES");

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

Comments Comments (3)
| Write comment?
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can you please explain how did you deduce that answer will be yes only when n is a power of 2??
→ Reply
  • 14 years ago, # ^ |
    ← Rev. 5   Vote: I like it +4 Vote: I do not like it
    Let n be a power of two: n = 2m. Let us prove that first n - 1 jumps will end at different hassocks. Really, jump with number k ends at hassock . Suppose that jumps k1 and k2 ends at the same hassock. It means that . So we get that k12 + k1 - k22 - k2 = (k1 - k2)(k1 + k2 + 1) is divisible by 2m + 1. But k1 - k2 and k1 + k2 + 1 have different parity and both less than 2m + 1. A contradiction. So we derive that all hassocks will be visited after first n - 1 jumps.

    If n isn't a power of two, then n is divisible by some odd prime p. Let's look at hassocks not mod n, but mod p. We will see that not all residues (mod p) will be visited. Indeed after p jumps flea returns to initial residue mod p, because is divisible by p. And after that jumps would be the same as in the beginning (mod p), because p is divisible by p. Moreover, even after p - 1 jumps flea returns to initial residue mod p. So there are p - 1 different residues as maximum. Thus not all hassocks will be visited.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Ya please explain why n should be a power of 2 ?
→ Reply