Math Problem Solving Session 1 - Solutions

Udit Shah
August 2024

Problem 1
Suppose the first n prime numbers 2, 3, 5, . . . pn , are partitioned into two sets
arbitrarily. Let P1 and P2 be the products of all the elements in set 1 and set
2 respectively. In case of an empty set, let Pi = 1 . Prove that each of the
numbers P1 + P2 and |P1 −P2 | will also always turn out to be a prime number
for every such partition, given that Pi is less than p2n+1
Remark. The problem in its current form was not the intended problem.
The intended problem had the condition that |P1 ± P2 | < p2n+1 . Though I
think that the given problem is also true, it would require much more work
in proving it. One argument involves proving that p1 p2 · · · pn ≥ p4n+1 ∀n ≥
N0 for some N0 and individually checking the validity of the given statement
for n < N0 . So you may consider the given problem as a challenge problem
to prove or disprove. I present the intended problem and the solution to the
intended problem.

Intended Problem
Suppose the first n prime numbers 2, 3, 5, . . . pn , are partitioned into two sets
arbitrarily. Let A and B be the partitioned sets and let PA and PB be the
products of all the elements in A and B respectively. In case either A or B is
empty, let PA or PB = 1 . Prove that each of the numbers P1 + P2 and |P1 −
P2 | will also always turn out to be a prime number for every such partition,
given that |PA ± PB | is less than p2n+1

(Source : More Mathematical Morsels)

Solution
Each of the first n prime numbers divide either PA or PB but not both. So
none of them divide PA + PB or |PA − PB |. Then, any prime divisor of
PA + PB or |PA − PB | is greater than or equal to pn+1 . If there were more
than one prime divisor, then the number would be greater than or equal to

1
p2n+1 which is not possible. Therefore the number itself must be a prime p
such that pn+1 ≤ p < p2n+1

Problem 2
Determine all functions f : N 7→ N satisfying

xf (y) + yf (x) = (x + y)f (x2 + y 2 )

for all positive integers x and y.

(Source : 2002 Canadian Mathematical Olympiad)

Solution 1
The constant function f (x) = k, where k is a positive integer, is the only
possible solution. That any such function satisfies the given condition is easy
to check.
Now suppose there exists a nonconstant solution f . There must exist two
positive integers a and b such that f (a) < f (b). This implies that

(a + b)f (a) < af (b) + bf (a) < (a + b)f (b)

By the given condition this is equivalent to

(a + b)f (a) < (a + b)f (a2 + b2 ) < (a + b)f (b)

We can divide by a + b > 0 to obtain that

f (a) < f (a2 + b2 ) < f (b)

Thus between any two different values of f we can insert another. But this
cannot go on forever, since f takes only integer values. The contradiction shows
that such a function cannot exist. Thus constant functions are the only solu-
tions.

Solution 2
xf (y) + yf (x) = (x + y)f (x2 + y 2 ) (1)
Substituting y = x in 1, we get

2xf (x) = (2x)f (2x2 )

f (x) = f (2x2 ) (as x ̸= 0)

Substituting x = 1 in 1, we get

xf (1) + f (x) = (x + 1)f (x2 + 1)

2
So we have
xf (1) + f (x) ≡ 0 (mod (x + 1))
Since x ≡ −1 (mod (x + 1))

−f (1) + f (x) ≡ 0 (mod (x + 1))

Therefore
|f (x) − f (1)| ≡ 0 (mod (x + 1)) (2)
2
Replacing x by 2x , we get

|f (2x2 ) − f (1)| ≡ 0 (mod (2x2 + 1))

Since f (x) = f (2x2 ), we have

|f (x) − f (1)| ≡ 0 (mod (2x2 + 1))

Let a ∈ N be a constant and let f (a) = b . Now using f (x) = f (2x2 ), we can
obtain
b = f (a) = f (2a2 ) = f (8a4 ) = f (128a8 ) . . .
From 2, we have

|f (a) − f (1)| ≡ 0 (mod (k + 1)) k = f (a), f (2a2 ), f (8a4 ) . . .

Thus |f (a) − f (1)| has infinitely many divisors. So f (a) − f (1) = 0. Since a
was an arbitrary natural number and f (1) is a constant, we can conclude that
f (x) is constant for all postive integers x

Problem 3
You are the manager of a stadium, which is heavily overbooked. Your goal is
to devise a method such that every person who shows up to the stadium has
equal probability of being seated as compared to any other person (regardless
of the time at which this person shows up) but you also don’t want any seat
to remain empty. How will you do it? Once a person is refused entry, he/she
will never come back.

Alternate Problem Statement

Given a stream of input data where the total number of data points is un-
known and with limited space to store data, provide an algorithm such that
at the end of the stream, each of the data points has an equal probability of
being selected
(Source : The Idea of Reservoir Sampling)

3
Solution 3
Initialize an array R indexed from 1 to k, containing the first k items of the
input x1 , . . . , xk . This is the reservoir.

For each new input xi , generate a random number j uniformly in {1, . . . , i}. If
j ∈ {1, . . . , k}, then set R[j] := xi . Otherwise, discard xi .

Return R after all inputs are processed.

This algorithm works by induction on i ≥ k.

Proof of the algorithm

When i = k, Algorithm R returns all inputs, thus providing the basis for a
proof by mathematical induction.

Here, the induction hypothesis is that the probability that a particular input
is included in the reservoir just before the (i + 1)-th input is processed is ki
and we must show that the probability that a particular input is included in
k
the reservoir is i+1 just after the (i + 1)-th input is processed.

Apply Algorithm R to the (i + 1)-th input. Input xi+1 is included with proba-
k
bility i+1 by definition of the algorithm. For any other input xr ∈ {x1 , . . . , xi },
by the induction hypothesis, the probability that it is included in the reservoir
just before the (i + 1)-th input is processed is ki . The probability that it is still
included in the reservoirafter xi+1
 is processed (in other words, that xr is not
k 1 k
replaced by xi+1 is i × 1− i+1 = i+1 .

The latter follows from the assumption that the integer j is generated uni-
formly at random; once it becomes clear that a replacement will in fact occur,
k 1 1
the probability that xr in particular is replaced by xi+1 is i+1 k = i+1 .

We have shown that the probability that a new input enters the reservoir is
equal to the probability that an existing input in the reservoir is retained.
Therefore, we conclude by the principle of mathematical induction that Al-
gorithm R does indeed produce a uniform random sample of the inputs.

4
Problem 4
The ”board” on which this 2-person game is played is a monic polynomial
f (x) = x2n + a2n−1 x2n−1 + · · · + a1 x + 1
in which the 2n − 1 coefficients a2n−1 , . . . , a1 are unspecified real numbers
to begin with. The degree is set at any even integer ≥ 4, and the players,
starting with A, take turns specifying an undetermined coefficient until f (x)
is completely defined. At the end, A wins if no root of f (x) = 0 is real, and B
otherwise. Determine a winning strategy for B.
(Source : More Mathematical Morsels)

Solution 4
Since the degree is even, there is always an odd number of unspecified terms
at the beginning of the game, one more term of odd degree than of even de-
gree. For example,
for 2n = 10, there are 9 unspecified
terms, 5 of odd degree
x, x3 , x5 , x7 , x9 and 4 of even degree x2 , x4 , x6 , x8 . As we shall see, it is to
B ’s advantage to preserve this delicate imbalance, and so B ’s initial strat-
egy is simply to restore the status quo by doing just the opposite of what A
does- if A specifies a term of odd degree. then B specifies one of even degree,
and vice versa. At this point it doesn’t matter what value either A or B may
assign to his choice of coefficient. B stays with this approach until there are
exactly 3 terms left to be specified. At this stage, then, there must be left
two terms of odd degree and one of even degree. Since there is an odd num-
ber of unspecified coefficients to begin with, it is again A’s turn to play when
there are just 3 terms left, and, after making this move, he must present to B
a polynomial with only 2 unspecified terms, axs and bxt , where either (i) one
of s, t is even and the other odd, or (ii) both s and t are odd.
If P (x) denotes the part of f (x) that has already been specified to this point,
then f (x) = P (x) + ax2 + bxt , where a and b are still to be specified. Let us
consider the two cases separately. (i) Suppose s is even and t is odd. In this
case,

f (1) = P (1) + a + b
f (−1) = P (−1) + a − b
giving
f (1) + f (−1) = P (1) + P (−1) + 2a.
Now B wins by choosing the value of a so as to make the right side of this
equation equal to zero:
P (1) + P (−1)
a=−
2
This makes f (1) + f (−1) = 0, no matter what A puts for the value of b on the
final move of the game. Therefore either (a) f (1) and f (−1) are themselves

5
both zero, making both x = 1 and x = −1 real roots, or (b) one of f (1), f (−1)
is negative and the other positive, forcing a real root between 1 and -1 (by the
continuity of polynomials). (ii) Suppose s and t are both odd. In this case,
f (1) and f (−1) contain the same function of a and b, and cannot be solved
for a and b. However, if f (1) is replaced by f (2), we obtain

f (−1) = P (−1) − a − b
f (2) = P (2) + a2x + b2t

Thus b is eliminated by multiplying f (−1) by 2t and adding:

2t f (−1) + f (2) = 2t · P (−1) + P (2) − a 2t − 2s

Again, then, B crushes A by choosing a so as to make the right side vanish:

2t P (−1) + P (2)
a=
2t − 2s
( s ̸= t since they are exponents of different unspecified terms.) This makes
2t f (−1) + f (2) = 0, no matter how A may specify the last coefficient b and
again either (a) both f (−1) and f (2) are themselves zero, or (b) they straddle
zero (the factor 2t doesn’t affect this), implying a real root in either case.

Problem 5
You are playing a game with the Devil. There are n coins in a line, each show-
ing either H (heads) or T (tails). Whenever the rightmost coin is H, you de-
cide its new orientation and move it to the leftmost position. Whenever the
rightmost coin is T , the Devil decides its new orientation and moves it to
the leftmost position. If you can make all coins face the same way within 2n s,
you win, else the devil wins. Show that you have a winning strategy, i.e., no
matter what the devil does, you can find a way to make all coins heads or all
coins tails.

(Source : Some Online Math Club session)

Solution 5
We will first show that it is possible to achieve the desired configuration, and
worry about the number of steps later. Firstly, replace the heads with 0 and
the tails with 1. Then we do yet another simplification. Rather than moving
the coin itself to the left most end after each turn, what we do is imagine we
have a box placed at the coin where we will perform the operation. For the
binary string 1001, this looks something like this,

100 1 → 10 0 1 → 1 0 01 → 1 001

6
Where the boxed place is where the operation is taking place. After all the
coins have been acted upon, the box again moves to the rightmost end. Mark
this as the end of a round. It is clear that this setup is equivalent to the prob-
lem statement. Our strategy is to change all the 0’s to 1, until the devil changes
a 1 to a 0. To prove that this strategy works, note that if the devil changes no
1 to a 0, then we win because we get all 1’s. If the devil changes any of the
1’s to a 0, after that, we will keep the 0’s left to that place as a 0. Note that
if we follow this strategy, either we win at the end of a round or, the binary
value strictly decreases. It is easy to show that this strategy terminates with
at most 2n steps, and we leave it as an exercise!

Problem 6
Let F be the set of differentiable functions f : [0, 1] → R, with f ′ continuous
over [0, 1] and which verify the equalities
Z 1 Z 1
f (x)dx = xf (x)dx = 1
0 0
nR o
1 2
Find min 0
(f ′ (x)) dx | f ∈ F

(Source : Gazeta Mathematica Vol.2022,No.3-4)

Solution 6
Solution. Using integration by parts, we obtain that
Z 1 Z 1 Z 1
1 ′
1= f (x)dx = xf (x)|0 − xf (x)dx = f (1) − xf ′ (x)dx
0 0 0

and
Z 1 1 Z 1 Z 1
1 2 1 f (1) 1
1= xf (x)dx = x f (x) − x2 f ′ (x)dx = − x2 f ′ (x)dx
0 2 0 2 0 2 2 0
R1
x − x2 f ′ (x)dx =


By canceling out f (1) in the two equalities, we get that 0
The Cauchy-Schwarz inequality then leads to
Z 1 2 Z 1 Z 1

2 2
x − x2 f ′ (x)dx x − x2 (f ′ (x)) dx


1= ≤ dx ·
0 0 0
Z 1
1 2
= (f ′ (x)) dx
30 0

′
some α ∈ R, since f ′ is con-


with equality if and only if f (x) = α x − x2 for
2 3
tinuous. This happens when f (x) = α x2 − x3 + β, where the constants α

7
and β are such that f ∈ F. A simple computation leads to the linear system
1


 α+β =1
12
 7 α + 1β = 1

120 2
nR o
1 2
with the solution α = 30, β = − 32 . Concluding, min 0 (f ′ (x)) dx | f ∈ F =
30, which is achieved for the function f (x) = −10x3 + 15x2 − 23 .
Remark. There was another solution proposed using Euler Lagrange equa-
tion which turned out to be incorrect. The reason for incorrectness was the
fact that in the derivation of Euler Lagrange equation the end points are fixed
and the function is varied. But here the initial conditions given by the the
two equations did not imply fixed values at boundary of f (x).