Problem
COM-B1-M08-P015 Moves \(1,3,4\)
#15
★★★☆☆ Level 3 of 5
There are \(31\) stones. In one move, a player may take \(1\), \(3\), or \(4\) stones. The last move wins. Find a winning first move.
The losing residues modulo \(7\) are \(0\) and \(2\).
Check positions with residues \(0\) and \(2\) modulo \(7\). From them, moves \(1,3,4\) never lead again to residues \(0\) or \(2\). From every other residue one can move to \(0\) or \(2\): from \(1\) take \(1\), from \(3\) take \(1\), from \(4\) take \(4\), from \(5\) take \(3\), from \(6\) take \(4\). Thus the losing positions are residues \(0\) and \(2\) modulo \(7\). Since \(31\equiv3\pmod7\), the first player takes \(1\) stone and leaves \(30\equiv2\pmod7\).
Good task for building a table of losing residues.