In each node of a simple unweighted n-node graph G there lives a citizen. Tomorrow morning, the citizens of G are about to vote "Yes/No" on a critical and highly controversial proposition whose details I could never really figure out.
Out of curiosity and boredom, each citizen of G spends the afternoon amusing himself by conducting a private poll among his neighbors (including himself), in order to get a sense of the outcome of this all-important election. The alarming and disappointing result found by each "Yes" voter is an astounding 3:1 majority for the "No" voters in his neighborhood.
Should the "Yes" voters be worried?! Should the "No" voters rejoice?! Can all these polls lie?? In short: What can be said with certainty about the minimum guaranteed number of "No" voters in tomorrow's election, given these poll results?
The result of a 3:1 majority for the "No" voters in the neighborhood, was found by EACH and EVERY voter (not just the "Yes" voting ones).
What can be guaranteed now about the minimum number of "No" voters in the election?
In order to strengthen the validity of the polls, each citizen performs his poll among all citizens in distance up to 4 from himself. Alas, the poll results remain the same.
What can be deduced now, in both previous cases?
If you are interested in reading more on these and related riddles you can
download a paper by J.C. Bermond and David Peleg, available both in pdf
and ps. See also the references therein.