4 ms·
Sorry, this is just a trivial observation, but if you're going to accept x + x + 100 = 500 and 3x - x = 400 you can probably list any variety along the line
by nawgszy 9y ago
Sorry, this is just a trivial observation, but if you're going to accept
x + x + 100 = 500
and
3x - x = 400
you can probably list any variety along the lines of
(n)x - (n - 2)x + y = 400 + y
so clearly that isn't a finite transformation space.
Now, these transformations might look trivial, but this problem is too. So there's an interesting question of bounding your algebraic transformations to a subset of all possible transformations that still make all possible solutions available, which ultimately doesn't answer yours.
- grondilu 9y agoTrue, it is not finite. Still, considering the algorithm will not attempt to search the tree exhaustively anyway, maybe the fact that the tree is infinite does not make much difference. PS. On second thought the number of rules is finite, so the number of possibilities has to be finite, at least if you apply the rules one at a time. It's the iteration of the rules that makes the tree infinite.
- groby_b 9y agoNope, a single rule still has an infinite number of possibilities. As an example, multiplying both sides of the equation with an arbitrary constant produces a new valid equation, and there's an infinite number of constants to multiply with. (Bonus point: You get to choose what kind of infinity - countable or uncountable) The reason a move tree[1] in a chess game has a finite number of nodes is not due to the finite number of possible transforms, but due to the fact that the number of possible board states is finite. [1] graph, really.