HMMT 二月 2011 · ALGCOMB 赛 · 第 18 题
HMMT February 2011 — ALGCOMB Round — Problem 18
题目详情
- Let n be an odd positive integer, and suppose that n people sit on a committee that is in the process of electing a president. The members sit in a circle, and every member votes for the person either to his/her immediate left, or to his/her immediate right. If one member wins more votes than all the other members do, he/she will be declared to be the president; otherwise, one of the the members who won at least as many votes as all the other members did will be randomly selected to be the president. If Hermia and Lysander are two members of the committee, with Hermia sitting to Lysander’s left and Lysander planning to vote for Hermia, determine the probability that Hermia is elected president, assuming that the other n − 1 members vote randomly. √ 2 2
解析
- Let n be an odd positive integer, and suppose that n people sit on a committee that is in the process of electing a president. The members sit in a circle, and every member votes for the person either to his/her immediate left, or to his/her immediate right. If one member wins more votes than all the other members do, he/she will be declared to be the president; otherwise, one of the the members who won at least as many votes as all the other members did will be randomly selected to be the president. If Hermia and Lysander are two members of the committee, with Hermia sitting to Lysander’s left and Lysander planning to vote for Hermia, determine the probability that Hermia is elected president, assuming that the other n − 1 members vote randomly. n 2 − 1 Answer: Let x be the probability Hermia is elected if Lysander votes for her, and let y be the n − 1 n 2 probability that she wins if Lysander does not vote for her. We are trying to find x , and do so by first 1 finding y . If Lysander votes for Hermia with probability then the probability that Hermia is elected 2 y x 1 chairman is + , but it is also by symmetry. If Lysander does not vote for Hermia, Hermia can 2 2 n get at most 1 vote, and then can only be elected if everyone gets one vote and she wins the tiebreaker. 1 The probability she wins the tiebreaker is , and chasing around the circle, the probability that every n 1 person gets 1 vote is . (Everyone votes for the person to the left, or everyone votes for the person n − 1 2 to the right.) Hence 1 y = . n − 1 n 2 x 1 1 Then + = , so solving for x gives n 2 n 2 n n 2 − 1 x = . n − 1 n 2 √ 2 2