MathDB

1

Divisors of almost primes are 1 modulo Fermat primes

We say that a square-free positive integer

n

is almost prime if

n \mid x^{d_1}+x^{d_2}+\dots+x^{d_k}-kx

for all integers

x

, where

1=d_1<d_2<\dots<d_k=n

are all the positive divisors of

n

. Suppose that

r

is a Fermat prime (i.e. it is a prime of the form

2^{2^m}+1

for an integer

m \ge 0

),

p

is a prime divisor of an almost prime integer

n

, and

p \equiv 1 \pmod{r}

. Show that, with the above notation,

d_i \equiv 1 \pmod{r}

for all

1 \le i \le k

. (An integer

n

is called square-free if it is not divisible by

d^2

for any integer

d>1

.)

9

1

An even number of possibilites to fill an array with increasing numbers

A matrix

A=(a_{ij})

is called nice, if it has the following properties: (i) the set of all entries of

A

is

\{1,2,\dots,2t\}

for some integer

t

; (ii) the entries are non-decreasing in every row and in every column:

a_{i,j} \le a_{i,j+1}

and

a_{i,j} \le a_{i+1,j}

; (iii) equal entries can appear only in the same row or the same column: if

a_{i,j}=a_{k,\ell}

, then either

i=k

or

j=\ell

; (iv) for each

s=1,2,\dots,2t-1

, there exist

i \ne k

and

j \ne \ell

such that

a_{i,j}=s

and

a_{k,\ell}=s+1

.
Prove that for any positive integers

m

and

n

, the number of nice

m \times n

matrixes is even. For example, the only two nice

2 \times 3

matrices are

\begin{pmatrix} 1 & 1 & 1\\2 & 2 & 2 \end{pmatrix}

and

\begin{pmatrix} 1 & 1 & 3\\2 & 4 & 4 \end{pmatrix}

.

8

1

An almost-linear recurrence featuring 2^n

Define the sequence

x_1,x_2,\dots

by the initial terms

x_1=2, x_2=4

, and the recurrence relation x_{n+2}=3x_{n+1}-2x_n+\frac{2^n}{x_n} \text{for} n \ge 1. Prove that

\lim_{n \to \infty} \frac{x_n}{2^n}

exists and satisfies

\frac{1+\sqrt{3}}{2} \le \lim_{n \to \infty} \frac{x_n}{2^n} \le \frac{3}{2}.

7

1

Finding det(AB) if A+B=I and (A^2+B^2)(A^4+B^4)=A^5+B^5

Let

n

be a positive integer. Suppose that

A

and

B

are invertible

n \times n

matrices with complex entries such that

A+B=I

(where

I

is the identity matrix) and

(A^2+B^2)(A^4+B^4)=A^5+B^5.

Find all possible values of

\det(AB)

for the given

n

.

6

1

A function from Q to Z cannot be monotone

Prove that for any function

f:\mathbb{Q} \to \mathbb{Z}

, there exist

a,b,c \in \mathbb{Q}

such that

a<b<c

,

f(b) \ge f(a)

and

f(b) \ge f(c)

.

5

1

How likely is it to be contained in the convex hull of n random points?

Let

n>d

be positive integers. Choose

n

independent, uniformly distributed random points

x_1,\dots,x_n

in the unit ball

B \subset \mathbb{R}^d

centered at the origin. For a point

p \in B

denote by

f(p)

the probability that the convex hull of

x_1,\dots,x_n

contains

p

. Prove that if

p,q \in B

and the distance of

p

from the origin is smaller than the distance of

q

from the origin, then

f(p) \ge f(q)

.

4

1

Subgroup generated by length-n words of an infinite g-h-sequence.

Let

g

and

h

be two distinct elements of a group

G

, and let

n

be a positive integer. Consider a sequence

w=(w_1,w_2,\dots)

which is not eventually periodic and where each

w_i

is either

g

or

h

. Denote by

H

the subgroup of

G

generated by all elements of the form

w_kw_{k+1}\dotsc w_{k+n-1}

with

k \ge 1

. Prove that

H

does not depend on the choice of the sequence

w

(but may depend on

n

).

3

1

Can a 0-1 matrix square to the matrix with all ones?

For which positive integers

n

does there exist an

n \times n

matrix

A

whose entries are all in

\{0,1\}

, such that

A^2

is the matrix of all ones?

2

1

Asymptotic behaviour of 1^12^2...*n^n

For

n=1,2,\dots

let

S_n=\log\left(\sqrt[n^2]{1^1 \cdot 2^2 \cdot \dotsc \cdot n^n}\right)-\log(\sqrt{n}),

where

\log

denotes the natural logarithm. Find

\lim_{n \to \infty} S_n

.

1

Equation with complex numbers on the unit circle

Determine all pairs

(a,b) \in \mathbb{C} \times \mathbb{C}

of complex numbers satisfying

|a|=|b|=1

and

a+b+a\overline{b} \in \mathbb{R}

.

2024 IMC

Subcontests

Divisors of almost primes are 1 modulo Fermat primes

An even number of possibilites to fill an array with increasing numbers

An almost-linear recurrence featuring 2^n

Finding det(AB) if A+B=I and (A^2+B^2)(A^4+B^4)=A^5+B^5

A function from Q to Z cannot be monotone

How likely is it to be contained in the convex hull of n random points?

Subgroup generated by length-n words of an infinite g-h-sequence.

Can a 0-1 matrix square to the matrix with all ones?

Asymptotic behaviour of 1^12^2...*n^n

Equation with complex numbers on the unit circle

2024 IMC

Subcontests

Divisors of almost primes are 1 modulo Fermat primes

An even number of possibilites to fill an array with increasing numbers

An almost-linear recurrence featuring 2^n

Finding det(AB) if A+B=I and (A^2+B^2)(A^4+B^4)=A^5+B^5

A function from Q to Z cannot be monotone

How likely is it to be contained in the convex hull of n random points?

Subgroup generated by length-n words of an infinite g-h-sequence.

Can a 0-1 matrix square to the matrix with all ones?

Asymptotic behaviour of 1^1*2^2*...*n^n

Equation with complex numbers on the unit circle

Asymptotic behaviour of 1^12^2...*n^n