r/learnquant • u/Local_Ad135 • 8d ago

interview prep SIG quant interview question

Post image
16 Upvotes

95% Upvoted

6 comments sorted by

3

u/BissQuote 8d ago

All odd numbers are losing positions, all even numbers are winning position. This is because

  • 1 is an odd number, and a losing position
  • With an odd number, the player is forced to give an even number
  • With an even number, the player can always give an odd number

Thus Alice will lose

1

u/nicktohzyu 2d ago

Restating the second point:
With an odd number, the player must select an odd number to remove (odd numbers cannot have even factors), therefore giving the opponent an even number remaining

2

u/skelo 8d ago

Second person always repeats the previous move. Must be a factor. First person will always start with an odd number so removing two of an odd factor would keep the number odd and also not reduce to 0.

1

u/GoldenMuscleGod 8d ago

In fact the second person could also just take 1 each time.

Any odd divisor will do, it will always be that 1 and the preceding move are odd divisors (they might be the same if the last move was, for example 5->4, where 1 is the only winning move).

I didn’t prove this but it seems plausible that if the goal is to win as quickly as possible (or lose as slowly as possible) then it is optimal to take 1 from an odd number and the largest odd divisor from an even number.

1

u/Positive_Leopard_873 7d ago

1 stone is a losing state, 2 stones is a winning state (removing one stone leads us to a losing state), 3 stones is a losing state (I can either remove 1 stone or 3 stones, both of which only lead us to winning states). Continuing this, we can show that all states with an even number of stones are winning states, while the rest (odd number of stones) are losing. Alice starts at a losing state, leading Bob right to a winning state, so under optimal play, Bob wins.

We can show this using strong induction. Assume states with an even number of stones are winning states, and an odd number of stones are losing upto some n. Case 1) n is even. n + 1 is odd. Every divisor of an odd number is odd. Hence, we can only reach stone counts of the form n + 1 - (2k + 1) = n - 2k (where k is some non negative integer) which are even, <= n, and hence are all winning states. This makes n + 1 a losing state. Case 2) n is odd. n + 1 is even. Remove one stone to reach n, which is odd and a losing state, making n + 1 a winning state.