TooNewbie's blog

Game theory problem
By TooNewbie, 7 years ago, In English

Alice and Bob are bored from playing Nim, so they modified that game — ArbiNim has been created just now. Rules of game is very simple:

  1. There are k piles of stones such that there are ai stones in i'th pile.

  2. Alice and Bob are making moves alternatively, as Bob is gentlemen Alice starts first.

  3. In each move, player selects one of non-empty piles and takes some of stones from that pile and throws away. From remaining stones (if there are) in selected pile, player takes any number of stones again and distributes them arbitrarily to non-empty piles.

  4. The player who takes last stone wins.

Bob can be gentlemen and give some opportunities to his opponent Alice the optimal mover, but as we know, he is merciless in games, he will play optimal also!

Your task is determining winner of game, GAME ON!

P.S. If you know source of problem or some judge to submit, please mention it.

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

»
7 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

Have you seen this problem anywhere (or just came up with it)? Is it possible that it's unsolvable? If you did see it somewhere, could you provide a link?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +18 Vote: I do not like it

    Maybe I did mistake with modifying problem a little (maybe this little gets bigger than old one :P). It's from our IMO training problems (I really don't know source).

    In math-version it asks find all k such that Alice will win, no matters what ai is.

    P.S. Can anyone help me with math-version at least? :P

    → Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I don't think I understand. With these rules number of stacks always decreases by exactly one. What's the problem then?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think so too. That makes the answer depend only on the parity of n. But it would be challenging if the one who takes the last stone loses.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      It still seems easy. No matter what happens before, on the last stack player who moves can leave exactly one stone, in this case he wins. This is only impossible when the stack has exactly one stone. Hence, the player should focus on having a possibility to move on one >1 stone pile in the last move, and the other one should prevent it.

      Now we're left with a simple greedy. Nice problem, though.

      → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +28 Vote: I do not like it

    Yes, you misunderstood. Number of piles can remain same in move. For example, if there are 10 stones in first pile, player can take 4 of them and throw away, from remaining 6, player can take 5 of them, and put 2 of them to second pile, 3 of them to third pile (if second and third piles exists and they are not empty). So, in first pile there is 1 stone now.

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +89 Vote: I do not like it

If k = 1 then Alice obviously wins.

If k = 2 then Alice wins iff a1 ≠ a2.

If k = 3 then Alice always wins: Assume that a1 ≤ a2 ≤ a3, Alice will empty the third pile and add (a2 - a1) stones to the first pile, creating two identical piles.

We claim that:

i) If k is odd, Alice wins no matter what; and

ii) If k is even, Alice LOSES iff there are k / 2 pairs of identical piles, i.e. a2i - 1 = a2i holds for all 1 ≤ i ≤ k / 2 if we sort the piles in increasing order (we define this condition as (*)).

For even k, it is easy to see that both players want to avoid emptying piles, as k - 1 piles yield a win for the opponent (by induction). Hence, whoever moves to state (1, 1, ... 1) wins.

We observe that:

  • The terminal state satisfies condition (*).

  • It is impossible to move from a state which satisfies condition (*) to another state which also does.

  • It is always possible to move from a state which does not satisfy (*) to a state which does.

(the last two observations are pretty complicated I cannot explain them properly =( ).

Anyway, we can deduce that (*) is the losing condition for even k.

For odd k, things are a tad easier: suppose a1 ≤ a2 ≤ ... ≤ ak, we will empty pile k and add (a2i - a2i - 1) stones to pile 2i - 1, creating a state which satisfies (*) and have an even number of piles. We can always do that since a1 + a3 + ... + ak > a2 + a4 + ... + ak - 1.

Edit: Oops, I meant (*) was the losing condition for even k, not winning :(

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Thanks, very nice! I think I proved second observation, but how to prove 3rd?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Suppose a1 ≤ a2 ≤ ... ≤ ak, we reduce ak to a1 and add (a2i + 1 - a2i) to pile 2i, moving to state (a1, a1, a3, a3, ..., ak - 1, ak - 1). This move is always valid, since there exists at least one i such that a2i - 1 < a2i, which means a1 + a3 + ... + ak - 1 < a2 + a4 + ... + ak holds.

      → Reply
»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

The problem F from Datatähti Open 2018 is very similar to this one, you can try to solve it here.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thanks for giving that information. I'm curious about did author of problem got motivation from this blog :)

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Let's ask our announcer pllk :D

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      Seriously, I wasn't aware of this blog post. The problem for Datatähti was created by mango_lassi and others during their NWERC trip last year.

      → Reply