Ugh, so coming up with a perfect solution to a riddle isn't enough in an interview now apparently. You guys just can't be pleased :)

Perhaps you can simply ask how they arrived to their solution, you owe them at least that. Or be upfront that they should reason aloud.