January Maths Puzzle
Here at G-Research we’re always focused on predicting the future through data. This involves tackling a wide variety of mathematical challenges, and it’s become our favourite pastime to come up with challenging problems to try and solve.
In the past we’ve sponsored the IMO, and have also run a maths competition to support wider efforts to tackle maths problems in creative ways.
This month, we’re looking at the below puzzle, though we haven’t been able to solve it conclusively yet.
It relates to the game of “Nim with a pass” which we first introduced during our summer IMO Challenge:
Nim* is a game similar to Nim, with one difference: there is a single ‘passing token’ which either player may take in lieu of their turn if it is still available. Once either player takes the passing token the game plays exactly like a normal game of Nim. The game ends when there are no stones left, regardless of whether or not the passing token has been taken. The game is played under normal play convention, ie the last player to make a move wins.
The initial state contains the passing token in addition to piles of size 1, 3, 5, . . . , 2019.
Given that context, here is our January Problem:
In the above game, define a state as being sporadic if the state (P/N) is different from what you’d get if you replaced the pass token with a pile of size 1, otherwise non-sporadic. Define a state as strongly non-sporadic if all supersets of the state (i.e. adding extra piles, but not changing the existing piles) are non-sporadic. Show that all strongly non-sporadic states contain two disjoint subsets of piles, each with nim sum=1.
Think you have the answer? We’d love to discuss it with you! Drop us a line at firstname.lastname@example.org or check out our Quantitative Research openings and apply now to get in touch with us to chat in person.