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:

There are

*k*piles of stones such that there are*a*_{i}stones in*i*'*th*pile.Alice and Bob are making moves alternatively, as Bob is gentlemen Alice starts first.

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.

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.

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?

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

ksuch that Alice will win, no matters whata_{i}is.P.S. Can anyone help me with math-version at least? :P

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

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

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.

If

k= 1 then Alice obviously wins.If

k= 2 then Alice wins iffa_{1}≠a_{2}.If

k= 3 then Alice always wins: Assume thata_{1}≤a_{2}≤a_{3}, Alice will empty the third pile and add (a_{2}-a_{1}) stones to the first pile, creating two identical piles.We claim that:

i) If

kis odd, Alice wins no matter what; andii) If

kis even, Alice LOSES iff there arek/ 2 pairs of identical piles, i.e.a_{2i - 1}=a_{2i}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, ask- 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: supposea_{1}≤a_{2}≤ ... ≤a_{k}, we will empty pilekand add (a_{2i}-a_{2i - 1}) stones to pile 2i- 1, creating a state which satisfies (*) and have an even number of piles. We can always do that sincea_{1}+a_{3}+ ... +a_{k}>a_{2}+a_{4}+ ... +a_{k - 1}.Edit: Oops, I meant (*) was the losing condition for even

k, not winning :(Thanks, very nice! I think I proved second observation, but how to prove 3rd?

Suppose

a_{1}≤a_{2}≤ ... ≤a_{k}, we reducea_{k}toa_{1}and add (a_{2i + 1}-a_{2i}) to pile 2i, moving to state (a_{1},a_{1},a_{3},a_{3}, ...,a_{k - 1},a_{k - 1}). This move is always valid, since there exists at least oneisuch thata_{2i - 1}<a_{2i}, which meansa_{1}+a_{3}+ ... +a_{k - 1}<a_{2}+a_{4}+ ... +a_{k}holds.The problem F from Datatähti Open 2018 is very similar to this one, you can try to solve it here.

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

Let's ask our announcer pllk :D

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.