The riddle:
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?
2nd variant:
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?
3rd variant:
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?
No comments:
Post a Comment