I was doing this problem on Spoj. The solution of this problem is that first player always wins.

Can anyone give me proof of this?

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | Um_nik | 3567 |

3 | tourist | 3520 |

4 | maroonrk | 3421 |

5 | apiadu | 3397 |

6 | 300iq | 3317 |

7 | ecnerwala | 3309 |

8 | Benq | 3283 |

9 | LHiC | 3229 |

10 | TLE | 3223 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 194 |

2 | antontrygubO_o | 193 |

3 | vovuh | 178 |

4 | pikmike | 177 |

5 | Radewoosh | 168 |

6 | tourist | 166 |

7 | Um_nik | 165 |

8 | ko_osaga | 163 |

9 | McDic | 162 |

9 | Ashishgup | 162 |

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/07/2020 10:12:57 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Proof by contradiction :

Say the initial state is always a losing state. This means regardless of the number the first player picks , the second player ends up with a winning state (if not , the initial state would have been a winning state). Say the first player picks 1 and the second player ends up with {2,3,4,.....,N} which is a winning state. Say the second player picks X now and provides the first player with state S (a losing state) , the first player could have just picked X and forced the second player to state S ( a losing state) which is a contradiction. Hence the first player always wins.

Thank you very much.

Thanks.. :))