Given three positive number n, x and y. Player A know x + y and player B know x * y. Each player takes turn to guess x and y (x, y <= n). Player will say "I don't know" if they cannot guess the answer or if they certainly know the answer, they guess it and end the game. Count the number of "I dont't know" during the game.
What algorithm used to solve this kind of problem?
I have tried to google it but cannot get the answer.
Edit:
For example, n = 10, x = 3, y = 6. The game happens as follow:
A: I don't know.
B: I don't know.
A: I don't know.
B: I don't know.
A: It's 3 and 6!
Actually, there is a case where they cannot guess the answer: n = 10, x = 3, y = 5 and the game go as follow:
A: I don't know
B: I don't know
A: I don't know
B: This game will play forever, let stop it here.
I also ran into this exact problem when teaching high schoolers competition maths. To explain the problem to other readers:
The two players are competing against each other, they are given the information n, but not the two numbers. The goal is to find the two numbers. Let's say the numbers are 3 and 6, and the upper limit (n) is 10. Player A knows the sum of the numbers: 9, and player B knows the product: 18. They alternate turns based on whether they know what are the numbers.
In the beginning, A knows that there are 4 possibilities: (1,8), (2,7), (3,6), (4,5), based on knowing that the sum is 9. He says "I don't know", and now the next turn is player B's. He knows the product is 18, so there would be three opportunities: (1,18), (2,9), (3,6), but the first one is not possible, as 18 is bigger than 10, so there are only two possibilities. He says "I don't know", he can't decide between the two possibilities.
Now comes player A. He actually can cancel out the possibility of (2,7) now solely from the information that player B said "I don't know". Because if (2,7) were the numbers, the product would be 14 (which player B would know), and as (1,14) is not possible due to n=10, player B would know (2,7) are the numbers and say he knows these are the numbers. But he didn't, so (2,7) is not a possibility anymore. All other possibilities stay, so he again says "I don't know", as there are 3 opportunities still.
Continuing this logic, you can show player B next step still does not know the answer, after which player A knows it and wins.
The way you can solve these kinds of problems is via Game trees, I recommend reading about them (although they are not designed for these problems, see bottom note). The basic idea of game trees is that finite games have finite possible steps, and you can build a hierarchical diagram of steps, with "game ending positions" (win/lose/draw), and from the bottom the Xth layer is X-1 steps away from a game-ending position. It's common for determining winning and losing positions. For example, in chess, the bottom of the tree would be all checkmating positions possible, and all drawing positions (chess game "tree" is a little bit more complicated because of this, since there are repetitions, which mess up the tree). The layer above the bottom layer is all positions from which you can reach checkmate in 1, and so on.
In your game, I recommend implementing such a game tree, but carefully. You might optionally create two trees: one from player A's view and one from player B's view, but maybe one tree is simpler to implement. In each step, you store the set of possibilities for an (x,y) pair according to both players, and whenever one player says "I don't know", update the other player's set of possibilities (he may cancel out some possibilities, the case of those possibilities, where the other player would not have said "I don't know", but the two numbers). When it's a player's turn and their list of possibilities only has 1 (x,y) pair is when that player wins. The infinite game would appear when both players consecutively couldn't cancel any possibilities after the other player said "I don't know". This way, you'd have an infinite tree, but you could find this information by checking that if there were two consecutive steps where players said I don't know and no possibilities were cancelled.
(Note: In all fairness, trees are not needed here, as all steps are decided in advance, because the two players don't make decisions, they just say the correct answer. You only need a "series", not a tree. But this method works here too.)