Engineering university - COMBINATORICS PROOF

[filip_go]

Let's presume that in one group of voters for the election of a mayor, a voters intend to vote for candidate A, b voters for candidate B and c voters for candidate C, while 0<a<b<c. During pre-election silent period, gathering of more than two voters who would discuss about the candidates is not allowed. Every time that a meeting occurs between any two voters of different groups, after the discussion both of them change their attitude and would vote for the third candidate. (For example, if two voters meet and each of them would have voted for candidates A and B respectively, after the long discussion they both decide to vote for candidate C. If afterwards any of them meets another voter who would have voted for candidate A, for example, both of them would vote for candidate B after the conversation.)
The question is if it can really happen all voters a+b+c to be convinced to vote for the same candidate for mayor?

[Guest]

All voters can be convinced to vote for the same candidate if and only if one of the three quantities
[tex]a-b[/tex], [tex]a-c[/tex], [tex]b-c[/tex] is congruent to [tex]0 \bmod 3[/tex].

It is easy to check that the three quantities are invariant mod 3, for example if a voter of A meets a voter of B, [tex]a,b,c[/tex] becomes [tex]a-1,b-1,c+2[/tex] which makes the three quantities we are interested in become [tex](a-1)-(b-1) = a-b[/tex], [tex](a-1)-(c+2) = a-c-3\equiv a-c \bmod 3[/tex], [tex](b-1)-(c+2) = b-c-3\equiv b-c\bmod 3[/tex].

So if it is possible that all candidates vote the same way then eventually two values of [tex]a,b,c[/tex] must become 0 which implies at least one of [tex]a-b[/tex], [tex]a-c[/tex], [tex]b-c[/tex] must be [tex]0 \bmod 3[/tex].

Now we will prove the converse, that (without loss of generality) if [tex]a-b \equiv 0 \bmod 3[/tex] we can make all the voters vote the same way. To start with keep making a voter of A meet a voter of B until either [tex]a[/tex] becomes 0 or [tex]b[/tex] becomes 0. Without loss of generality let us assume [tex]b[/tex] becomes 0. So now [tex]a,b,c[/tex] has become [tex]x,0,z[/tex] we know [tex]x[/tex] must be a multiple of 3 because [tex]a-b \equiv 0 \bmod 3[/tex] remains invariant. If either [tex]x[/tex] or [tex]z[/tex] is 0 we are done, otherwise [tex]x\geq 3[/tex] and [tex]z\geq 1[/tex] in which case we can do the following:
Voter A meets voter C, so [tex]x,0,z[/tex] becomes [tex]x-1,2,z-1[/tex]
Voter A meets voter B, so [tex]x-1,2,z-1[/tex] becomes [tex]x-2,1,z+1[/tex]
Voter A meets voter B, so [tex]x-2,1,z+1[/tex] becomes [tex]x-3,0,z+3[/tex]
Keep repeating this process until [tex]x[/tex] becomes 0 and all voters vote for C.

Hope this helped,

R. Baber.