Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let's assume that there are three candidates running in an election. Right before the elections (when there is no more propaganda), it is forbidden to gather in groups of more than two people to discuss the candidates regarding the election.

There are basically three groups of people: group a which would vote for candidate A, group b which would vote for candidate B, and group c which would vote for candidate C, in such a way that the following is true: 0 < |a| < |b| < |c| (If we assume that the groups are sets). Each time two people from different groups meet, they change their opinions and vote for the third candidate. (So if a person which would vote for A meets a person which would vote for B, then after their conversation, they both would vote for C).

The question is: can all of the voters (the union of groups a, b, c) be persuaded to vote for the same candidate?

share|improve this question
2  
I'm pretty sure this problem is treated in Terence Tao's book Solving Mathematical Problems: A Personal Perspective, in the guise of a problem about colored chips, where you can remove two different-colored chips and replace them with two chips of the third color. I don't have my copy handy but perhaps that will help you or someone else. –  MJD Mar 31 '13 at 18:42
7  
This math.SE question phrases it in terms of a riddle about chameleons who change color. –  Zev Chonoles Mar 31 '13 at 19:30
    
In case anyone needs this in the future, it's on page 83 of the Tao book, and an extensive discussion follows. –  MJD Apr 15 '13 at 0:42

6 Answers 6

up vote 6 down vote accepted

Let $s_0 = \newcommand{\tuple}[1]{\left\langle #1 \right\rangle}\tuple{a_0,b_0,c_0}$ be the initial state and $(s_k)_k$ be any sequence of following states. Set $$f(\tuple{a,b,c}) = \tuple{a-b, b-c, c-a} \bmod 3,$$ then $f(s_k) = f(s_0)$ for any $k$.

Proof.

Without loss of generality we can assume that

$$s_k = \tuple{a, b, c} \leadsto \tuple{a-1, b-1, c+2} = s_{k+1}.$$

Then:

\begin{align} (a-1)-(b-1) &= a-b &&= a-b \pmod 3, \\ (b-1)-(c+2) &= b-c-3 &&= b-c \pmod 3, \\ (c+2)-(a-1) &= c-a+3 &&= c-a \pmod 3, \end{align}

hence, $f(s_k) = f(s_{k+1})$.

Concluding, it is possible to get $a = b = 0$ only if $a_0-b_0 = 0 \pmod 3$. Moreover, there is a winning strategy if there are at least two different voters: WLOG we have $a \leq b$ (otherwise switch $a$ and $b$). First we obtain $c \geq b$ (trivial). Next we generate: $\tuple{0, b_0-a_0, c_0+2a_0}$, then $\tuple{2\frac{b_0-a_0}{3},2\frac{b_0-a_0}{3}, c_0+2a_0-1\frac{b_0-a_0}{3}}$, and finally $\tuple{0, 0, a_0+b_0+c_0}$.

I hope this helps ;-)

share|improve this answer
    
Crap, I've just went to make tea, and when I'm back there are 3 more posted answers similar to mine :-( –  dtldarek Mar 31 '13 at 19:55

No. Let group a have 1 person, group b have 2, and group c have 3. It's not difficult to go through the different possible meetings of people from the groups to see that (1,2,3) (0,2,4) and (0,1,5) are the only possible distributions of votes (up to permutations of the groups.)

share|improve this answer
1  
I tried that, and I got a similar result. So, if the question was "is the persuasion possible in all the cases", your answer is full-n-final. But, that question omits the word "always", so I think we must provide in what cases it is possible, and in what cases it isn't. Even if the question was just asking about the always-possibility, still, it'd be interesting to find out where such a persuasion is possible or not! –  Parth Thakkar Mar 31 '13 at 19:07
    
I thought the word 'always' was implied. However, I can see how understanding the different cases would be more interesting. –  Josh B. Mar 31 '13 at 19:14
    
No, 'always' is not implied. The question is about whether even one possibility exists. Feel free to edit it if you feel appropriate. –  Alex Mar 31 '13 at 19:16

If $2*$|a|+ |b| = |c| - |a|, then there is a solution by having everyone in a meet someone from c in an initial round and then pair up b and c in the second round so that then everyone is for a as there isn't anything mentioned for how many conversations could happen.

If one needs an example for the above, consider if $a=1, b=2, c=5$. Then after a and c meet, the values are $a=0,b=4,c=4$ and then each of b and c meet to produce the result of $a=8,b=0,c=0$.

The key is to get 2 of the 3 sets to have the same cardinality as then it is easy to move each of those people into the third set.

share|improve this answer

It can be done whenever b-a is a multiple of 3,when c-a is a multiple of 3 and a+b is greater than or equal to c, and when c-b is a multiple of 3 and a+b is greater than or equal to c. (3,6,7),(5,5,6),...(0,0,16). (5,6,9),(4,8,8),...(20,0,0) are examples.

share|improve this answer

It may also worth noting that for there to be an initial configuration $(a,b,c)$ where no two of $a$, $b$, $c$ are congruent mod $3$ (and therefore, as others have shown, it is impossible to reach unanimity), it is necessary and sufficient that $a+b+c$ be divisible by $3$.

share|improve this answer

Edit: my answer below is incorrect, because I am assuming that the total number of voters is a multiple of 3.


Yes, if and only if the sizes of all of the groups are congruent modulo $3$.

Say that condition $P$ holds if and only if the sizes of all of the groups are congruent modulo $3$. Whenever two people from different groups meet, the truth value of condition $P$ is preserved. When everyone is voting for candidate $C$, condition $P$ holds. Therefore, if condition $P$ does not hold, then it is impossible to make everyone vote for candidate $C$.

Suppose that condition $P$ does hold. Assume, without loss of generality, that $|a| \le |b| \le |c|$. We can make everyone vote for $C$ using the following algorithm:

  • First, people who are voting for $A$ meet with people who are voting for $B$, until there are no longer any more people voting for $A$. After this, $|a| = 0$ and $|b| \le |c|$.
  • Notice that since $|a| = 0$ and condition $P$ holds, $|b|$ and $|c|$ must both be congruent to $|a| = 0$ modulo $3$. In particular, there exists some number $n$ such that $|b| = 3n$.
  • Do the following $n$ times:
    • Have one person who is voting for $B$ meet with one person who is voting for $C$, thereby increasing $|a|$ by $2$ and decreasing $|b|$ by $1$.
    • Have two people who are voting for $A$ meet with two people who are voting for $B$, thereby decreasing both $|a|$ and $|b|$ by $2$.
  • Now $|a|$ is still $0$, but $|b|$ has been decreased by $3n$, and so $|b|$ is now $0$ as well. Since $|a|$ and $|b|$ are both $0$, everyone is now voting for $C$.
share|improve this answer
    
um, but I got a solution for (1,2,4). The group sizes aren't congruent modulo 3. (solution is given in [a bad, very bad format] the answer by Josh B.) –  Parth Thakkar Mar 31 '13 at 19:29
1  
What about the case (0,4,6) -> (2,3,5) -> (4,2,4) -> (3,4,3) -> (2,6,2) -> (1,8,1) -> (0,10,0) –  Josh B. Mar 31 '13 at 19:31
    
@Tanner Swett, probably you should remove the phrase 'if and only if' and replace it by vanilla 'if' –  Parth Thakkar Mar 31 '13 at 19:32
    
This solution assumes $P$ is true iff all voters can be moved to $C$. However, as @JoshB. has illustrated, it is possible to move all the voters to another group. –  George V. Williams Mar 31 '13 at 19:33
1  
Here's the solution for (1,2,4): (1,2,4) -> (0,4,3) -> (2,3,2) -> (1,3,1) -> (0,4,0) –  Parth Thakkar Mar 31 '13 at 19:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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