One clarification, at least for me, would have been the details of Random.
My assumption, was that Random would answer any question randomly, either yes or no, in which case it really didn't matter what the question was since it would have no bearing on his answer.
But the solutions appear to be based on Random's answers being consistent. So Random isn't Random on a question by question basis, but rather upon meeting you, the choice is made to either always lie, or always tell the truth. You don't know which he will choose, but he won't change question to question.