By MohamedHamada_, history, 13 months ago, ,

I was solving the problem UVa 10368 and after thinking for a while i came up with this solution:

The first player have a number n%m == 0 or n/m > 1 is the winner and got AC ! :D

I just observed this solution when i tried some numbers on a paper but i actually don't have a rigorous proof for that ! could you demonstrate why this solution works ?

 » 13 months ago, # | ← Rev. 5 →   0 The following is a possible proof: The initial pair (m, n), where 0 < m ≤ n can be rewritten as (m, qm + r) where q ≥ 0 and 0 ≤ r ≤ m - 1 are quotient and remainder of the integral division div(n,m), respectively. Case 1: If r = 0, then the game is over, as the player can immediately subtract qm from n to make the next number zero and win. Case 2: If r > 0 and q > 1, then the next pair is (m, (q - k)m + r), where 1 ≤ k ≤ q. If k < q is chosen, then (q - k)m + r > m and the smaller number in the next pair is m. It is then guaranteed that the next remainder of dividing (q - k)m + r by m is non-zero as r > 0. Consequently, it is guaranteed that the other player does not win in the next play. The following is a slight update to your program using the standard library function div(n,m).