According to the World Rock Paper Scissors Society, "the symbolic meaning of paper covering a rock dates back to ancient Chinese culture. When a petition was made to the Emperor, the petition was signified by a rock. Upon making a decision, the Emperor would have his servants place a sheaf of paper either over or under the rock. If the sheaf was placed under the rock, it would signify acceptance of the petition. If the sheaf was placed on top of the rock, it signified denial of the petition. Over time the symbolic image of paper covering a rock became synonymous with defeat."
-- from http://en.wikipedia.org/wiki/Stone,_Paper,_Scissors |