I think another possible solution to the first puzzle is that everyone is lying.It felt like being back in logic class, p->q all over again :D
