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 say I have a results of a small vote - but only in percentage form and want actual vote counts (as well as total vote).

For example:

  • $A: 47.4$%
  • $B: 26.3$%
  • $C: 26.3$%

In this case, I constructed a spreadsheet of votes vs total votes, and looked down until all the numbers were close to whole numbers (which occurs at total votes $= 19$, with $9$, $5$, $5$ respectively).

  • Is there a mathematical way I can take these numbers and estimate the vote quantities - assuming those percentages are rounded?

I am willing to make the assumption it is the lowest time where values are close to whole numbers (ie at $19$ and not $38$, etc) as well as consider all numbers within $0.05$ of a whole number to be considered valid.


The context is an online game, where different groups often post election results in percentage form. Sometimes it can be strategically advantageous to approximate what percentage of their group voted from these results.

share|improve this question

3 Answers 3

up vote 2 down vote accepted

The continued fraction for $0.474$ is $(0,2,9,8,1,2)$. The approximants for the partial continued fractions are $$ \begin{array}{} &&0&2&9&8&1&2\\ \hline\\ 0&1&0&1&\color{#C00000}{9}&73&82&237\\ 1&0&1&2&\color{#C00000}{19}&154&173&500 \end{array} $$ The approximant $\frac{9}{19}=0.473684210526316$ is close enough to be rounded to $0.474$.

The continued fraction for $0.263$ is $(0,3,1,4,17,3)$. The approximants for the partial continued fractions are $$ \begin{array}{} &&0&3&1&4&17&3\\ \hline\\ 0&1&0&1&1&\color{#C00000}{5}&86&263\\ 1&0&1&3&4&\color{#C00000}{19}&327&1000 \end{array} $$ The approximant $\frac{5}{19}=0.263157894736842$ is close enough to be rounded to $0.263$.

Thus, the smallest number of total votes that gives the correct rounded results is $19$, with the votes being $9$, $5$, and $5$.

share|improve this answer
    
Continued fractions will not always work. Consider a case with $A=47.4\%, B=24.4\%$, where you'd find $\frac01,\frac12,\frac9{19},\frac{73}{154},\ldots$ and $\frac01,\frac14,\frac{10}{41},\frac{61}{250}$ as approximants and would miss $\color{#C00000}{\frac{37}{78},\frac{19}{78}}$ (though admittedly the remaining $28.2\%$ have $\frac{11}{39}=\frac{22}{78}$ as an approximant, but I'm sure a better counterexample can be found - I wanted to explicitly keep the $47.4\%$ of the original question). –  Hagen von Eitzen Feb 2 '13 at 11:13
    
The proper way to do it is to compute the continued fractions for $n-.05$ and $n+.05$; then any truncated continued fraction which is between those two will get rounded to $n$. For instance, if you obtained continued fractions of [0;1,2,2] and [0;1,2,4] then you would also have to consider [0;1,2,3]. –  half-integer fan Feb 2 '13 at 12:45
    
@HagenvonEitzen: Yes, these problems do not always have easy solutions. If the approximants did not work out, we would have to resort to half-integer fan's suggestion, and bracket the possible values between $0.4735$ and $0.4745$. Of course, this becomes as complicated as walking the Stern-Brocot Tree, as you did in your answer. Luckily, the simpler first attempt worked. –  robjohn Feb 2 '13 at 14:09

By rounding rules you know that the first value is somewhere between $u=0.4735$ and $v=0.4745$. Of yourse you can always find a valid fraction in $[u,v)$ if you select a denominator $\ge \frac1{v-u}$. You can use Farey sequence methods to find the fractions of minimal denominator that are within this range as well as all fractions with denominators $<\frac1{v-u}$ in the range:

Start with the (very rough) approximation $\frac 01<u<v\le \frac 11$. Now as long as you have an approximationk $\frac ab<u<v\le \frac cd$ compute the Farey sum $\frac{a+c}{b+d}$; it is the only rational number between $\frac ab$ and $\frac cd$ with a denominaor $\le b+d$. If $\frac{a+c}{ b+d}<u$, replace $\frac ab$ with $\frac{a+c}{b+d}$; if $\frac{a+c}{b+d}\ge v$, replace $\frac cd$ with $\frac{a+c}{b+d}$; otherwise you have the simplest candidate for a rational number corresponding to $47.4\%$. If you check the other percentages, you may either find that the same denominator works for it or not.

You can continue to enumerate all feasible fractions ordered by ascending denominator:

We meanwhile have fractions $$\frac {p_0}{q_0}<u\le \frac {p_1}{q_1}<\ldots <\frac{p_m}{q_m} <v\le \frac {p_{m+1}}{q_{m+1}}$$ for some $m\ge 1$. Determine $0\le i\le m$ such that $q_i+q_{i+1}$ is minimal and insert the Farey sum $\frac{p_i+p_{i+1}}{q_i+q_{i+1}}$ into the sequence (kicking out $\frac{p_0}{q_0}$ if it is $<u$, kicking out $\frac {p_{m+1}}{q_{m+1}}$ if it is $\ge v$, otherwise adding a new valid fration to our list). Repeat this until the next fraction would have denominator $\ge \frac1{v-u}$.

For each found fraction in $[u,v)$ check if the other percentages also allow this denominator (and there can be at most one matching numerator).


Example: With the above method, the fractions produced are (in this order) $\frac 12, \frac13, \frac25, \frac37,\frac49,\frac5{11},\frac6{13},\frac7{15},\frac8{17}$, after which we arrive at $$\tfrac01<\tfrac13<\tfrac25<\tfrac37<\tfrac49<\tfrac5{11}<\tfrac6{13}<\tfrac7{15}< \frac{8}{17}<u\le \frac 9{19}<v\le \frac 12<\tfrac11,$$ (fractions that got rejected are shown in smaller type) thus the first candidate is $\frac9{19}$. Next, we'll replace $\frac12$ with $\frac{10}{21}$, then $\frac8{17}$ with $\frac{17}{36}$, then find $\frac{19}{40}$ on the right, $\frac{26}{55}$ on the left and again $\frac{28}{59}$ on the right, then $\frac{35}{74}$ on the left. The next step produces $\frac{37}{78}$, which does lie in the interval and thus gives us the next smallest solution (apart from writing $\frac9{19}$ in non-smallest terms): $$\tfrac{8}{17}<\tfrac{17}{36}<\tfrac{26}{55}<\frac{35}{74}<u\le \frac 9{19}<\frac{37}{78}<v\le \frac {28}{59}<\tfrac{19}{40}<\tfrac{10}{21}<\tfrac12,$$ so it does take a few steps to find the next fraction in $[u,v)$. Next come $\frac{44}{93}$ and then $\frac{46}{97}$: $$\tfrac{35}{74}<\frac{44}{93}<u\le \frac{9}{19}<\frac{46}{97}<\frac{37}{78}<v\le \frac{28}{59} $$ and then after a few more steps $$\tag1\tfrac{44}{93}<\tfrac{53}{112}<\frac{62}{131}<u\le \frac{9}{19}<\frac{64}{135}<\frac{55}{116}<\frac{46}{97}<\frac{37}{78}<\frac{65}{137}<v\le \frac{28}{59}.$$ For completeness, this should be repeated until we reach denominators $\ge 1000$.

Do the same with $26.3\%$, i.e. with $u=0.2625$, $v=0.2635$: $$\tag2 \tfrac01<\tfrac14< \tfrac6{23}<\tfrac{11}{42}<\frac{16}{61}<u\le\frac{21}{80}<\frac5{19} <v\le \tfrac{19}{72}<\tfrac{14}{53}<\tfrac9{34}<\tfrac{4}{15}<\tfrac3{11}<\ldots$$ (merely continued until we find at least one more fraction in the interval). By sheer luck, we find the same denominator $19$ in both (1) and (2), thus giving us an immediate solution $9:5:5$, as well as all multiples $18:10:10$, $27:15:15$ and so on. But we may just as well 8and have to if there is no common denominator) pick any valid fraction from (1), any valid fraction from (2) and bring them to the $\lcm$ of the denominators. For example $\frac{55}{116}$ and $\frac{21}{80}$ give us the solution $1100:609:611 $, which however is bad for one reasons: The $\lcm$ is $2320>1000$, i.e. so big that we are in the realm of arbitrary denominators anyway. At any rate, (1) alone shows that the next simplest solutions are with denominators $78, 97$ and then $>100$, but as (2) supports neither $78$ nor $97$, so that there definitely cannot exist any other small solution (less than $100$ people) apart from $9:5:5$ and its multiples.

share|improve this answer

First, let me state that if the number of votes are high enough, then you most likely can't get it anyway. For example, if you have three decimal places as above but the total vote counts are more than about 20 or 30, it might be impossible as some fractions will actually have the same decimal representation.

However, in this case, what you can do is try to find continued fraction approximations of each number, and pick a denominator that 1) is common to all the percentages, and 2) actually gives the correct rounded result.

share|improve this answer
1  
My comment to robjohn's solution applies here as well. The smallest solution is not guaranteed to appear among the approximants. –  Hagen von Eitzen Feb 2 '13 at 11:53

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.