Maths Beyond Limits Balkans 2024 Qualifying Quiz

We ask you to solve three out of five olympic problems (i.e. problems 1-5) and three exploratory ones (i.e. problems
6-8). Do not get upset if you find the problems difficult as they are meant to be demanding, thought-provoking and get
the best out of you. Also, do not hesitate to submit just partial solutions as sometimes they may be very near completion.
This applies especially to problems 6-8, which are meant to help us understand your mathematical maturity.
If you have some interesting observations concerning the introduced framework in the exploratory pro-
blems, or you find an intriguing question, share it with us in your solution! These will also be awarded
points even if you get stuck at the very beginning of the solution. Moreover, if you come up with some
idea for a modified version of the presented problem, send it to us – this will be highly beneficial to your
application!
You can use books or the Internet to look up definitions or formulas, but do not try to look for the problems
themselves! In case the problem statement is unclear to you even after getting help from the aforementioned
sources, please contact us. You may not consult or get help from anyone else. Violation of any of these rules
may permanently disqualify you from attending any Maths Beyond Limits camp.
We would like to thank Arsenii Nikolaiev, Srdan Stefanović and Marc de Fontnouvelle for their con-
tribution to this quiz.

1. Let ABCD be a cyclic quadrilateral and let X be the intersection of its diagonals AC and BD. Rays DA
and CB are extended to their intersection point Y . Let M be the midpoint of AB. If XY is perpendicular to
AC, prove that XM is perpendicular to BC.

2. Prove there exists a polynomial P with real coefficients such that for any positive integer n it holds:

√ √ √ √
⌊2 1⌋ + ⌊2 2⌋ + ⌊2 3⌋ + · · · + ⌊2 n2 ⌋ = P (n).

3. Let S be the set of all points in the plane. Find all functions f : S → R such that for all nondegenerate
triangles ABC with orthocenter H, if f (A) ≤ f (B) ≤ f (C), then

f (A) + f (C) = f (B) + f (H)

4. There are 2024 boxes numbered from 1 to 2024, some of which contain stones. Ania and Boris take moves
alternatively, starting with Ania. A move consists of selecting a non-empty box i, taking one or more stones
from that box and putting them in box i + 1. If i = 2024, the selected stones are removed. The player who
removes the last stone wins. If there is exactly one stone in each box in the beginning, who has the winning
strategy?

5. Let A = {1, 2, ..., 2024}. Find the least number of sets forming a partition of A such that for each set, gcd
between pairs of its members is either always greater than 1 or always 1.

Note: It can happen that if B and C are sets in the same partition of A, gcd of any two elements from the set
B is 1 while the gcd of any two elements from the set C is greater than 1.
For example sets {1, 3}, {5, 6}, {7, 8}, . . . , {2023, 2024}, {2, 4} form a partition that satisfies the problem condi-
tions. Of course, this is not an optimal one.
6. Suppose there is a probability space (Ω, P), where Ω = {ω1 , ω2 , ....} is a set of all simple events and P is a
function somehow defined on Ω, say P(ωi ) = pi ≥ 0 where p1 + p2 + p3 + ... = 1. This is just a more formal way
of saying that there are a bunch of simple events (finite or infinite number of them) with some probabilities
assigned to them.

Next, a random variable is, by definition, a function from Ω to R. We can then define

E(X) = p1 X(ω1 ) + p2 X(ω2 ) + ... + pn X(ωn )

and we call it mathematical expectation of a random variable X. Finally, the variance of X, denoted as
Var(X), stands for E(X 2 ) − E(X)2 . Now, you’re ready to try to solve the following exercises.

i) As a first exercise to make you a bit more comfortable with the definitions, prove/recall why maths
expectation is linear, i.e that

E(c1 · X + c2 · Y ) = c1 · E(X) + c2 · E(Y )

where c1 , c2 are constants and X, Y are some two random variables. Next, prove that the variance is
non-negative. Is it always true that Var(X + Y ) = Var(X) + Var(Y )?
ii) There are n real numbers on the board, among which there is a 0 and there is 1. Some of them can be
equal. Uniformly at random you select one of the numbers, say X (so this is a random variable). What is
the smallest possible variance of X and for what kind of distribution will it be achieved?
iii) There are two rods of unknown visibly different lengths a and b. You need to measure their length using
the ruler you have as ”good”as possible. In this case, ”good”means that you want the variance of the error
of your measurement (which is random...) to be as small as possible. Of course, we assume the mean of
the error is 0, and suppose the variance is σ 2 . To estimate the lengths of the measurements we could take
separate independent measurements A (for the first rod) and B for the second one and get

E(A) = a, Var(A) = σ 2 ; E(B) = b, Var(B) = σ 2

but can you do any ”better”?

iv) Prove that P(X ≥ c) ≤ E[X]c (for a c > 0), and thus deduce that P(|X − E[X]| ≥ δ) ≤ Var(X)
δ2 (for a fixed
δ > 0) for any non-negative random variable X. Can one replace the ≤ with < in either of the inequalities
for all X with non-constant distributions?
v) In an imaginary world with strange creatures, 100 ploofs and 100 bloops are going on a blind dating event.
There are gonna be 100 tables with two chairs next to each and creatures will be (uniformly) randomly
allocated to those. Bloops are quite aggressive, and so if two of them sit next to each other, they will start
arguing and then soon leave. If a bloop and a ploof sit next to each other, there is a 50% chance the ploof
will leave (but the bloop will stay anyway). But if two ploofs, friendly accepting creatures, end up next to
each other, they will both stay. Find the largest constant c for which you can prove that the probability
that the number of creatures that will stay is gonna be between 100 and 150 is larger than c. The larger the
constant the more likely you are to receive more marks. Obviously no calculator, computers, simulations,
etc... will count as a solution.

7. For n ∈ N let c(n) denote the number of positive integers x < n such that n|xn + 1.

a) Are there infinitely many positive integers n such that c(n) = 0? Determine all such n.
b) Determine whether there exists a positive integer n such that
i) c(n) = 1
ii) c(n) = 170
iii) c(n) = 385
iv) c(n) = 399?
If so, do there exist infinitely many such n?
c) Find at least one positive integer t such that there exist finitely many, but at least one, positive integers
n such that c(n) = t. Are there infinitely many such t? Can you describe them all?

Can you characterize all positive integers s such that c(n) = s holds for at least one positive integer n?
8. To be able to solve the following problem you’ll have to become familiar with a few definitions which are
essential in a mathematical discipline called measure theory.

Definition 1: Let X be a non-empty set. Powerset of set X (symbol is P(X)) is the set of all subsets of X
(including ∅ and X).
For example, the powerset of X = {1, 2, 3} is P(X) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

Definition 2: A family of subsets I ⊆ P(X) is a semialgebra over X if:

s2) If A ∈ I, then X \ A = B1 ⊔ · · · ⊔ Bn , for some sets B1 , . . . , Bn ∈ I, where the symbol ⊔ means that
B1 , . . . , Bn are pairwise disjoint sets;
s3) If A, B ∈ I, then A ∩ B ∈ I.

Definition 3: A family of subsets A ⊆ P(X) is an algebra over X if:

We say that A is minimal algebra with some property if it is a subset of every other algebra with some property.

Definition 4: Let A be an algebra over X. Function µ : A → [0, +∞] is called measure on algebra if:
m1) µ(∅) = 0;
+∞
 +∞  +∞
F F P
m2) If An ∈ A, for all n ∈ N are pairwise disjoint sets such that An ∈ A, then µ An = µ(An ).
n=1 n=1 n=1

Definition 5: We says that measure µ on algebra A over X is complete if for every E ∈ A such that µ(E) = 0
and for every subset F ⊆ E it is valid that F ∈ A.

Definition 6: Let X be a set, A an algebra over it and µ measure on A. Function f : X → R is called

Problem: Let X = (0, +∞) i A = (0, 3] i B = (1, 7].

a) Find two different semialgebras I1 and I2 over X such that A and B are their elements, but neither of
them is algebra.
b) Find minimal algebra A over X such that A, B ∈ A.
c) How many elements does a minimal algebra containing A, B and C = {2024} has?

+∞,
 if 2 ∈ E
d) Define a function µ on the algebra A from b) with µ(E) = 10, if 1 ∈ E and 2 ∈
/ E . Prove that µ is

0, otherwise

a measure on algebra A over X.
e) If they exist, find µ((3, 7]) and µ((−2023, 2024)).
f) Is the measure µ complete?
g) Is the function f (x) = x A-measurable?

h) Find two different A-measurable functions.