Mary and Pat play a number game, smallest initial integer for Pat not winning
Source: Irmo 2018 p1 q1
September 16, 2018
game strategygamenumber theoryminimum
Problem Statement
Mary and Pat play the following number game. Mary picks an initial integer greater than . She then multiplies this number by and adds to the result. Pat will add to this new number and it will again be Mary’s turn. Both players will continue to take alternating turns. Mary will always multiply the current number by and add to the result when it is her turn. Pat will always add to the current number when it is his turn. Pat wins if any of the numbers obtained by either player is divisible by . Mary wants to prevent Pat from winning the game.
Determine, with proof, the smallest initial integer Mary could choose in order to achieve this.