MathDB

1

Set of Binary Strings

A binary string is a sequence, each of whose terms is

0

or

1

. A set

\mathcal{B}

of binary strings is deﬁned inductively according to the following rules.
[*]The binary string

1

is in

\mathcal{B}

.[/*] [*]If

s_1,s_2,\dotsc ,s_n

is in

\mathcal{B}

with

n

odd, then both

s_1,s_2,\dotsc ,s_n,0

and

0,s_1,s_2,\dotsc ,s_n

are in

\mathcal{B}

.[/*] [*]If

s_1,s_2,\dotsc ,s_n

is in

\mathcal{B}

with

n

even, then both

s_1,s_2,\dotsc ,s_n,1

and

1,s_1,s_2,\dotsc ,s_n

are in

\mathcal{B}

.[/*] [*]No other binary strings are in

\mathcal{B}

.[/*]
For each positive integer

n

, let

b_n

be the number of binary strings in

\mathcal{B}

of length

n

.
[*]Prove that there exist constants

c_1,c_2>0

and

1.6<\lambda_1,\lambda_2<1.9

such that

c_1\lambda_1^n<b_n<c_2\lambda_2^n

for all positive integer

n

.[/*] [*]Determine

\liminf_{n\to \infty} {\sqrt[n]{b_n}}

and

\limsup_{n\to \infty} {\sqrt[n]{b_n}}

[/*]
Note: The problem is open in the sense that no solution is currently known to part (b).

B3

1

Labelling of Graph

Let

G

be a ﬁnite simple graph and let

k

be the largest number of vertices of any clique in

G

. Suppose that we label each vertex of

G

with a non-negative real number, so that the sum of all such labels is

1

. Deﬁne the value of an edge to be the product of the labels of the two vertices at its ends. Deﬁne the value of a labelling to be the sum of values of the edges. Prove that the maximum possible value of a labelling of

G

is

\frac{k-1}{2k}

. (A ﬁnite simple graph is a graph with ﬁnitely many vertices, in which each edge connects two distinct vertices and no two edges connect the same two vertices. A clique in a graph is a set of vertices in which any two are connected by an edge.)

B2

1

Sum of factorials divisible by p

For each odd prime number

p

, prove that the integer

1!+2!+3!+\cdots +p!-\left\lfloor \frac{(p-1)!}{e}\right\rfloor

is divisible by

p

(Here,

e

denotes the base of the natural logarithm and

\lfloor x\rfloor

denotes the largest integer that is less than or equal to

x

.)

B1

1

Maximizing the integral

Determine all pairs

(a,b)

of real numbers with

a\leqslant b

that maximise the integral

\int_a^b e^{\cos (x)}(380-x-x^2) \mathrm{d} x.

A3

1

Dividing possible outcomes into two groups

For some positive integer

n

, a coin will be ﬂipped

n

times to obtain a sequence of

n

heads and tails. For each ﬂip of the coin, there is probability

p

of obtaining a head and probability

1-p

of obtaining a tail, where

0<p<1

is a rational number. Kim writes all

2^n

possible sequences of

n

heads and tails in two columns, with some sequences in the left column and the remaining sequences in the right column. Kim would like the sequence produced by the coin ﬂips to appear in the left column with probability

1/2

. Determine all pairs

(n,p)

for which this is possible.

A2

1

Operation a(b+1)

Consider the operation

\ast

that takes pair of integers and returns an integer according to the rule

a\ast b=a\times (b+1).

[*]For each positive integer

n

, determine all permutations

a_1,a_2,\dotsc , a_n

of the set

\{ 1,2,\dotsc ,n\}

that maximise the value of

(\cdots ((a_1\ast a_2)\ast a_3) \ast \cdots \ast a_{n-1})\ast a_n.

[/*] [*]For each positive integer

n

, determine all permutations

b_1,b_2,\dotsc , b_n

of the set

\{ 1,2,\dotsc ,n\}

that maximise the value of

b_1\ast (b_2\ast (b_3\ast \cdots \ast (b_{n-1}\ast b_n)\cdots )).

[/*]

A1

1

Sequence formed by product of prime factors

Consider the sequence of positive integers defined by

s_1,s_2,s_3, \dotsc

of positive integers defined by
[*]

s_1=2

, and[/*] [*]for each positive integer

n

,

s_{n+1}

is equal to

s_n

plus the product of prime factors of

s_n

.[/*]
The first terms of the sequence are

2,4,6,12,18,24

. Prove that the product of the

2019

smallest primes is a term of the sequence.

A4

1

$\sum_{n \in \mathbb{N}} \min(x_n, \frac{1}{n \log n})$ always diverges ?

Suppose

x_1,x_2,x_3,\dotsc

is a strictly decreasing sequence of positive real numbers such that the series

x_1+x_2+x_3+\cdots

diverges.
Is it necessary true that the series

\sum_{n=2}^{\infty}{\min \left\{ x_n,\frac{1}{n\log (n)}\right\} }

diverges?

2019 Simon Marais Mathematical Competition

Subcontests

Set of Binary Strings

Labelling of Graph

Sum of factorials divisible by p

Maximizing the integral

Dividing possible outcomes into two groups

Operation a(b+1)

Sequence formed by product of prime factors

$\sum_{n \in \mathbb{N}} \min(x_n, \frac{1}{n \log n})$ always diverges ?