How many solutions are there for equation $x^2\equiv y\pmod N$?
That problem is easier when $N$ is odd and $\gcd(y,N)=1$ (notice that when either does not hold, we have a factor of $N$): there are either $0$ or $2^k$ solutions, where $k$ is the number of distinct primes $p_i$ dividing $N$. Proof starts with $N$ prime (see Legendre symbol), then a power of a prime, then the product of powers of distinct primes (using the Chinese Remainder Theorem).
Why the algorithm $A$ would always return the same output?
The proof thought to answer the question should work including when the algorithm $A$ always return the same output $x$ for input $(y,N)$, because nothing in the question's assumption "Suppose.." says that $A$ will return all solutions, or would eventually return all solutions when invoked repeatedly. Many algorithms are deterministic, that is always perform the same operations for a given input, including producing the same result. Actually, in cryptography, we often implicitly restrict to such deterministic algorithms, considering that a random behavior must come from an explicit extra random input.
Hint: you want to have two solutions: one you know beforehand, and one that the algorithm will give you. The algorithm can't read your mind, thus there's a chance that it will return another solution, and perhaps that will be helpful.