Draft solutions for CMI BSc entrance exam on May 19, 2024

Send any comments to [email protected] by May 25, 2024.

In the online exam the instruction page counted as question 1, so the 21 part A questions
were numbered from 2 to 22. For any correspondence refer to the numbering below.

A test developed to detect Covid gives the correct diagnosis for 99% of people with Covid.
1
It also gives the correct diagnosis for 99% of people without Covid. In a city 1000 of the
population has Covid. Answer questions (1) and (2) as per the instruction below.

Questions

(1) What is the probability that a randomly selected person tests positive? (We assume that
in our random selection every person is equally likely to be chosen.) [2 points]

(2) Suppose that a randomly selected person tested positive. What is the probability that
this person has Covid? [2 points]

Instruction for (1) and (2)

If the probability is x%, then your answer should be the integer closest to x. E.g., for
probability 13 = 33.33 . . . %, you should type 33 as your answer. For probability 32 you should
type 67 as your answer.

Solution: Let C = event that the person has Covid, T = event that the test is positive.
Question (1) asks for P (T ) and question (2) asks for P [C|T ].
1 999 1 10.98 549
P [T ] = × 0.99 + × 0.01 = (0.99 + 9.99) = = = 1.098% ≈ 1%.
1000 1000 1000 1000 50000
1
P [C&T ] 1000
× 0.99 0.99 11
P [C|T ] = = 10.98 = = ≈ 9.02% ≈ 9%.
P [T ] 1000
10.98 122

Note: Most of the positive tests are false positives coming from Covid-free people, which
“explains” why the answer to (2) is so low. Because only 0.1% of the population has Covid,
positive tests coming from this group are an order of magnitude fewer than false positives
coming at 1% rate from Covid-free people who make up 99.9% of the population. This also
explains the answer to (1): when rounded down, it is the “same” 1% rate.
Consider the polynomial

p(x) = x6 + 10x5 + 11x4 + 12x3 + 13x2 − 12x − 11.

Questions

(3) Find the remainder when p(x) is divided by x + 1. [1 point]

P6 2
(4) Let z1 , z2 , z3 , z4 , z5 , z6 be the six complex roots of p(x). Evaluate i=1 zi . [2 points]

(5) Find an integer n with the least possible absolute value such that p(x) has a real root
between n and n + 1. Write this number along with your reason as per the instruction below.
[2 points]

Instruction for (5)

Write two numbers separated by a comma: value of n, number of the theorem below that
justifies this answer. E.g., if you think that n = 5 because of the factor theorem, then type
5,1 as your answer with no space, full stop or any other punctuation.

1. Factor theorem

2. Mean value theorem

3. Intermediate value theorem

4. Fundamental theorem of algebra

5. Fundamental theorem of calculus

Solution: (3) p(−1) = 4

(4) 6i=1 zi2 = ( i zi )2 − 2 i<j zi zj = (−10)2 − 2(11) = 78.

P P P

(5) p(0) = −11 and p(1) > 0. By intermediate value theorem p has a root between 0 and 1.
Two mighty frogs jump once per unit time on the number line as described below.

Questions

(6) The first frog is at x = 2i at time t = i. How many numbers of the form 7n + 1 (with n
an integer) does the frog visit from t = 0 to t = 99 (both endpoints included)? [3 points]

(7) The second frog starts at x = 0 and jumps i + 1 steps to the right just after t = i, so that
at times t = 0, 1, 2, 3, . . . this frog is at positions x = 0, 1, 3, 6, . . . respectively. How many
numbers of the form 7n + 1 (with n an integer) does the frog visit from t = 0 to t = 99 (both
endpoints included)? [3 points]

Solution: (6) For t = 0, 1, 2, 3, 4, 5, . . . the positions mod 7 are 1,2,4,1,2,4,. . . by repeatedly

multiplying by 2 modulo 7. So positions 1 mod 7 are occupied at t = every multiple of 3,
starting at 0. There are 34 multiples of 3 from 0 to 99 including both endpoints.

(7) Here we repeatedly add the sequence 1, 2, 3, 4, 5, 6, 7 = 0 mod 7 to previous position. For
t = 0, 1, 2, 3, 4, 5, 6, . . . we get the repeating pattern 0, 1, 3, 6, 3, 1, 0 of positions mod 7. Thus
a 1 mod 7 position occurs precisely for t = 1 mod 7 and t = 5 mod 7. So till 98 = 14 × 7
we get 14 × 2 = 28 such occurrences. We also get an occurrence at 99, which is 1 mod 7. So
the answer is 29.
Let O = (0, 0, 0), P = (19, 5, 2024) and Q = (x, y, z) be points in 3-dimensional space where
Q is an unknown point.
−→ −→
Consider vector u = OP = 19 î + 5 ĵ + 2024 k̂ and unknown vector v = OQ = x î + y ĵ + z k̂.
Instruction: for each of the sets below choose the correct option describing it and enter the
number of that option. E.g., if you think a given set is a line, enter 3 as your answer with
no full stop or any other punctuation.
Questions
(8) {Q | u · v = 2024}. [1 point]
√
(9) {Q | u · v = −2024 v · v }. [2 points]
(10) {Q | u · v = 2024 (v · v)}. [2 points]

Options
1. The empty set
2. A singleton set
3. A line
4. A pair of lines
5. A circle
6. A plane perpendicular to u
7. A plane parallel to u
8. An infinite cone
9. A finite cone
10. A sphere
11. None of the above

Solution: (8) A plane perpendicular to u.

√ √
(9) u · v = u · u v · v cos(θ) where θ is the angle between u and v (between 0 and 180◦ ).
So the given condition for nonzero v is cos(θ) = −2024
√
u·u
, which is a constant between −1 and 0
√
as u · u > 2024. So the given set consists of endpoints of all vectors making a fixed obtuse
angle with u, along with the origin. This is an infinite cone.
(10) This is the set of points satisfying 19x + 5y + 24z = 2024(x2 + y 2 + z 2 ). Taking LHS
to RHS and completing three squares, we get the equation of a sphere passing through the
origin.
An integer d is called a factor of an integer n if there is an integer q such that n = dq.
In particular the set of factors of n contains n and contains 1. You are given that 2024 =
8 × 11 × 23.

Questions

(11) Write the number of even positive integers that are factors of 20242 . [2 points]

(12) Write the number of ordered pairs (a, b) of positive integers such that a2 − b2 = 20242 .
If there are infinitely many such pairs, write the word infinite as your answer. [3 points]

Solution: (11) Answer: 54. As 20242 = 26 ×112 ×232 , the number of factors is 7×3×3 = 63.
Of these 6 × 3 × 3 = 54 are even as the power of 2 in an even factor cannot be 0.

(12) Answer: 22. Observe that 20242 = (a + b)(a − b) is a factorization with unequal factors
of the same parity which must be even. Conversely, given a factorization dq of 20242 into
even unequal factors, we get a unique solution for a, b by solving a + b = the larger factor
and a − b = the smaller factor. The number of factors d such that both d and 2024
d
are even
is 5 × 3 × 3 = 45 as the power of 2 in d cannot be 0 or 6. Of these the equal factors case
d = q = 2024 should be discarded (as that gives b = 0). The other 44 values of d break into
22 pairs, giving 22 solutions.
A good path is a sequence of points in the XY plane such that in each step exactly one of
the coordinates increases by 1 and the other stays the same. E.g.,

(0, 0), (1, 0), (2, 0), (2, 1), (3, 1), (3, 2), (3, 3)

is good path from the origin to (3,3). It is a fact that there are exactly 924 good paths from
the origin to (6,6).

Questions

(13) Find the number of good paths from (0, 0) to (6, 6) that pass through both the points
(1, 4) and (2, 3). [1 point]

(14) Find the number of good paths from (0, 0) to (6, 6) that pass through both the points
(1, 2) and (3, 4). [2 points]

(15) Find the number of good paths from (0, 0) to (6, 6) such that neither of the two points
(1, 2) and (3, 4) occurs on the path, i.e., the path must miss both of the points (1, 2) and
(3, 4). [3 points]

Solution: (13) 0. Going to one of (1, 4) and (2, 3) precludes going to the other as for that
to happen one coordinate would have to decrease and that is not possible in a good path.

(14) 2+1 × 3+4−(1+2) × 6+6−(3+4) = 31 × 42 × 53 = 3 × 6 × 10 = 180.

1 3−1 6−3

(15) We use basic set theory.

3 9



Number of paths through (1, 2) is 1
× 5
= 3 × 126 = 378.
7 5



Number of paths through (3, 4) is 3
× 3
= 35 × 10 = 350.
Number of paths through (1, 2) or (3, 4) is 350 + 378 − 180 = 548.
Number of paths missing both (1, 2) and (3, 4) is 924 − 548 = 376.
Suppose f is a function whose domain is X and codomain is Y . It is given that |X| > 1 and
|Y | > 1. No other information is known about X, Y and f . Instruction: for each question
below write the number of a single correct option for the given statement S.

Questions [1 point each]

(16) S = “For each x in X, there exists y in Y such that f (x) = y.”

(17) S = “For each y in Y , there exists x in X such that f (x) = y.”

(18) S = “There exists a unique x in X such that for each y in Y it is true that f (x) = y.”

(19) S = “There exists a unique y in Y such that for each x in X it is true that f (x) = y.”

Options (with each question’s number written next to its matching option)

1. S is always true. (16)

2. S is always false. (18)

3. S is true if and only if f is one-to-one.

4. If S is true then f is one-to-one but the converse is false.

5. If f is one-to-one then S is true but the converse is false.

6. S is true if and only if f is onto. (17)

7. If S is true then f is onto but the converse is false.

8. If f is onto then S is true but the converse is false.

9. S is true if and only if f is a constant function. (19)

10. If S is true then f is a constant function but the converse is false.

11. If f is a constant function then S is true but the converse is false.

12. None of the above.

Solution: This is a matter of careful reading and interpretation of precise language.

Suppose a differentiable function f from R to R has a local maximum at (a, f (a)) (This
means there are numbers m and M such that (i) m < a < M and (ii) f (a) ≥ f (x) for any
x ∈ [m, M ].) The proof of a standard result is sketched below. Complete it as instructed.
Proof: For sufficiently 1 h > 0, it is given that f (a + h) 2 3 .
Therefore for such h the quantity 4 must be 5 6 .
By taking the limit of this quantity as h → 0 from the right, we get that 7 must be
8 9 .
A parallel argument for suitable negative values of h gives that 10 must be 11 12 .
Combining both conclusions gives the desired result: 13 14 15 . Note that the
mentioned limits exist because 16 .
Questions
(20) Write a sequence of 9 letters indicating the correct options to fill in the numbered blanks
1 to 9. Do not use any spaces, full stop or other punctuation. E.g., ABACDIJKB is in
the correct format. [3 points]
(21) Write a sequence of 7 letters indicating the correct options to fill in the numbered blanks
10 to 16. [2 points]
Options
A. small B. large

C. ≥ D. >

E. ≤ F. <

G. = H. 6=

I. 0 J. f (a)

f (a+h)−f (a)
K. h
L. f 0 (a)

M. f is differentiable N. f is continuous

Solution: For sufficiently small h > 0, it is given that f (a + h) ≤ f (a).

f (a+h)−f (a)
Therefore for such h the quantity h
must be ≤ 0.
By taking the limit of this quantity as h → 0 from the right, we get that f 0 (a) must be ≤ 0.
A parallel argument for suitable negative values of h gives that f 0 (a) must be ≥ 0.
Combining both conclusions gives the desired result: f 0 (a) = 0.
Note that the mentioned limits exist because f is differentiable.
 Solutions to Part B Problems

B1. [10 points] (a) Draw a qualitatively accurate sketch of the unique bounded region
R in the first quadrant that has maximum possible finite area with boundary described as
follows. R is bounded below by the graph of y = x2 − x3 , bounded above by the graph of
an equation of the form y = kx (where k is some constant), and R is entirely enclosed by
the two given graphs, i.e., the boundary of the region R must be a subset of the union of the
given two graphs (so R does not have any points on its boundary that are not on these two
graphs). Clearly mark the relevant point(s) on the boundary where the two given graphs
meet and write the coordinates of every such point.

(b) Consider the solid obtained by rotating the above region R around Y-axis. Show how to
find the volume of this solid by doing the following: Carefully set up the calculation with
justification. Do enough work with the resulting expression to reach a stage where the final
numerical answer can be found mechanically by using standard symbolic formulas of algebra
and/or calculus and substituting known values in them. Do not carry out the mechanical
work to get the final numerical answer.

Solution to B1: (a) Increasing k from 0 rotates the line counterclockwise and increases the
desired area until the line stops intersecting
the graph of y = x2 −x3 in the first quadrant.
So bounded R with maximum possible area
is obtained when the line is tangent to the
graph of y = x2 − x3 in the first quadrant.
See the picture. At the point of tangency the
slope is k = 2x − 3x2 and the y coordinate
is kx = x2 − x3 . Solving gives the point of
tangency = (0.5, 0.125) and slope k = 0.25.

(b) This can be done by either the “washer”

method or the “shell” method. The washer
method divides R into horizontal slices of
“tiny height dy” and integrates along Y-axis
the volumes of the resulting thin washers of
revolution around Y-axis. This gives
Z 0.125
desired volume = πx2 dy − (volume of a cone of radius 0.5 and height 0.125),
0

2 3 2
where x and y in the integral are related R 0.5 2 by y = 2x − x . So dy = (2xπ− 3x 2)dx. After
substitution the integral becomes π 0 x (2x − 3x )dx. Cone volume = 3 (0.5) (0.125) (or
R 0.125 2
R 0.5 π
0
π(4y) dy or 0
(0.25)πx2 dx). Overall answer (not asked for) is 480 .
The shell method divides R into vertical slices of “tiny width dx” and integrates along X-axis
the volumes of resulting shells of revolution around Y-axis. This gives the following integral
and the same numerical answer.
Z 0.5 Z 0.5
desired volume = 2πx(y1 − y2 )dx = 2π x(0.25x − (x2 − x3 ))dx.
0 0

B2. [15 points] (a) Find the domain of the function g(x) defined by the following formula.
Z x
log10 log10 (t2 − 1000t + 101000 ) dt.


g(x) =
10

Calculate the quantities below. You may give an approximate answer where necessary, but
clearly state which answers are exact and which are approximations.
(b) g(1000).
(c) x in [10,1000] where g(x) has the maximum possible slope.
(d) x in [10,1000] where g(x) has the least possible slope.
ln(x)
(e) limx→∞ g(x)
if it exists.

Solution to B2: (a) The parabola t2 −1000t takes lowest value −250000 (at t = 500), which
is absolutely dwarfed by 101000 = (1 followed by 1000 zeros). So log10 (t2 − 1000t + 101000
)
2 1000
is defined for any t and is always greater than 999. So log10 log10 (t − 1000t + 10 ) is
defined for any t. The integrand is a continuous function, so g(x) is defined for all real x.

(b) The log function increases very slowly, so log log increases extremely slowly. In the
interval [10,1000], the values of t2 − 1000t are in [−250000, 0] and have no practical effect
on the order of magnitude of the far larger 101000 . So throughout the interval of integration
[10,1000], log10 (t2 − 1000t + 101000 ) is extremely close to 1000 and log10 of that is extremely
close to 3. So we are essentially integrating the constant function 3. The answer is ≈
3 × (1000 − 10) = 2970. This answer is correct to a very high degree of accuracy and a
rigorous calculation bounding the error can be given, but for this exam the above simple
qualitative answer was enough. (Idea taken from “Lucky numbers” in Surely You’re Joking,
Mr. Feynman! “People started giving me problems they thought were difficult such as
integrating a function ... which hardly changed over the range they gave me”. Also worth
reading are Feynman’s thoughts on education near the end of “O Americana, Outra Vez!”,
starting with “In regard to education in Brazil, I had a very interesting experience ...”)

(c,d) Slope of g is g 0 (x), which is log10 log10 (x2 − 1000x + 101000 ) by the fundamental

theorem of calculus. As log10 is an increasing function, we may simply discard the log10 log10
in the front and find extrema of x2 −1000x+101000 over the interval [10,1000]. This parabola
takes minimum value at its vertex which is at x = 500. By symmetry of the parabola, the
maximum value occurs at the endpoint farther from the vertex of the parabola, namely at
x = 1000. (Note that while these are theoretically exact answers, g 0 (x) sees extremely tiny
variation thanks to flattening due to log log.)

(e) Both ln(x) and g(x) go to ∞ as x → ∞ but the denominator dominates. (Why?) Proof:
By L'Hôpital’s rule the required limit can be checked via limx→∞ g1/x
0 (x) , which is 0 as 1/x → 0

and g (x) = log10 log10 (x − 1000x + 10 ) → ∞. (Note: calculating limx→∞ xg(x)

0 ln(x)
2 1000


is a
bit more interesting. What is the answer?)

B3. [15 points] (a) For non-negative numbers a, b, c and any positive real number r prove
the following inequality and state precisely when equality is achieved.

ar (a − b)(a − c) + br (b − a)(b − c) + cr (c − a)(c − b) ≥ 0

Hint: Assuming a ≥ b ≥ c do algebra with just the first two terms. What about the third
term? What if the assumption is not true?
(b) As a special case obtain an inequality with a4 + b4 + c4 + abc(a + b + c) on one side.
(c) Show that if abc = 1 for positive numbers a, b, c, then
a2 + b 2 b 2 + c 2 c 2 + a2
a4 + b 4 + c 4 + a3 + b 3 + c 3 + a + b + c ≥ + + + 3.
c a b

Solution to B3: (a) This is known as Schur’s inequality. Here is the standard argument.

We may assume a ≥ b ≥ c because the inequality is completely symmetric in a, b, c, i.e.,

any interchange of two letters gives the same inequality (check this), and therefore so does
any permutation of a, b, c. (Alternatively, if a ≥ b ≥ c is not true, then arrange a, b, c in
a decreasing order and use similar reasoning as below by separating the term with three
occurrences a least one among of a, b, c. Check this in two cases: b ≥ a ≥ c and b ≥ c ≥ a.)


So let a ≥ b ≥ c. First note ar (a − b)(a − c) + br (b − a)(b − c) = (a − b) ar (a − c) − br (b − c) .
Now ar ≥ br ≥ 0 and a − c ≥ b − c ≥ 0. Multiplying the left sides and the middle terms we
get ar (a − c) ≥ br (b − c), so ar (a − c) − br (b − c) ≥ 0. Now multiplying by (a − b) gives

(a − b) ar (a − c) − br (b − c) = ar (a − b)(a − c) + br (b − a)(b − c) ≥ 0.

Adding cr (c − a)(c − b) ≥ 0 (which is true when a ≥ b ≥ c), we get the desired inequality.

To have equality, trace all used inequalities to deduce the necessary and sufficient condition


(a = b) OR (ar = br ) and (a − c = b − c) AND cr (c − a)(c − b) = 0.
This happens exactly when (a = b) AND (c = 0 or c = a or c = b). Using symmetry we get
equality precisely when a = b = c or when one of a, b, c is zero and the other two are equal.
(b) Substitute r = 2 and do algebra to get

a4 + b4 + c4 + abc(a + b + c) ≥ ab(a2 + b2 ) + bc(b2 + c2 ) + ca(c2 + a2 ).

(c) (Problem by Dan Sitaru, this solution by Imad Zak, source www.cut-the-knot.org) Use
abc = 1 in part (b). Cancel abc from the left and divide by abc on the right to get

a2 + b 2 b 2 + c 2 c 2 + a2
a4 + b 4 + c 4 + a + b + c ≥ + + .
c a b
We will be done by showing a3 + b3 + c3 ≥ 3 = 3abc, which is true by AM ≥ GM .

B4. [10 points] Find all solutions of the following equation where it is required that
x, k, y, n are positive integers with the exponents k and n both > 1.

20xk + 24y n = 2024.

Solution to B4: First solve 20a + 24b = 2024 in integers. For any solution (a, b), the pair
(a − 6k, b + 5k) is also a solution for any integer k.

Moreover any solution (a0 , b0 ) is obtainable this way from a single known solution (a, b).
Proof: we have 20(a − a0 ) + 24(b − b0 ) = 0, so 5(a − a0 ) + 6(b − b0 ) = 0. As gcd(5, 6) = 1, we
see that 6 must be a factor of a − a0 (and 5 must be a factor of b − b0 ). Letting a − a0 = 6k,
the equation 5(a − a0 ) + 6(b − b0 ) = 0 implies b − b0 = −5k, so (a0 , b0 ) = (a − 6k, b + 5k) as
claimed.

Observe that a = 100, b = 1 is a solution. As subtracting 5 from b = 1 gives a negative

number, we can take only positive values of k to generate the remaining positive integer
solutions. One gets 17 solutions in positive integers, the last one being a = 100 − 16 × 6 = 4
paired with b = 1 + 16 × 5 = 81. Listing all 17 solutions shows that (100,1) and (4,81) are the
only ones in which a, b are both perfect powers: 100 = 102 , 1 = 1any n , 4 = 22 , 81 = 34 = 92 .

B5. [15 points] (a) Find all complex solutions of z 6 = z + z.

(b) For an integer n > 1, how many complex solutions does z n = z + z have?

Solution to B5: (b) z = 0 is a solution. From now on let z 6= 0. Suppose z = reθi . So

z n = rn enθi = z + z = 2r cos θ, which is real. So the equation is true if and only if
   
enθi = 1 and rn = 2r cos θ OR enθi = −1 and rn = −2r cos θ .
Case 1. In the first case eθi must be an nth root of 1 and its real part cos θ must be positive
n−1
because cos θ = r 2 is positive. Conversely for any one of such values of θ, the preceding
equation uniquely determines r, thus giving a solution of the given equation. The number
of such θ can be calculated by cases mod 4.
• For n = 4k we get 2k − 1 valid values of θ as two of the nth roots of 1 are imaginary
and half of the remaining 4k − 2 have positive real part.
• For n = 4k + 1, 4k + 2, 4k + 3, we get 2k + 1 valid values of θ, namely θ = 0 and k
values each in the first and fourth quadrant because 2kπ
n
< π2 < 2(k+1)π
n
.
Case 2. Otherwise eθi must be an nth root of −1 and its real part cos θ must be negative
n−1
because cos θ = − r 2 is negative. Conversely for any one of such values of θ, the preceding
equation uniquely determines r, giving a solution of the given equation. The number of
valid θ can again be calculated by cases mod 4. Let S = (set of angles of nth roots of −1) =
{ (2j+1)π
n
| j = 1, . . . , n}, i.e., the set of angles obtained by rotating each nth root of 1 halfway
to the next root. We need to find angles θ in S with π2 < θ < 3π 2
.
• For n = 4k we get 2k valid values of θ as exactly half the angles in S are on each side
of the Y axis.
• For n = 4k + 2 we get 2k valid values of θ as two of the angles in S are on the Y axis.
For odd n, note that if z is a root, then so is −z. So for odd n, (number of roots in case 2)
= (number of roots in case 1), giving 2k + 1 case 2 roots for n = 4k + 1, 4k + 3. We can also
get this by continuing brute force analysis.
(2j+1)π
• For n = 4k + 1 we get 2k + 1 valid values of θ, namely θ = 4k+1
for j = k, . . . , 3k.
(2j+1)π
• For n = 4k+3, we get 2k+1 valid values of θ, namely θ = 4k+3
for j = k+1, . . . , 3k+1.
Adding up the number of solutions of two types and counting z = 0, we get the following
result. The total number of solutions of the equation z n = z + z (for integer n > 1) is n + 2
when n = 1 mod 4 and n otherwise. One can check this for several n on a numerical solver,
e.g., at https://www.wolframalpha.com.

Aside: if z is a root, then so is z. (Why?) This symmetry does not seem helpful to reduce
work, but it does explain some of the numerology, e.g., case 1 always gives an odd number
of roots (because θ = 0 always gives a root) while case 2 gives odd or even number of roots
depending on whether θ = π gives a root or not. But θ = π means z is a negative real
number and such a root exists exactly when n is odd.

(a) Applying the general analysis above gives five nonzero solutions: three with positive real
part (case 1 above), and two with negative real part (case 2 above). Working out the details
gives the following list of six solutions.
√  √
√ √ ± 5πi √ − 3±i

5 ± πi 1 ± 3i 10 10
0 2 e 3 = 3e 6 = 3
2 2
B6. [15 points] A list of k elements, possibly with repeats, is given. The goal is to find
if there is a majority element. This is defined to be an element x such that the number of
times x occurs in the list is strictly greater than k2 . (Note that there need not be such an
element, but if it is there, it must be unique.) A celebrated efficient way to do this task uses
two functions f and m with domain {1, 2, . . . , k}. The functions are defined inductively as
follows.

Define f (1) = first element of the list, m(1) = 1.

Assuming f and m are defined for all inputs from 1 to i, define
(
f (i) if m(i) > 0
f (i + 1) = th
(i + 1) element of the list if m(i) = 0
(
m(i) − 1 if m(i) > 0 and (i + 1)th element of the list is other than f (i)
m(i + 1) =
m(i) + 1 otherwise

(a) For the example of length 15 given below, write a sequence of 15 letters showing the
values of f (i) and a sequence of 15 numbers directly underneath showing the values of m(i)
for i = 1, 2, . . . , 15.
aababccbbbabbcb

(b) Prove that in general the list can be divided into two disjoint parts A and B such that
• Part A contains m(k) elements of the list each of which is f (k).

• Part B contains the remaining k − m(k) elements of the list and B can be written as
disjoint union of pairs such that the two elements in each pair are distinct.

(c) If there is a majority element, show that it must be f (k). You may assume part (b) even
if you did not do it.

(d) Assuming f (k) is the majority element, answer the following two questions. Show by
examples that the number of occurrences of f (k) in the list does not determine the value
of m(k). Can the value of m(k) be anything in {0, . . . , k}? Find constraints if any on the
possible values of m(k).
k
(e) Now assume instead that an element occurs exactly 2
times in the list. Is it necessary
that f (k) is such an element?

Solution to B6: This is the well known Boyer-Moore majority vote algorithm. Note some
features of this clever procedure. To calculate f (i + 1) and m(i + 1) one needs only f (i) and
m(i). No need to “remember” previous values! The inductive nature means a single pass of
the list gives a unique candidate f (k) for the majority element. (To verify that f (k) indeed
has majority, one pass won’t do. One can count occurrences of f (k) in a second pass.)
(a) One follows the procedure to get the following table of values of f and m for i = 1, . . . , 15.

i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
list a a b a b c c b b b a b b c b
f (i) a a a a a a c c b b b b b b b
m(i) 1 2 1 2 1 0 1 0 1 2 1 2 3 2 3

(b) Use induction. Initially part A contains f (1) and part B is empty, so the claim is true.
Assuming it is true at stage i we make three cases at stage i + 1.
• If m(i) = 0, by induction part A is empty. We just put the (i + 1)th element in part A
and leave part B untouched.
• If m(i) > 0 and the incoming element is the same as f (i), again put the (i+1)th element
in A and leave B untouched. This case can also be combined with the previous one.
• If m(i) > 0 and the incoming element is different from f (i), we remove one copy of
f (i) from part A (which is there by induction as m(i) > 0), pair it with the incoming
element and place this pair of distinct elements in part B.
In all cases the claim stays true by using induction and the definition of f (i+1) and m(i+1).
(c) By the claim proved in (b), the number of occurrences of any element in part B can be
at most half of the size of B. So the majority element has to occur in part A (otherwise it
cannot occur more that k2 times). But all elements in part A are f (k), so f (k) must be the
majority element.
(e) No. The list cabc of length 4 has c occurring twice but f (4) = b.
(d) The lists abccc and aaccc both have the majority element c occurring thrice but different
m(5), namely 3 and 1 respectively.
Some constraints on possible values of m(k) are as follows. First, the answer to (b) shows
that if there is a majority element, it has to occur in part A, so m(k) = size of part A cannot
be 0. Second, by part (b) we also have that m(k) ≤ number of occurrences of f (k). Finally
as m(1) = 1 and since the value of m changes by 1 at each step, m(k) must have the same
parity as k. The second and third properties are true for all lists regardless of whether there
is a majority element.
Conversely, given the list length k, the number of occurrences n of the majority element (say
x) and any nonzero number p ≤ n with p of the same parity as k, one can easily construct
a list with m(k) = p as follows. Put p occurrences of x at the end of the list and ensure
that every element in an even numbered slot among the first k − p elements differs from the
preceding element. This means that values of m(i) follow the pattern 1, 0, 1, 0, . . . , 1, 0 until
index i = k − p, which is even. (This simpleminded scheme can realize a desired value p of
m(k) of the correct parity regardless of existence of the majority element if one is given an
element x with pre-specified frequency ≥ p. If there are more constraints, e.g., if frequencies
of all list elements are pre-specified, then possible values of m can have more restrictions.)