5
$\begingroup$

The new board of the Fun-and-Nonsense-Club is to be elected. The voting procedure itself is fairly simple: The club has 24 members, and every pair of (distinct) members announces to the public whether they are close friends or not. Then every member receives one vote for every close friend, and the composition of the board depends on these numbers of votes in a horribly complicated fashion; in our puzzle this luckily is of no concern to us.

In the week before the election, the club hired Professor Halfbrain to carry out an opinion poll. Halfbrain briefly spoke to every pair of club members and asked them whether they are close friends or not. Then he summarized his data and announced his prediction on the number of votes that each club member is going to receive.

Scenario 1: During the poll, all club members answered truthfully to the professor's questions. But once they hear Halfbrain's prediction, they change their mind and decide to have their fun with the professor. They plot up and at the actual election not a single one of Professor Halfbrain's 24 predicted numbers turns out to be correct.

Question 1: Was it just a lucky coincidence that the original (truthful) data allowed the club members to shatter Halfbrain's predictions? Or is there always a way of doing this?

Scenario 2: At the end of his interviewing work with the club members, Professor Halfbrain realized that he had accidentally erased all the collected data. As he could not remember a single number and as he was unwilling to admit his mistake, he decided to simply use 24 random numbers (from the range $0,1,\ldots,23$) in his prediction. Once the club members hear Halfbrain's prediction, they decide to have their fun with the professor. They plot up and at the actual election not a single one of Professor Halfbrain's 24 predicted numbers turns out to be correct.

Question 2: Was it just a lucky coincidence that the club members were able to shatter Halfbrain's random predictions? Or is there always a way of doing this?

$\endgroup$
7
$\begingroup$

Question 1:

Because there are 24 members, that means each member belongs to exactly 23 pairs (1:24, 2:24 ... 23:24). Because the number of pairs is odd, each member must have a different number of close friends versus non-friends. For example, if a member has 12 close friends, he must then have 11 non-friends. If at the time of the vote every member reversed their opinions of each other, then every member will have a different number of close friends than what they originally stated in the poll. Therefore, they will all have a different number of votes than the professor will have predicted.

Question 2:

If the professor chooses all random numbers for his prediction (from the range 0-23), then chances are good that he is wrong about all the numbers anyway.

In the event [A] that he guesses two members' vote counts correctly, those members can change each others' vote counts at the same time as a pair. By extension, this works for all possibilities where the professor guessed an even number of members' votes correctly.

In the event [B] that the professor guesses only one person's, or an odd number of members', votes correctly, then there's the potential that reversing the opinion in one of his pairs will correct the other person's vote count by mistake. In such a case where this is unavoidable, the already-correct member reverses two pairs in the same direction (adding two close friends or subtracting two). This guarantees that the two people he swapped with are now correct with the professor's prediction, and therefore sets up event [A] above.

For example, pretend that the entire board had no close friends at all, the simplest scenario, where all members are tied with 0 votes. Let's say the professor's random number generator gets all 1's and only a single 0. By reversing member A, whose vote count was guessed correctly, with member B (B had 0 close friends; now he has 1), then member B's vote count has now been correctly predicted by mistake. If after that member A reverses with someone else, member C, then now C has 1 close friend and has a correctly predicted vote count as well. Now, simply reverse B and C together as a pair, making them close friends with each other, and they will all three have two votes apiece, being close friends with each other. The professor's zero-guess has been nullified. Note: if one of the guesses were two votes off, then this whole situation would have been avoided in the first place.

$\endgroup$
  • $\begingroup$ For question 2, what happens if the professor guesses 2 or more members' vote counts correctly, and these correct guesses are all the same number? $\endgroup$ – Lopsy Feb 13 '15 at 17:42
  • $\begingroup$ Doesn't matter. The above states fix that, too. In the above example, if the professor guessed all 1's except for two 0's, then those two he guessed correctly reverse their opinion of each other as a pair. That immediately changes both of their votes without affecting anyone else's. $\endgroup$ – Bulldogg6404 Feb 13 '15 at 20:04
  • $\begingroup$ Oh, I see. I had misread your solution. +1 $\endgroup$ – Lopsy Feb 13 '15 at 22:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.