2
$\begingroup$

I'm reading Jim Hefferon's free ebook about linear algebra. I tried to solve the problem 1.37 about the Wohascum County Board and have a question about it. In short: 20 members of a board can vote for three candidates A, B, C. They have to list them in order of preference (e.g. C,A,B), no abstentions possible. These information is given about the results of the voting:

  • 11 members preferred A over B
  • 12 members preferred C over A
  • 14 members preferred B over C
  • every possible order of A, B, C occurred at least once

The question is now, how many voted for B at the first position?

There is even a solution given in a second ebook but at one point I don't understand it. It is clear that one can define a frequency for each permutation of A, B, C resulting in 6 variables and translate the first three statements into three equations involving these variables. One additional information is that there are 20 votes so that the variables have to sum up to 20, alternatively one can define three more complementary equations but this does not help, because there are only four different / independent statements and the system is under-determined in both cases.

In the solution in the second ebook an author (not Hefferon) gives the right numbers directly but I don't see how to get there without making a case-by-case analysis of the under-determined system using the fact that all variables have to be natural numbers. One will try to be as clever as possible and keep the cases at a low number, but is it really necessary to do a case-by-case analysis or am I missing something ?

2 Answers 2

2

You were on the right track; you just need to make judicious use of the equations. These are, with $x_1$ through $x_6$ denoting the number of votes for ABC, ACB, BAC, BCA, CAB, CBA, respectively:

$ x_1+x_2+x_5=11\;, \\ x_4+x_5+x_6=12\;, \\ x_1+x_3+x_4=14\;, \\ x_1+x_2+x_3+x_4+x_5+x_6=20\;. $

Subtracting the sum of the first three from twice the last yields

$x_2+x_3+x_6=3\;.$

Since each order occurred at least once, that implies $x_2=x_3=x_6=1$. That leaves us with

$ x_1+x_5=10\;, \\ x_4+x_5=11\;, \\ x_1+x_4=13\;, $

and that system is readily solved to yield $x_1=6,x_4=7,x_5=4$. Thus $x_3+x_4=1+7=8$ members put B first.

2

In fact, $11+12+14=37$ counts every vote two times except $ACB$,$BAC$ and $CBA$, so $ACB+BAC+CBA=2\cdot 20-37=3$,and every of them equals $1$, then other variables can be determined easily.