34
$\begingroup$

In the far-off country of Politica, there are three main parties: the Left, the Right, and the Centre. In the last election, there were 19 million Left voters, 21 million Right voters, and 23 million Centre voters.

Every time two people who support different parties get into a debate, they each end up convincing the other that their party is terrible and not worth supporting, and both decide to switch their vote to the third party. For instance, a debate between a Left voter and a Right voter will turn both of them into Centre voters. This is the only way anyone's chosen party can change: if more than two people get into a debate, they'll just end up fighting instead.

Is it possible that by the next election, everyone will be agreed on the same party?

For the sake of simplicity, assume a fixed population: the set of voters is exactly the same in the next election as the last one.

This problem is inspired by one in the 1984 Tournament of Towns.

$\endgroup$
48
$\begingroup$

I am assuming that

these numbers are all exact. It will quickly become apparent why I need this.

So, consider

the difference between the number of Left and Right voters. When two L,R voters argue this doesn't change. When an L and a C argue, we turn +1 into -2. When an R and a C argue, we turn -1 into +2. In any case, the total mod 3 remains fixed.

Now,

this difference starts out at 4 million. Since the total number of voters is a multiple of 3, we want it to end at zero. But 4 million is not a multiple of 3. Therefore: no, it is not possible.

$\endgroup$
  • 16
    $\begingroup$ I went out of my way to minimize the mathematical formalism in this answer, and what do I get for it? Not one, not two, but three other later answers essentially equivalent to it and no shorter but with more mathematical formalism :-). $\endgroup$ – Gareth McCaughan Jan 17 '17 at 10:27
  • 4
    $\begingroup$ What, exactly, are you moaning about?  You know that questions like this typically accrue duplicate answers, some of which may have been developed independently of yours.  The question didn’t call for minimal formalism, so, even if the other answerers were aware of your answer, they probably righteously believed that their proofs were better.  Relax; you’re winning by votes, and @randal'thor will probably award you the crown within six to eight weeks.     :-)    ⁠ $\endgroup$ – Peregrine Rook Jan 17 '17 at 19:04
  • $\begingroup$ It wasn't a very serious complaint :-). (And +37 seems frankly excessive, though I'm not going to complain about it.) $\endgroup$ – Gareth McCaughan Jan 18 '17 at 2:17
  • $\begingroup$ i like its simplicity. +1! $\endgroup$ – Omega Krypton May 8 at 13:25
7
$\begingroup$

Let the $V_n$ be the set $\{L,C,R\}$ where $L$, $C$ and $R$ are the number of voters for Left, Centre and Right respectively, after the $n^\text{th}$ argument.

Initially $V_0=\{19000000,21000000,23000000\}\equiv\{0,1,2\} \pmod 3$ because sets are unordered. We wish to prove $V_n\equiv\{0,1,2\} \forall n \pmod 3$.

Then if $V_i\equiv\{0,1,2\}$, $V_{i+1}\equiv\{0,1,2\}$ because having a conversation maps $L$, $C$ and $R$ to $L-1$, $C-1$ and $R-1 \pmod 3$, since $X+2\equiv X-1 \pmod 3$.

So $V_{i+1}\equiv\{0-1,1-1,2-1\}\equiv\{-1,0,1\}\equiv\{0,1,2\} \pmod 3$, completing the induction.

For one party to have unanimous favour after $j$ conversations, the other two parties must not have any voters, so $V_j\equiv\{0,0,k\}\pmod 3$, however $\{0,0,k\}\not\equiv\{0,1,2\}\forall k$, a contradiction.

Therefore there will never be an unanimous vote.

$\endgroup$
  • $\begingroup$ This should be the accepted answer, IMHO. $\endgroup$ – SQB Jan 17 '17 at 7:29
  • 1
    $\begingroup$ I hope you don't mind my edit. $\endgroup$ – SQB Jan 17 '17 at 8:20
5
$\begingroup$

Any argument between two voters results in a change of votes of $(-1, -1, 2)$; in other words, both parties the voters belonged to lose $1$ vote while the third party gains $2$.

That means that the difference in votes between any two parties modulo $3$ has not changed. If two parties have at $t=0$ a total number of votes $P_0$ and $Q_0$, then $P_0 - Q_0 \equiv P_1 - Q_1 \pmod 3$ regardless of which two parties we choose.

The total number of votes is $63 000 000$. If one party wins unanimously, that party has all those $63 000 000$ votes while both losing parties have $0$ votes. That means that the difference in votes between any two parties in this end state, modulo $3$, will be $0$.
In other words, $(P_n - Q_n) \mod 3 = 0$ regardless of the parties chosen.

This should be congruent with the starting state (again, under modulo $3$), but it isn't. Labelling the number of votes for Left, Right, and Centre in the starting state as $L_0$, $R_0$, and $C_0$, we can see that $(C_0 - R_0) \mod 3 \neq 0$, $(C_0 - L_0) \mod 3 \neq 0$, and $(R_0 - L_0) \mod 3 \neq 0$, which means the end state in unreachable from the starting state.

$\endgroup$
2
$\begingroup$
R - x = C + 2x
Where R is the number of Right, and C is the number of centre.
Where x is the number of people changing parties.
23-x = 21 + 2x
23 = 21 + 3x
3x = 2
x = 2/3

This is to try to get the number of Centre and Right voters to be equal.

L=19 C=21 R=23

So 2/3 of a million Right and Left voters argue.

L=18 1/3 C=22 2/3 R=22 2/3

Then 22 1/3 million Centre and Right voters argue.

L=63 1/3 C=0 R=0

All voters 63 million voters are Left wing!

$\endgroup$
  • 6
    $\begingroup$ This is morally correct, but I am fairly sure the actual intention of the puzzle is that we should take the numbers of voters to be exact, in which case your prescription requires fractional voters to debate one another. $\endgroup$ – Gareth McCaughan Jan 16 '17 at 19:27
  • 2
    $\begingroup$ @GarethMcCaughan that would be even more painful then just normal debates! $\endgroup$ – Beastly Gerbil Jan 16 '17 at 19:28
  • 2
    $\begingroup$ 2/3 of a person voting? Sounds like Democracy to me in its purest form, from the original Ancient Greek times ;-) $\endgroup$ – Ertai87 Jan 16 '17 at 19:30
  • 2
    $\begingroup$ @Gareth Yes, in actual political situations they're chopping up voters into wriggling one-third-sized chunks all the time :-P $\endgroup$ – Rand al'Thor Jan 16 '17 at 22:27
  • 3
    $\begingroup$ And the reason for that "3/5 of a person" thing, in case anyone didn't know, was the opposite of what many think. The "slave states" wanted slaves to count towards the House of Representatives (even though they couldn't vote), because that way they would have more power. The "free states" wanted slaves to count as 0 people for the purpose of House representation, because then the slave states would have less power. (And the 3/5 thing was a compromise). People often think it was the slave states who wanted slaves to not count, but in fact it was the opposite. Off-topic, but interesting. :-) $\endgroup$ – rmunn Jan 17 '17 at 5:40
1
$\begingroup$

19 million Lefties argue with 19 million Righties, result 0 L, 2M R, 61M C. (Previous argument, but 1+1=1 in it: So 1M C argue with 1M R, result 2M L, 1M R, 60M C, and L and R argue again.). Alternative argument - need L=R, so 2M-x=2x, or 2M=3x, which is not possible if x is an integer.

$\endgroup$
  • $\begingroup$ The number of centrists after your first step is wrong: you have 42M but it should be 38M+23M=61M. [EDITED to note that after I wrote this JMP fixed the first step ... but now the second step is wrong.] $\endgroup$ – Gareth McCaughan Jan 16 '17 at 19:27
  • 1
    $\begingroup$ Your maths is wrong. 1M C arguing with 1M R would give 2M L not 1M L $\endgroup$ – Beastly Gerbil Jan 16 '17 at 19:27
  • $\begingroup$ Also the number of people who convert to L from C and R in your second step is wrong. If 1M R and 1M C argue, then they become 2M L. $\endgroup$ – Ertai87 Jan 16 '17 at 19:27
1
$\begingroup$

The answer is...

Nope.

Because...

After every debate between Party A and Party B, there are one less Party A and Party B supporters each, and 2 more Party C supporters. That means the difference between the numbers of Party C and Party A/B supporters increases by 3, but it stays the same between Party A and B supporters, so the difference between the number of any two parties' supporters either stays the same or changes by 3. Therefore, for one party to completely take over, ending up being supported by 63M people and leave zero people supporting any of the others, the difference between any two parties must start out as a multiple of 3 (including 0). Since the latter isn't the case, that will never happen.

$\endgroup$
  • 1
    $\begingroup$ I think this is *identical* to SQB's answer... $\endgroup$ – boboquack Jan 17 '17 at 7:03
  • 1
    $\begingroup$ ... which is pretty much identical to Gareth McCaughan's. $\endgroup$ – Nautilus Jan 17 '17 at 9:34
1
$\begingroup$

6,666,666 Rights argue with the same number Centres, converting to Left. Then there are: 20,333,332 Lefts, 20,333,334 Right, and 22,333,334 Centres. All the Lefts argue with the Rights so that there are only 2 Rights left.

But the following happens...

One Centre gets into an argument with a Right, but then bumps his head, gets amnesia, and forgets back to Centre. (1L, 1R, 62,999,998C) Then the remaining Right gets into and argument with the newly convinced Left and they both decide everyone else must be right and go to the Centre.


Alternatively the first Center casts his vote before arguing with the first Right.

$\endgroup$
  • 1
    $\begingroup$ I fixed your formatting for you :) Welcome to puzzling $\endgroup$ – Beastly Gerbil Jan 17 '17 at 20:29
  • 1
    $\begingroup$ There's a bit too much lateral thinking in your second spoilerblock. The question includes an assumption about the only way people's chosen party can change. $\endgroup$ – Rand al'Thor Jan 17 '17 at 20:36
1
$\begingroup$

I am making the following assumptions:

  • Party supporters will engage in numerous debates between elections, and the outcome of each debate is dictated by the rules stated in the initial question.
  • Party supporters can flow between all parties over time (for example, can change from Party A to Party B, and then change back to Party A following a subsequent debate with someone from Party C).
  • Party supporters may debate with party supporters from the same party, with both affirming the other's views, in which case their support remains constant.
  • Party supporters will debate randomly with other supporters randomly, with the same probability as the proportion of party support within the community (they neither avoid, nor seek out supporters of other parties).

The number of supporters of Party A is given as A, Party B as B, Party C as C, and the total population is T=(A+B+C).

A supporter of Party A will debate a supporter of Party B with probability B/T. As there are A supporters of Party A, the number of debates between party supporters of A and B = AB/T. From each debate, two new Party C supporters will emerge. This means that Party C has inflows in each iteration of 2AB/T. Likewise, Party B has inflows of 2AC/T, and Party A has inflows of 2BC/T.

Similarly, Party A will have outflows based on the number of debates its supporters have between Party B supporters and Party C supporters. There will be AB/T debates between supporters of Party A and Party B, and AC/T debates between supporters of Party A and Party C. Hence, Party A will have outflows of (AB/T) + (AC/T). Outflows for the other parties can be likewise determined.

Inflows and Outflows in each iteration, the change in party support for each of the parties is as follows:

  • Change in A = 2BC/T - ((AB/T)+(AC/T))
  • Change in B = 2AC/T - ((AB/T)+(BC/T))
  • Change in C = 2AB/T - ((AC/T)+(BC/T))

Running these equations through numerous iterations, with the initial values for each party shows that all parties tend towards an equilibrium level where all parties have equal support. This is the case even with greater differences in party support, however it takes more iterations to reach the equilibrium.

$\endgroup$
-3
$\begingroup$

Since all answers basically argue that the figures dont match up exactly to have literally zero voters for two parties and literally everyone voting for the exact same party, I would like to add a different view on the question.

Lets assume first that either it is OK to change the numbers a little bit like this:

there were 20 million Left voters, 20 million Right voters, and 23 million Centre voters.

(changed numbers bold)

If now everyone in the Centre party is convinced that having a debate with less than two other people is worthless and since to be avoided, only Left and Right voters are going to have

a debate [of two people.] [Thus] they each end up convincing the other that their party is terrible and not worth supporting, and both decide to switch their vote to the [Centre] party

In the end, there are zero voters for Left and Right, and 63 million Centre voters. I think the point I am trying to make here is that OP didn't specify the mechanism of two people getting into a debate, neither the rate at which this happens. I think, everyone just assumed a stochastic pairing of two people at a time and then came to the conclusion that in a most extreme scenario where one party has zero voters, the second party is going to have at least 1 or 2 voters. But from my perception this isn't what OP wanted to see discussed. He could rephrase his question from "everyone" to "everyone except for one or two voters", which would render every answer in this line of thought incorrect.

EDIT and rather substantial extension

Introduction

EDIT: After criticism of my post as changing the rules of the OP unilaterally and biased, I would like to try to illustrate what else might be a "solution" to the OP.

The mechanism described in the OP can be expressed as three interdependent reaction equations:

$$ B + C \xrightarrow{k_1} 2A\\ A + C \xrightarrow{k_2} 2B\\ A + B \xrightarrow{k_3} 2C $$

Here, $A, B$, and $C$ denote anonymous voters for one of the three parties each. The rates at which they talk to each other are called $k_i$. In all answers so far, those rate constants have been assumed to be irrelevant. After this assumption, they approach the question in the OP whether it is possible that by the next election (and one can discuss this for any random point in time) the populations of two of the parties are zero in an algebraic and exact manner. In terms of the notation of this post, we are going to call the populations $N_i$. Thus, one possibility to look for is $N_1 = N_2 = 0$ and $N_3 = N_{\mathrm{sum}} = 6.3 \cdot 10^7$ as well as the other two permutations of this. They come to the conclusion that this situation is impossible to achieve under the following two assumptions:

  1. Assuming 5 significant digits not specified in the OP, i.e. 19 million exactly means 19000000 and not anything between 18500000 and 19499999.
  2. Absolute zero for two of the $N_i$ and not relative zero (e.g. ${N_1 \over N_{\mathrm{sum}}} = 0$) to some extent of accuracy or amount of significant digits.

The point I tried to make before this edit was that beyond the lack of a definition of the precision of the measurement values given in the OP there are at least two interesting things to discuss here.

1. Probability

First off, we try to enhance on whether it is possible to have all voters agree on one of the three parties in terms of probability: How probable is it that they are going to agree? For this purpose, we have to get rid of one of the two assumptions made above. It actually doesn't matter too much which one to choose, for the sake of simplicity we choose to let go of assumption #2. Then, the most extreme case to have the most voters to agree on one party is, e.g., $N_1 = 0$, $N_2 = 1$, $N_3=62999999$ and the other five permutations of that.

This makes a maximum number of possible arrangements of individual voters (in other words: microstates) of $p_{\mathrm{min}} = 6 \cdot 62999999 = 3.8 \cdot 10^8$ (everyone of the voters subsumed in $N_3$ could exchange with the single voter in $N_2$. and the other five permutations of that. rounded to number of significant digits given in OP.).

The other extreme case is complete randomness, that is all possibilities of putting all voters into the three parties, also called "n labelled balls into k labelled boxes". This yields a number of microstates of

$$ p_{\mathrm{max}} = 3^{63000000} - 3.8\cdot 10^{8} = 1.1 \cdot 10^{30058639} $$

Thus, the probability of the most extreme case (as many voters for one party as possible) equals to $\frac{p_{\mathrm{min}}}{p_{\mathrm{max}}} = 10^{-10^{7.5}}$. Which is, basically, zero. Consequently, even if we changed the numbers in the OP slightly to make it possible that literally everyone agrees to vote for one party, it will almost never happen.

2. Kinetics

Another approach to circumvent the extreme improbability of almost everyone agreeing to vote on one party as shown in the preceding subsection is to look at the rate constants mentioned above, $k_i$.

First off, lets consider the most basic case. The $k_i$ are all the same, i.e. $k_1 = k_2 = k_3 = k$. In this case, the first measurement of populations $N_i$ (called "last election" in OP) does not represent a state of equilibrium. Rather, after some time, the three populations will equilibriate and become $N_1 = N_2 = N_3 = \frac{N_{\mathrm{sum}}}{3}$ in a second measurement (called "next election" in OP).

Another possibility is that the first measurement actually already represents the equilibrium. Now we can say something about the rates at which the voters get into debates. This will finally lead to some insight into which rates are necessary to get almost everyone to vote for one party. The coupled reaction equations shown above yield the following rate equations

$$ \dot N_1 = 2k_1 N_2 N_3 - k_2 N_1 N_3 - k_3 N_1 N_2\\ \dot N_2 = 2k_2 N_1 N_3 - k_1 N_2 N_3 - k_3 N_1 N_2\\ \dot N_3 = 2k_3 N_1 N_2 - k_1 N_2 N_3 - k_2 N_1 N_3 $$

In equilibrium, the populations do not change (in their sum, they might change in composition since our reaction equations are anonymous, but voters are individuals), i.e. $\dot N_i = 0$. Furthermore, the $N_i$ in equilibrium are given by the first measurement in this case. This way, we can calculate the rate constants $k_i$ by solving the equation system

$$ 0 = 2\cdot21\cdot23\cdot k_1 - 19\cdot23\cdot k_2 - 19\cdot21\cdot k_3\\ 0 = 2\cdot19\cdot23\cdot k_2 - 21\cdot23\cdot k_1 - 19\cdot21\cdot k_3\\ 0 = 2\cdot19\cdot21\cdot k_3 - 21\cdot23\cdot k_1 - 19\cdot23\cdot k_2 $$

By arbitrarily defining $k_1 = 1$ (without a specified time axis we can't define a unit anyway), we obtain $k_2 = 1.5$ and $k_3 = 1.6$. Now that's interesting. This tells us to which extent the voters for a respective party engage debates.

And, finally, a very easy conclusion: If one of the $k_i$ is very big (lets say $\infty$) and the other two are very small (or, easier, zero), then party $i$ will obtain the highest amount of votes possible with the mechanism described in the OP. What does this mean in numbers? Putting "everyone" into perspective by $\frac{1}{62999999} = 1.6 \cdot 10^{-8} = 0.0 = 0.0 \%$ to the degree of accuracy possible given the figures in the OP (two significant digits).

$\endgroup$
  • 3
    $\begingroup$ Since you've changed the numbers, this isn't a valid answer to the original question. $\endgroup$ – Rand al'Thor Jan 17 '17 at 14:01
  • 1
    $\begingroup$ So your original question really is just about simple subtraction? If so I agree, I did not post a valid answer to the original question. Still, I am somewhat puzzled about everyone agreeing upon a stochastic mechanism of two people at a time getting into a debate, since this isn't specified in the original question. I had the impression that the question was more than mere numbers. Sorry. $\endgroup$ – hintze Jan 17 '17 at 14:07
  • 2
    $\begingroup$ I'm not sure what you mean by "simple subtraction". There's a single fairly simple type of operation which is the only way to change people's votes, yes. I did say in the OP that we only care about two people at a time getting into a debate: "if more than two people get into a debate, they'll just end up fighting instead." $\endgroup$ – Rand al'Thor Jan 17 '17 at 15:42
  • 2
    $\begingroup$ What philosophy are you expressing here? If you get stuck solving a Rubik’s cube, do you think it’s OK to paint the sides so they are all monochrome? or to declare the cube to be “solved” if only one or two tiles on each side are the wrong color? $\endgroup$ – Peregrine Rook Jan 17 '17 at 18:43
  • 1
    $\begingroup$ Hi, welcome to Puzzling :) Hope that you will learn from this answer that you should take into consideration all the rules, even when they're implicit, into the account before answering a question. have a good time here... $\endgroup$ – ABcDexter Jan 19 '17 at 7: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.