I’m on a bit of a continued fractions jaunt at the moment, as they’re my current “oo! That’s a tool I haven’t played with enough, and that I think might be interesting!”

One of their applications (surprisingly to me) is to answer the question “A survey firm says ‘82.43% of our respondents said [x].’ Given that they rounded the percentage to two decimal places, what’s the smallest number of people they could have asked?”

Naively, one might say “Well, it’s between $\frac{82425}{100000}$ and $\frac{82435}{100000}$ and we just need to find the fraction between those with the smallest denominator!” This is, of course, true. However, the word “just” is doing an awful lot of heavy lifting there.

Instead, we can represent 0.82425 and 0.82435 as continued fractions and see where their expansions coincide..

How do we do that?

We start with the lower bound as a fraction, $\frac{82425}{100000}$ and say “It’s less than 1, so the first entry in the continued fraction is 0.”

We then invert it to find the next number, $\frac{100000}{82425}$, which is between 1 and 2, so the second entry is 1. We take that away, leaving us with $\frac{17575}{82425}$.

We invert this to find the next number, $\frac{82425}{17575}$. We could even cancel that down to $\frac{3297}{703}$, which is between 4 and 5, so the third entry is 4. We’re left with $\frac{485}{703}$.

Again, we invert to find the next number, $\frac{703}{485}$, which is between 1 and 2, so entry number four is 1. Taking it away, we now have $\frac{218}{485}$

Another inversion: $\frac{485}{218}$ is between 2 and 3, so the fifth entry is 2; subtract and we get $\frac{49}{218}$

Flip: $\frac{218}{49}$. The sixth entry is 4. Take it away: $\frac{22}{49}$. We’re getting close to the end now!

Flip: $\frac{49}{22}$, so the seventh entry is 2, and we have $\frac{5}{22}$ left.

Flip: $\frac{22}{5}$ gives us 4 for entry number eight, and $\frac{2}{5}$ left over after subtracting.

Then $\frac{5}{2}$ gives us 2, and $\frac{1}{2}$ as a remainder.

And finally we have an integer 2 at the end.

The full continued fraction expansion is $[0; 1, 4, 1, 2, 4, 2, 4, 2, 2]$.

How does it help?

We can work out the upper bound the same way: it’s $[0; 1, 4, 1, 2, 3, 1, 6, 2, 1, 12]$.

This first differst from the lower bound in the sixth element - and if we just take the first six terms, $[0; 1,4,1,2,3]$ and $[0; 1,4,1,2,4]$, at least one of them is between the two limits. ((I’m taking that on trust. It seems reasonable. Prove it in the comments if you’d like to!))

How do we work that out? We use the magic table method! We write the continued fraction across the top of the table, and put 0 1 and 1 0 at the start of the first two rows, like so:

     0  1  4  1  2  (3 or 4)
1 0
0 1

Now, the rules we follow are “multiply the rightmost number in each row by the number at the top of each column; add it to the next-to-rightmost number, and write the sum down.” For the first row, that means we multiply 1 by 0 and add 0; in the second, we multiply 0 by 0 and add 1, so we write down 0 and 1 next:

     0  1  4  1  2  (3 or 4)
0 1  0
1 0  1

We then carry on the same way: zero by 1, add 1, and 1 by 1 add 0:

     0  1  4  1  2  (3 or 4)
0 1  0  1
1 0  1  1

(What’s going on here is that the last two columns represent upper and lower bounds on our eventual answer - which is between 0/1 and 1/1.)

The next numbers are 4 and 5

     0  1  4  1  2  (3 or 4)
0 1  0  1  4
1 0  1  1  5

Then 5 and 6:

     0  1  4  1  2  (3 or 4)
0 1  0  1  4  5
1 0  1  1  5  6

And finally, 14 and 17:

     0  1  4  1  2  (3 or 4)
0 1  0  1  4  5  14
1 0  1  1  5  6  17

If we go with 3, we get 47 and 57; if we go with 4, we get 61 and 74, so our answer is between 47/57 and 61/74. These work out to 0.82456 and 0.82432, the lower of which rounds to 82.43%! That means, the survey firm must have had at least 74 respondents.

I haven’t dug far enough in to figure out how to pick between the two limits without working the fractions out by hand ((yes, sensei, absolutely by hand, I have not seen any calculators around here.)) – again, I’d welcome any insights in the comments!