The CSAT and Practice[+] are designed by the Climb Foundation to help candidates. We are advocates for more opportunity to shine and less opportunity to fail, and we strive to level the playing field.

The Computer Laboratory

Practice Paper 4 Question 18

A poll with 2 choices is run among \(n>2\) participants. Each participant chooses at random. The poll shows the results for the 2 options as percentages rounded to the nearest integer, i.e. \(x\) rounded is \(\lfloor x+0.5\rfloor\), where \(\lfloor x\rfloor\) is the greatest integer less than or equal to \(x\). For example, 1/3 would be shown as 33%. What is the probability that the sum of the 2 shown percentages does not add to 100?

The above links are provided as is. They are not affiliated with the Climb Foundation unless otherwise specified.

Warm-up Questions

  1. Why does \(\lfloor x+0.5\rfloor\) round \(x\) to the nearest integer? Use the ceiling function \(\lceil \cdot \rceil\) to create a rounding function.
  2. Under what circumstances is \(\lfloor a+1 \rfloor = \lceil a \rceil\) true?
  3. Boris flips \(8\) fair coins. What is the probability that at least \(6\) of them are tails?

Hints

  • Hint 1
    How are the two percentages related?
  • Hint 2
    Under what circumstances do the two rounded percentages not add up to 100? Try expressing it in an equation with integer solutions.
  • Hint 3
    The only scenarios in which the rounded percentages do not add up to 100 are when one of the percentages end in \(.5,\) causing both percentages to round up and their sum to be 101.
  • Hint 4
    Try phrasing the above condition in terms of \(n, k\) and \(j,\) where \(k\) is the number of votes for the first option and \(j\) is the integer of that percentage.
  • Hint 5
    Why not rearrange to get rid of all fractions and decimal points?
  • Hint 6
    Consider the prime factors of the terms in your equation. What can you deduce about the divisibility of \(n?\)
  • Hint 7
    \(n\) must be divisible by \(8.\) By substituting \(n = 8m,\) could you derive a new equation in terms of \(n, k\) and \(j?\)
  • Hint 8
    What are the possible factors of \(m?\) How about doing a case split?
  • Hint 9
    By considering divisibility of \(5,\) determine which values of \(j\) are possible.
  • Hint 10
    Given the possible values for \(j,\) what are the possible values for \(k?\)
  • Hint 11
    What is the probability that the \(n\) voters will choose one of the suitable \(k?\)

Solution

It suffices to consider the answers picking one of the options; suppose there are \(k\) of these. Then the rounded percentages of the two answers are \(\lfloor \frac{100k}{n} + 0.5\rfloor\) and \(\lfloor \frac{100(n-k)}{n} + 0.5\rfloor\) respectively. Adding these together we get \(100 + \lfloor \frac{100k}{n} + 0.5 \rfloor\) \(+ \lfloor 0.5 - \frac{100k}{n}\rfloor,\) which evaluates to 101 when the fractional part of \(\frac{100k}{n}\) is exactly \(0.5.\)

Thus, we need to solve \(\frac{100k}{n} = j + 0.5\) for \(j \in \{0, \dots, 99\}.\) Rearrange to obtain \(200k = n(2j+1).\) Since \(200 = 2^3 \cdot 5^2\) and \(2j+1\) must be odd, it must be the case that \(n\) is a multiple of \(2^3 = 8.\) Writing \(n=8m,\) our expression becomes \(5^2k=m(2j+1)\) for \(j\in \{0, \ldots, 99\}.\) There are three cases:

  1. \(m\) is not a multiple of \(5.\) This means that \(2j+1\) must be a multiple of \(25,\) hence the only possible values for \(2j+1\) are \(S_1 = \{25, 75, 125, 175\}.\)
  2. \(m\) is a multiple of \(5\) but not a multiple of \(25.\) This means that \(2j+1\) must be a multiple of \(5,\) hence the only possible values for \(2j+1\) are \(S_2 = \{5,15,25,35\ldots,195\}.\)
  3. \(m\) is a multiple of \(25.\) There is no restriction on \(j\) except \(j<100,\) hence the only possible values for \(2j+1\) are \(S_3 = \{1,3,5,7\ldots,199\}.\)

Each \(x \in S_i,\) \(K(x) = \frac{nx}{200}\) will result in the rounded percentages to not add up to \(100.\) Thus, the probability is:

\[ \begin{equation*} p(n)= \begin{cases} 0 & \text{if } 8\nmid n \\ 2^{-n}\sum_{x \in S_1}\binom{n}{K(x)} & \text{if } 8\mid n, 5\nmid n \\ 2^{-n}\sum_{x \in S_2}\binom{n}{K(x)} & \text{if } 40\mid n, 25\nmid n \\ 2^{-n}\sum_{x \in S_3}\binom{n}{K(x)} & \text{if } 200 \mid n \\ \end{cases} \end{equation*} \]

If you have queries or suggestions about the content on this page or the CSAT Practice Platform then you can write to us at oi.foo[email protected]. Please do not write to this address regarding general admissions or course queries.