Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider $n$ piles of coins, with pile $i$ having $a_i$ coins. A valid move is to remove zero or more coins from each of the piles, with the constraint that atleast one pile should remain unchanged, and with the goal that after the move, the XOR sum of all the pile sizes should be $0$.

Given some game configuration (where the XOR sum or nim-sum is not already $0$), how many valid moves are possible, that bring the XOR sum to $0$?

The range of coins in each pile can range up to $10^9$ (30 bit numbers), and there could be around 100 piles, so a brute force is out of the question. The solution needs to be efficient in terms of time complexity.

This was a question I encountered in a programming contest, which is long since over and closed. I was trying to use induction to get a recursive formulation, but could not do so. How can we count the number of moves?

share|improve this question
    
My phone fails to let me do searches on MSE (and google adds another layer of distance). But I am fairly certain I have seen a (simpler, less general) variant of this question recently on MSE. Last I looked at it then, it remained unsolved, but discussed. Maybe if you (someone) find(s), this would be a first step. –  gnometorule Feb 5 '13 at 16:10
    
@gnometorule: Likely you were remembering this problem, It seems like a nim variant. –  hardmath Feb 5 '13 at 19:15
    
@hardmath: good link, probably better than the one I remembered, but different. The one I had in mind had "XOR" in the title I believe, but no reference to nim I think in question text. –  gnometorule Feb 5 '13 at 19:23
2  
@gnometorule You probably meant this one: math.stackexchange.com/questions/293339/… . My question is harder in the sense that there must be atleast one unchanged pile. –  mayank Feb 5 '13 at 19:40
    
@mayank: That's the one. Unfortunately, it apparently went nowhere after I stopped checking up on it. :( –  gnometorule Feb 5 '13 at 21:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.