### TooNewbie's blog

By TooNewbie, 11 months ago, ,

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!

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

•
• +48
•

 » 11 months ago, # | ← Rev. 2 →   +18 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?
•  » » 11 months ago, # ^ | ← Rev. 2 →   +18 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
 » 11 months ago, # |   +5 I don't think I understand. With these rules number of stacks always decreases by exactly one. What's the problem then?
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 11 months ago, # ^ |   +10 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.
•  » » 11 months ago, # ^ | ← Rev. 2 →   +28 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.
 » 11 months ago, # | ← Rev. 2 →   +89 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; andii) 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 :(
•  » » 11 months ago, # ^ |   +13 Thanks, very nice! I think I proved second observation, but how to prove 3rd?
•  » » » 11 months ago, # ^ |   +10 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.
 » 10 months ago, # |   +4 The problem F from Datatähti Open 2018 is very similar to this one, you can try to solve it here.
•  » » 10 months ago, # ^ |   +1 Thanks for giving that information. I'm curious about did author of problem got motivation from this blog :)
•  » » » 10 months ago, # ^ |   +1 Let's ask our announcer pllk :D
•  » » » 10 months ago, # ^ |   +17 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.