PROBLEMS FOR THE 9th INTERNATIONAL TOURNAMENT OF YOUNG

MATHEMATICIANS

JULY 2017, IAŞI (ROMANIA)

Contents
Notation 1
1. Numbers from Strings 1
2. Monotonous Functions 2
3. Dense Analytic Curves 2
4. Partitions of Regular Polygons 3
5. Coin Toss Function 4
6. Rooks on Graphs 4
7. Weighted Sums of Distances 5
8. A Communication Network 6
9. An Approximation Problem 7
10. Kinds of Convexity 7

Keywords: 1. discrete optimization – 2. real analysis – 3. complex analysis – 4. combi-

natorial geometry, partition – 5. probability – 6. graph theory, combinatorics – 7. geometry,
optimization – 8. graph theory – 9. number theory – 10. convex analysis

Notation
N = {1, 2, 3, . . .} set of natural numbers (positive integers)
Zn = {0, 1, . . . , n − 1} ring of residue classes modulo n
Z, Q, R, C sets of integer, rational, real and complex numbers
R+ set of positive real numbers
Fq finite field of size q = pk
M ⊗N mean-product of two functions M and N
gcd(x1 , . . . , xn ) greatest common divisor of x1 , . . . , xn
P [.] and E [.] probability and expectation
det(A) or |A| determinant of a matrix A
|x| absolute value of x
#M or |M | cardinality of a set M
sup f (x) supremum of a set {f (x) | x ∈ M }
x∈M

1. Numbers from Strings

1. Four fours:
a) What is the largest number we can form with 4 fours by using only the four standard
arithmetic operations? (You are allowed to concatenate several fours to obtain, for
example, 44.)
b) What is the smallest positive number?
c) How many numbers can be formed ?
Date: April 3, 2017.
1
2 JULY 2017, IAŞI (ROMANIA)

2. Five fives:
a) Investigate this question for 5 fives if the additional (fifth) operation of exponentiation
(ab ) is allowed.
b) Try another “fifth operation” instead.

3. In this question we consider the number of symbols in the expression we evaluate. For
example, the string “(4 + 4) ∗ (4 + 4)” uses 11 characters and evaluates to 64.
a) Using the digits 0 to 9, the 4 operations and brackets, what is the largest number using
n symbols?
b) If we allow variables and assignment statements like “a = 32, b = 77, a ∗ b ∗ b”, what
is the largest number that can be obtained by evaluating the string with 10; 15 and
20 symbols? Try to generalise. We assume here that statements may involve only 4
arithmetic operations and possibly assignments. Different statements are separated by
comma (which also counts as a symbol!), and the final result is the evaluated value of
the last statement in the string.
c) If we allow one-argument function exp, what will be the result?

4. Define the “value” of a string of n symbols as logd (eval(string)), where d = #{string} is the
number of different symbols used. What is the largest possible value of a string with 5, 10, 15
symbols?

2. Monotonous Functions
Denote by f (x), g(x), h(x) some real-valued functions defined for all x ∈ R such that:
f (x)g(x) = h(x) for all x ∈ R. (1)

1. Do there exist strictly increasing functions f (x) and g(x) satisfying (1), if h(x) = x is the
identical function? Do such functions f (x) and g(x) exist, if in addition they are:
a) continuous for all x ∈ R?
b) differentiable (twice differentiable, infinitely differentiable) for all x ∈ R?
c) entire, that is represented as a sum of the power series converging for all x ∈ R?
d) discontinuous at a fixed finite set of points on the line?
e) discontinuous at a fixed countable set of points on the line?

2. Give an answer to the above questions, if h(x) = a sin(x) + b cos(x) + c is a trigonometric

polynomial.
3. For each item in question 1, describe classes of functions h(x) for which the answer is positive.
In other words, describe all functions h(x) that can be represented as (1) with additional
conditions on the strictly increasing functions f (x) and g(x).
4. Investigate how non-monotonous the function h(x) can be in each of the classes from the
previous item. In particular, can the function h(x) be non-monotonous for each x ∈ R, that is
the expression (h(x) − h(a))(x − a) has different signs on any open interval containing x?

3. Dense Analytic Curves

The problem is concerned with the existence of analytic curves that are dense in C.
1. Let L be any line in the complex plane:
L = {at + b : t ∈ R}, where a, b ∈ C.
 PROBLEMS FOR THE 9th INTERNATIONAL TOURNAMENT OF YOUNG MATHEMATICIANS 3

Describe all possibilities for exp(L). Recall that the complex exponential exp(z) is defined for
z = x + iy as:
∞
z n /n! = exp(x) exp(iy) = exp(x)(cos y + i sin y).
X
exp(z) =
n=0

2. Describe all possibilities for exp(exp(L)). In particular, state necessary and sufficient con-
ditions for when this is dense in C.
3. Show that exp(exp(exp(L))) is always dense in C unless a, b are exceptional. What are these
exceptions?
4. Are there analogous results for maps of the form cos(z), or exp(z) + c, or a cos(z) + bsin(z),
or some other map?
5. Can you find similar results in three or more dimensions?

4. Partitions of Regular Polygons

1. Let n ≥ 1 be an integer. We consider the following equation, where n, a, b and c are positive
integers:
an + bn = nc .
a) Solve the equation for n = 2.
b) Solve the equation when n is a prime number.
c) Study the solutions of the equation when n is not prime.

2. Let n ≥ 3 be an integer and let Pn be the regular polygon with n sides inscribed in the
unit circle and whose vertices are the n complex roots of unity. Fix an integer k ≥ 3. A
k-angulation of Pn is a collection of diagonals of Pn that may intersect only at their endpoints
and such that every face has degree k (a degree of a face is the number of diagonals or sides of
(k)
Pn that surround the face). For k ≥ 3, let Zn be the number of k-angulations of Pn .
(3) (3)
a) Find a formula for Zn . How does Zn behave for large n?
(3) (3)
b) For k ≥ 4, express Zn . How does Zn behave for large n?
(k)
3. Let An be a k-angulation of Pn chosen randomly among all k-angulations of Pn . Let
(k) (k)
χ(An ) be the length of the longest diagonal of An . Find a; b > 0 such that:

P(χ(A(3)
n ) > a) → 1; P(χ(A(3)
n ) < b) → 1,

as n tends to infinity.
4. Does there exist a function f : R → R such that for every 0 ≤ u ≤ v we have:
Z v
P(u ≤ χ(A(3)
n ) ≤ v) → f (x)dx
u

as n tens to infinity?
(3) (k)
5. Investigate questions 3 and 4 when An is replaced by χ(An ).
(k)
6. Investigate question 3, 4 and 5, when χ(An ) is replaced by the largest area of all faces in
(k)
An .
4 JULY 2017, IAŞI (ROMANIA)

5. Coin Toss Function

Let p ∈ (0; 1) be a real number. Consider an infinite process of tossing a coin, such that on
each trial the probability for heads is p. Form the random binary number X = 0, a1 a2 a3 . . . as
follows: if the i-th toss gives heads, then ai = 1, else ai = 0. If x ∈ [0; 1] is a real number, then
denote by Fp (x) the probability that X ≤ x.
1. Calculate Fp ((0, 11111100001)2 ) and Fp (1/2017) in terms of p. Can you give general algo-
rithm(s) for calculating Fp (x) for a given decimal x, if x is:
a) of the form a/2k , a; k ∈ N;
b) rational;
c) irrational.

2. Let n be a positive integer. Calculate the expected value of X n .

3. Investigate the function Fp (X) in more detail:
a) Show that Fp (x) is strictly increasing in [0; 1].
b) Show that Fp (x) is continuous in [0; 1].
c) For which p the function Fp (x) uniformly continuous in [0; 1]?

4. Let n be a positive integer. Find:

a) 01 Fp (x)n dx.
R

b) the arc length of the graph of Fp (x)n on the interval [0; 1].

5. Let p 6= 1/2. Denote by fp (x) the derivative of Fp (x) (at points x where it exists).
a) Show that fp (x) does not exist if x is of the form a/2k , a; k ∈ N.
b) For a fixed p, describe the behaviour of the derivative fp (x): for which x ∈ R does it
exist (or is infinite) and at which points it does not exist? How to find its value?
c) Find all x ∈ R in which the derivative exists (and is not infinite) for all p.

6. Suggest and investigate generalisations. For example, one can define a similar function in
k-number system, if instead of 2 outcomes (0 and 1) we have k outcomes (0, 1, . . . , k − 1), with
probabilities p0 , p1 , . . . , pk−1 .

6. Rooks on Graphs

1. Consider an m by n grid:

C1 C2 C3 C4

B1 B2 B3 B4

A1 A2 A3 A4

a) Place a rook on the lower left corner of this grid. In how many ways can the rook reach
the upper right corner if in a single step it may move one edge up or one edge to the
right, but not down or left? For example, the rock can move A1−A2−B2−B3−B4−C4
in the grid above.
 PROBLEMS FOR THE 9th INTERNATIONAL TOURNAMENT OF YOUNG MATHEMATICIANS 5

b) Now suppose the rook can move in each of the four directions. In how many ways it can
reach the upper left corner (A1 and C1 in the grid in the picture), if at the beginning it
is placed on the lower left corner and the rook can’t go through an edge more than once?
An example of a valid path is A1 − A2 − A3 − A4 − B4 − C4 − C3 − C2 − B2 − B1 − C1
in the grid above. Start with small m = 2, 3, 4, . . .
c) Find the number of rook paths, which do not pass through the same edge more than
once and join the opposite vertices of the grid (A1 and C4 in the grid on the picture).
Start with the case when the grid is square (m = n) and some small value of m.

2. Now assume the grid is infinite.

a) Find the number of paths which start and end at the same vertex, do not pass through
the same edge more than once and go through exactly t edges (vertices do not need to
be necessarily distinct).
b) Start at an arbitrary vertex and start moving along the grid with equal probability in
each direction. Find the probability of the event that the path of the rook forms a cycle
of length t without repeating edges.

3. Now instead of a grid we will generalise the problem by looking at a graph G(V ; E) without
loops or multiple edges.
a) Find the number of cycles of length t in a complete graph G = Kn with n vertices (the
vertices can be repeated but the edges can not).
b) For which n does there exist a cycle which covers all edges of the complete graph Kn ?
(Each edge is used exactly once.)

4. Now remove one edge from the complete graph Kn .

a) Find the the number of cycles of length t in the new graph Kn0 .
b) How the answer will change if we remove 2 edges from the complete graph Kn ? Does
the answer depend on which 2 edges were removed?

5. Suppose again that G = Kn is the complete graph with n vertices. Start at an arbitrary
vertex and start moving along the graph with equal probability. Give upper and lower bound
for the probability of the event that the path forms a cycle of length t without repeating edges.

7. Weighted Sums of Distances

Let 4ABC be a triangle and (λ, µ, ν) be a triple of real numbers with λ + µ + ν 6= 0. Let
also X be a point in the plane of the triangle. Denote by d1 , d2 , d3 the oriented distances from
X to the lines BC, CA and AB, respectively. We are interested in the function:
f (X) = λd21 + µd22 + νd23
and in particular, in its minimum and maximum (if they exist).
1. Let λ = µ = ν = 1. Prove that the minimum of f exists and is attained only at the Lemoine
point of 4ABC.
2. Let λ, µ, ν be non-negative.
a) Suppose λµν 6= 0. Prove that f (X) always has a minimum and describe the points (in
terms of λ, µ, ν) at which it is attained.
b) What happens in the case λµν = 0?

3. Consider the case when exactly one of λ, µ or ν is negative.

4. Consider the general case:
6 JULY 2017, IAŞI (ROMANIA)

a) Find all triples (λ, µ, ν), λ + µ + ν 6= 0 (and the respective attainable points X) for
which f (X) has a minimum, and those for which it has a maximum.
b) Answer the above question in the cases when λ + µ + ν = 0.

5. Answer question 4 for the function

f (X) = λd31 + µd32 + νd33 .

6. Now instead of the triangle consider a tetrahedron and quadruples (λ1 ; λ2 ; λ3 ; λ4 ) of real
numbers with non-zero sum. Similarly, we can define a function
f (X) = λ1 d21 + λ2 d22 + λ3 d23 + λ4 d24 ,
where di are the distances from a point X in space to the planes containing the faces of the
tetrahedron A1 A2 A3 A4 . Find all quadruples (and the respective attainable points X) for which
f (X) has a minimum, and those for which it has a maximum.
7. Similarly, consider an n-dimensional simplex and an analogously defined function (with
squared distances) for points in n-dimensional space.

8. A Communication Network
Consider the communication network consisting of nodes and communication channels be-
tween some of the nodes. Two nodes can communicate either via the direct channel between
them (if any), or via any other channels connecting these nodes. The network is called valid, if
any two nodes are able to exchange messages.
There is some secret information split between nodes in such a way that each node contains
a part of the secret not known to any other node in the network. Any node N can broadcast
a message. In this case all its information (its initial part of the secret and all secret parts
received from other nodes up to this moment) becomes known to all nodes connected with N
via the direct channel. The minimal number of such messages in order for all nodes to obtain
the entire secret (i.e. the secrets from all other nodes) is called a secret connectivity number or
just a secret number of the network.
We can model such communication network by a graph G, where vertices of G correspond to
nodes and edges of G become direct communication channels. A valid communication network
corresponds to a connected simple graph G.
Denote by s(G) the secret connectivity number of the corresponding network. For example,
if G = P4 is a simple chain with vertices {v1 , v2 , v3 , v4 } and edges {v1 v2 , v2 v3 , v3 v4 }, then
s(G) = 5, and one of the optimal sequences of messages is {v1 , v4 , v3 , v2 , v3 }.
1. Find s(G) for the following graphs:
a) the complete graph Kn ;
b) the simple cycle graph Cn (i.e. the graph represented by a regular n-gon);
c) the simple chain Pn ;
d) the complete k-partite graph Kn1 ,n2 ,...,nk ;
e) the graph of a three-dimensional cube;
f) the Petersen graph.

2. Let T be an arbitrary connected tree with n vertices. Find s(T ) and describe an algorithm
generating an optimal sequence of messages.
3. Consider the case of a connected unicyclic graph, that is a connected graph with a single
cycle.
4. Consider the graph Gm,n of the m by n grid (see Problem 6).
 PROBLEMS FOR THE 9th INTERNATIONAL TOURNAMENT OF YOUNG MATHEMATICIANS 7

5. Try to relate s(G) or at least estimates for s(G) with other known numeric invariants of
graphs.

9. An Approximation Problem

1. Consider the following subset of rational numbers

1
 
U = x− | x ∈ Q, x 6= 0 .
x
a) Show that U is dense in the real line (that is for any non-empty interval I ⊂ R, there
exists an element r ∈ U which belongs to I)?
b) Denote by aU the set of products ar with r ∈ U . Show that for any real a 6= 0, the set
aU is also dense in R.
2. Study intersections aU ∩ bU where a and b are integers. In particular, determine whether
aU ∩ bU is a) empty; b) infinite; c) dense in R.
3. Let n > 2 be a natural number. Study intersections a1 U ∩ . . . ∩ an U where a1 , . . . , an are
integers.
4. More generally, let f : D → R be a real-valued function defined on a domain D ⊂ R.
Consider the following set
Uf = {f (x) | x ∈ Q ∩ D } .
For example, in the previous questions U = Uf with f (x) = x − 1/x and D = R \ {0}.
Check the density of sets a1 Uf ∩ . . . ∩ an Uf where n is a natural number and a1 , . . . , an are
integers, in the following situations:
a) f is a polynomial with integer coefficients;
P (x)
b) f (x) = Q(x) , where P (x) and Q(x) are polynomials with integer coefficients (start with
polynomials of degree at most 2);
c) f is a trigonometric function;
d) f (x) = TS(x)(x) , where S(x) and T (x) are trigonometric polynomials with integer coeffi-
cients.
5. Suggest and investigate additional directions of research.

10. Kinds of Convexity

Recall that a function f (x) defined on an interval I ⊂ R is called convex on I, if for any
x, y ∈ I and any λ ∈ [0; 1] we have the following inequality:
f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y)

1. Let f (x) be a convex function on I. Let a1 ≤ a2 ≤ . . . an , b1 ≤ b2 ≤ . . . bn and ai + bj ∈ I

for all 1 ≤ i, j ≤ n. Prove the following inequality:
n
X n
X
f (ai + bi ) ≥ f (ai + bn−i+1 ).
i=1 i=1

2. Let f (x) be a convex function on I. Let a1 ≤ a2 ≤ . . . an , b1 ≤ b2 ≤ . . . bn and ai bj ∈ I for

all 1 ≤ i, j ≤ n.
a) Is it true that
n
X n
X
f (ai bi ) ≥ f (ai bn−i+1 )?
i=1 i=1
8 JULY 2017, IAŞI (ROMANIA)

b) If not, try to find additional conditions on ai and bi , so that it becomes true.

3. Fix a positive real number s. Let us say that the function f (x) is s-convex of first kind, if
for any x, y ∈ I and any λ ∈ [0; 1] we have the following inequality:
f (λx + (1 − λ)y) ≤ λf (x)s + (1 − λ)f (y)s .
a) For which s there exist a function f (x) on a closed interval I ⊂ R, which is s-convex of
first kind, but not convex?
b) Which of the inequalities from questions 1 and 2 hold for any s-convex function of first
kind?
4. Let us say that the function f (x) is s-convex of second kind, if for any x, y ∈ I and any
λ ∈ [0; 1] we have the following inequality:
f (λx + (1 − λ)y) ≤ λs f (x) + (1 − λ)s f (y).
Solve question 3 for s-convex functions of second kind.

E-mail address: [email protected]

URL: http://www.itym.org/