Like I said, I have no desire for them to create the "perfect, correct" solution; but I do want to know how they think about a problem and what questions they ask in the face of deficient information. I proactively encourage them to do so, so I am not trying to trick them into failure or anything.
It seems like you're very interested in people asking questions like "how big might the array be" or "what order of time can you afford to wait for the answer to this", to which you might answer "a billion" or, "as little as possible", but those questions are very different and less meaningful than questions like "how many users will this system have", and "how much time can users of this system afford to wait for a response", even though the answers may be the same.
I have to say, I respond quite differently to "I have a problem I'm trying to solve" vs something like "I need this algorithm implemented", and a lot of the way these programming challenges are presented always come off to me as the latter, and as a result, contrived.