10
$\begingroup$

There are $n$ MPs seated around a circular table, prepared to cast their votes on a single yes-or-no question.

The voting goes by rounds. Each voter raises his hand for 'yes' and keeps it down for 'no'. If a voter's neighbors both vote the same way in one round, he will vote that way in the next round; but if one of his neighbors votes 'no' and the other one votes 'yes', he keeps his current choice for the next round.

The voting ends when all $n$ voters keep their votes no matter how many further rounds take place.

enter image description here

Question:

  • what values of $n$ ensure a definite end?
  • if the voting is endless, how were votes cast in the initial round?
Improve this question
$\endgroup$

2 Answers 2

Reset to default
13
$\begingroup$

The following fact is the key to answering this question:

$(*)$ if any two adjacent MPs vote in the same way, then all votes will eventually be locked in indefinitely.

Proof

An MP will only change his vote if both his neighbours vote differently from him. So if two adjacent MPs ($M_1$ and $M_2$) vote in the same way, then clearly their votes are both locked in indefinitely. WLOG, let's say they both vote 'yes'.

Now consider the MP adjacent to them, $M_3$. If he ever votes 'yes', then that vote too will be locked in indefinitely, by the same reasoning. Otherwise, he never votes 'yes', i.e. his vote is locked in as 'no' indefinitely.

Let $k$ be minimal such that the $k$th MP $M_k$ never votes 'yes'. We know $M_1$ and $M_2$'s votes get locked in as 'yes'; if $k>3$, then $M_3$'s vote also gets locked in as 'yes'; ; if $k>4$, then $M_4$'s vote also gets locked in as 'yes'; and so on by induction. The votes of $M_1,\dots,M_{k-1}$ all get locked in at 'yes' while $M_k$'s vote is always 'no'. (If there is no such $k$, then the same argument shows they all get locked in at 'yes' and we're done.)

Now $M_{k+1}$ can't ever vote 'yes' after $M_{k-1}$'s vote is locked in, since that would mean $M_k$'s vote would change to 'yes'. So $M_{k+1}$'s vote is eventually locked in at 'no'.

At this stage, the pattern repeats. Argue exactly as above with the adjacent 'yes'-voters $M_1,M_2$ replaced by the adjacent 'no'-voters $M_k,M_{k+1}$. This argument can carry on indefinitely, and since $n$ is finite, we eventually come to an end. So all votes end up being locked in.

The converse is also clear: if the MPs' votes alternate so that every adjacent pair of MPs vote differently from each other, then every yes-man is in between two no-men and vice versa, so in each round all votes are toggled, and no votes end up being locked in.

So voting continues forever iff the MPs' votes alternate all the way round the table, which can only happen if $n$ is even.

So the answers to the OP's two questions are:

what values of $n$ ensure a definite end?

Odd $n$.

if the voting is endless, how were votes cast in the initial round?

Alternating all the way round the table.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Good observation at the beginning. $\endgroup$
    – Lawrence
    Commented Mar 26, 2015 at 9:02
  • $\begingroup$ i liked this answer because it s well explained , and the time spent writing this is caused the post to be proportionally a bit lagged . $\endgroup$
    – Abr001am
    Commented Mar 26, 2015 at 10:00
4
$\begingroup$

The voting is endless when

$n$ is even and votes alternate around the table

The voting has a definite end in all other cases.

Improve this answer
$\endgroup$
3
  • $\begingroup$ You posted this while I was in the middle of writing a proof! ;-) $\endgroup$
    – Rand al'Thor
    Commented Mar 26, 2015 at 0:32
  • 5
    $\begingroup$ Proof shmoof! Intuition! ;) $\endgroup$
    – Ian MacDonald
    Commented Mar 26, 2015 at 1:17
  • 2
    $\begingroup$ This needs an explanation. $\endgroup$
    – Esoteric Screen Name
    Commented Mar 26, 2015 at 6:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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